directed connectivity in DiGraphs

[Larry Moss]

I'm doing calculations that involve DiGraphs, and I'd like to know whether there's a path from one point to another.   

I had been using

def Conn(G,i,j):

    return(G.all_paths(i,j) != [])

But when the graphs got big, this started to take forever.   

I tried

def Conn2(G,i,j):

    return(j in Set(G.connected_component_containing_vertex(i)))

but this treats ignores the directedness.

Any ideas?

[Nathann Cohen]

Hello !

I'm doing calculations that involve DiGraphs, and I'd like to know whether there's a path from one point to another.   

Did you try computing D.distance(i,j) ? Or D.shortest_path(i,j) ? 

I had been using

def Conn(G,i,j):

    return(G.all_paths(i,j) != [])

But when the graphs got big, this started to take forever.   

Well, you ask it to list all paths. There are more than (n-2)! paths from i to j in a complete graphs..

def Conn2(G,i,j):

    return(j in Set(G.connected_component_containing_vertex(i)))

but this treats ignores the directedness.

Use distances. And you may be interested by the four d.strongly_connected_component* functions.

Nathann