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

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Davide Cavestro
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
Reply | Threaded
Open this post in threaded view
|

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

Szabolcs Besenyei


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
Reply | Threaded
Open this post in threaded view
|

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

Davide Cavestro
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



------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

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

Szabolcs Besenyei
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




------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

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

Davide Cavestro
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:
  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 <[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





------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users
Reply | Threaded
Open this post in threaded view
|

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

Szabolcs Besenyei
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:
  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 <[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






------------------------------------------------------------------------------

_______________________________________________
jgrapht-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgrapht-users