CODEWITHSUNDEEP
graph-tool
Espenol
Espenol

Reputation: 21

Finding all paths between source and target in graph-tool, return edges instead of vertices

Stack Overflow!

I have a directed graph and need to find all paths between a source and target vertex. Between several vertices, there are multiple edges. Using graph-tool, one may suggest using graph_tool.topology.all_paths(g, source, target), however, the lists contained in this vertex iterator are for vertices only; see some of the output below. Due to there being multiple edges between vertices, there are multiple occurrences of paths such as [ 0 4 8 13] and [0 4 13] and I am not able to distinguish between these paths. 

iterator, paths:  [ 0  4  8 13]
iterator, paths:  [ 0  4 13]
iterator, paths:  [ 0  4  8 13]
iterator, paths:  [ 0  4 13]
iterator, paths:  [ 0  4  8 13]
iterator, paths:  [ 0  4 13]

I need the paths in the form of edges, to be able to iterate over edge properties along each path. To solve this issue, I can only think of one method (apart from rewriting large amounts of code): creation of intermediary vertices to avoid occurrences of multiple edges between any two vertices. For any parallel edges between two vertices, they would be connected to each their own, unique intermediary vertex as to uniquely define the paths returned from graph_tool.topology.all_paths(g, source, target).

Is there a way to return all paths in the form of edges between a source and destination vertex?

Upvotes: 2

Views: 924

Answers (2)

Tiago Peixoto
Tiago Peixoto

Reputation: 5261

This has been added to graph-tool recently: https://git.skewed.de/count0/graph-tool/commit/5457d04f5f37c7a49e87b67c666c1a865e206b9a

You just need to pass the edges=True parameter:

for p in all_paths(g, u, v, edges=True):
    for e in p:
        print(e)  # e is an edge descriptor

Upvotes: 3

Paul Brodersen
Paul Brodersen

Reputation: 13041

Finding all paths is pretty computationally expensive (O(N+E), IIRC) already. If you are ultimately interested in the combinations of data attributes of your edges then I would find the path on a reduced graph (without multi-edges), and then look up the possible data attributes of each edge (can be done in constant time) and compute the possible combinations of data attributes. Step-by-step:

Find the paths. Convert the list of nodes to a list of edges. 

path_edges = zip(path_nodes[:-1], path_nodes[1:])

Create a dictionary (dict) mapping each edge (source, target) to a list of data attributes, e.g. [0.2, 0.7, 42]. Each data attribute corresponds to one multi-edge (presumably, many of these will be lists of length 1 in your case as multi-edges seem rare from the data sample you gave).

Compute all combinations of data attributes for all edges in the path. 

 data = [edge_to_data[edge] for edge in path_edges]
 cartesian_product = itertools.product(*data) # returns an iterator!
 print(list(cartesian_product))

Finally, apply your cost function or whatever to the list of values.

Upvotes: -1

Related Questions