|
From: Szabolcs B. <bes...@gm...> - 2014-11-03 15:17:06
|
I'm glad I could help. Regards, Szabolcs 2014-11-03 15:26 GMT+01:00 Davide Cavestro <dav...@gm...>: > 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 >>>> >>>> >>> >> > |
