|
From: Davide C. <dav...@gm...> - 2014-11-03 14:26:37
|
I guess *strongly connected <http://en.wikipedia.org/wiki/Strongly_connected_component>* 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: 1. an in-depth visit to determine the subgraph *vertexSet* 2. then filtering the graph *edgeSet* to keep only the ones for which both vertex belongs to the subgraph vertexSet. 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 <bes...@gm...>: > 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 > <http://en.wikipedia.org/wiki/Strongly_connected_component> 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 <dav...@gm...>: > >> 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 <bes...@gm...>: >> >>> >>> >>> 2014-10-31 18:23 GMT+01:00 Davide Cavestro <dav...@gm...>: >>> > 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 >>> jgr...@li... >>> https://lists.sourceforge.net/lists/listinfo/jgrapht-users >>> >>> >> > |
