has_path Equivalence

graph-tool
1

Hello,

I was wondering if there's a equivalent to NetworkX's has_path function. I'd like to check if there is a path
between two given vertexes, and if there is, then return True. This can be done in NetworkX with has_path. I think
this is doable in graph-tool with StopSearch method, but I couldn't figure out a way to implement it. Any help is appreciated.

Thanks.

2

This is trivial, just do:

   has_path = shortest_distance(g, u, v) < g.num_vertices()

Best,
Tiago

3

Hi,

Thanks for the reply. I've got two more questions:

edges = g.edge(1, 536)
for e in edges:
     print(e)

returns None because there's no such edge. However, when I run

  gt.shortest_distance(g, 1, 536)

it returns 2, but there shouldn't exist a path with length 2 between those points, am I wrong about
this? What am I missing?

Also, slightly related, I added those points with g.add_edge_list(my_edge_list), which is a list of
integer couples between 1 and 18000. Is there a way to run shortest_path just by using those
numbers, without indexes?

Like, gt.shortest_path(g, 1, 536)

The above returns

Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
   File "/opt/anaconda3/lib/python3.6/site-packages/graph_tool/topology/__init__.py", line 1882, in
shortest_path
     for e in v.in_edges() if g.is_directed() else v.out_edges():
AttributeError: 'int' object has no attribute 'in_edges'

4

Hi,

Thanks for the reply. I've got two more questions:

edges = g.edge(1, 536)
for e in edges:
print(e)

returns None because there's no such edge. However, when I run

gt\.shortest\_distance\(g, 1, 536\)

it returns 2, but there shouldn't exist a path with length 2 between those
points, am I wrong about this? What am I missing?

The existence of an edge between two nodes means that they are at a distance
one from one another. The absence of an edge means the distance must be 2 or
larger. A distance of 2 just means they share a neighbor.

Also, slightly related, I added those points with
g.add_edge_list(my_edge_list), which is a list of integer couples between 1
and 18000. Is there a way to run shortest_path just by using those numbers,
without indexes?

Like, gt.shortest_path(g, 1, 536)

The above returns

Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File
"/opt/anaconda3/lib/python3.6/site-packages/graph_tool/topology/__init__.py", line
1882, in shortest_path
for e in v.in_edges() if g.is_directed() else v.out_edges():
AttributeError: 'int' object has no attribute 'in_edges'

The function expects vertex descriptors:

    shortest_path(g, g.vertex(1), g.vertex(536))

I'll fix it so that it accept indices for convenience.

Best,
Tiago