Search code examples
c++graphboost-graph

Query a complete directional graph to determine downstream/upstream relationship and distance

Assuming that I've already constructed a graph using the Boost graph library to represent a complete directed graph, how would someone query the graph, given a set [node_a,node_b] to determine if node_b is "downstream" from node_a and by what distance. Here, I mean "downstream" in that node_a does not need to be immediately adjacent to node_b but that some path may be found through the graph to get from node_a to node_b.

I understand how to construct the graph but am fuzzy on how to utilize the built-in function to determine the information that I need. Any help would be appreciated...

Thanks!

Solution

  • You can use the Dijkstra algorithm to determine the distance from node a to node b. If the distance is finite, then they are connected.

    http://www.boost.org/doc/libs/1_55_0/libs/graph/doc/dijkstra_shortest_paths.html