jgrapht-users

On extracting a directedsubgraph containing only elements reachable from a given vertex

Classic

List

Threaded

6 messages Options

Davide Cavestro

On extracting a directedsubgraph containing only elements reachable from a given vertex

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

Szabolcs Besenyei

Re: On extracting a directedsubgraph containing only elements reachable from a given vertex

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.

ke a look at org.jgrapht.alg.ConnectivityInspector#pathExists.

--
Regards,

Szabolcs

Davide Cavestro

Re: On extracting a directedsubgraph containing only elements reachable from a given vertex

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]>:

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

Szabolcs Besenyei

Re: On extracting a directedsubgraph containing only elements reachable from a given vertex

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]>:

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]>:

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

Davide Cavestro

Re: On extracting a directedsubgraph containing only elements reachable from a given vertex

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:

an in-depth visit to determine the subgraph vertexSet
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 <[hidden email]>:

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]>:
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]>:

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

Szabolcs Besenyei

Re: On extracting a directedsubgraph containing only elements reachable from a given vertex

I'm glad I could help.

Regards,

Szabolcs

2014-11-03 15:26 GMT+01:00 Davide Cavestro <[hidden email]>:

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:
an in-depth visit to determine the subgraph vertexSet
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 <[hidden email]>:
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]>:
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]>:

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