I'm trying to figure out a way to extract from a DirectedGraph instance a DirectedSubgraph containing only the subset of vertex/edges reachable from a given vertex (of the original graph).
Any help appreciated. ------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
2014-10-31 18:23 GMT+01:00 Davide Cavestro <[hidden email]>: > I'm trying to figure out a way to extract from a DirectedGraph instance a > DirectedSubgraph containing only the subset of vertex/edges reachable from a > given vertex (of the original graph). > Any help appreciated. Ta ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.-- Regards, Szabolcs ------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
Thankyou for the quick hint... but It seems that org.jgrapht.alg.ConnectivityInspector#pathExists ignores edges direction (as it is based on org.jgrapht.alg.ConnectivityInspector#connectedSetOf) Is there any way to determine the set of paths reachable from a given vertex of a directed graph? This way I could use the results to create a DirectedSubGraph 2014-11-01 1:04 GMT+01:00 Szabolcs Besenyei <[hidden email]>:
------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
Given the problem a little bit more thought I think what you are trying to achieve is the same as determining the strongly connected components of a given directed graph. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that are themselves strongly connected. So the functionality of org.jgrapht.alg.StrongConnectivityInspector<V, E> meets the requirements of your problem. Regards, Szabolcs 2014-11-03 12:58 GMT+01:00 Davide Cavestro <[hidden email]>:
------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
I guess strongly connected means that every vertex is reachable from every other vertex, but this condition would be far too strict for my needs. I've managed to obtain the subgraph with:
Many thanks Davide PS: Follows a working groovy snippet for later reference... just my two cents import org.jgrapht.* import org.jgrapht.graph.* import org.jgrapht.alg.* import org.jgrapht.traverse.* import org.jgrapht.experimental.dag.* @Grab(group='org.jgrapht', module='jgrapht-core', version='0.9.0') DirectedGraph graph = new DirectedAcyclicGraph(DefaultEdge) graph.addVertex ('A') graph.addVertex ('B') graph.addVertex ('C') graph.addVertex ('D') graph.addVertex ('E') graph.addVertex ('F') graph.addEdge ('A', 'B') graph.addEdge ('B', 'C') graph.addEdge ('B', 'D') graph.addEdge ('D', 'C') graph.addEdge ('A', 'E') graph.addEdge ('E', 'F') graph.addEdge ('F', 'D') //println "graph: $graph" Iterator iterator = new DepthFirstIterator (graph, 'B') Set vertexSubset = [] as LinkedHashSet //determine the vertexset for the subgraph while (iterator.hasNext()) { vertexSubset << iterator.next() } //filter the full graph edgeset to obtain the subgraph one Set edgeSubset = graph.edgeSet().findAll {edge-> graph.getEdgeSource (edge) in vertexSubset && graph.getEdgeTarget (edge) in vertexSubset } //create the subgraph DirectedSubgraph subgraph = new DirectedSubgraph (graph, vertexSubset, edgeSubset) //println "subgraph: $subgraph" 2014-11-03 13:31 GMT+01:00 Szabolcs Besenyei <[hidden email]>:
------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
I'm glad I could help. Regards, Szabolcs 2014-11-03 15:26 GMT+01:00 Davide Cavestro <[hidden email]>:
------------------------------------------------------------------------------ _______________________________________________ jgrapht-users mailing list [hidden email] https://lists.sourceforge.net/lists/listinfo/jgrapht-users |
Free forum by Nabble | Edit this page |