Fwd: Reg, Boost lib dijkstra_shortest_paths for ECMP paths

From: kathireswaran thanuskodi (kthanusk_at_[hidden])
Date: 2021-09-06 10:19:10

Hi Team,

I came across the boost lib to identify the shortest paths in an
network using vertex/edge properties, and have
using dijkstra_shortest_paths method with predecessor_map concept with that
able to get the shortest path in the graph.

Have a requirement like to know about multiple shortest paths also if
present, for example below find the below network diagram with 4 edges,

A ------- B
|            |
|            |
D ------- C

Edges -> (A,B), (A,D), (B,C), (C,D) with equal distance 1.

With the predecessor_map as of now able to get path as A->B->C so that the
parent of C is noted as B.
In this example we have ECMP(equal cost multiple path) from src A to
destination C, tried to search for existing lib to achieve fetching all the
paths but unfortunately unable to identify the way.
kindly guide how to get such kind of multiple path info with the existing
library itself or not. If there exists how to get those info.

*<code snip>*
const int num_nodes = 4;
  enum nodes { A, B, C, D};
  Edge edge_array[] = { Edge(A, B), Edge(B, C), Edge(A, D), Edge(C,D)
  };
  int weights[] = { 1, 1, 1,1 };
  int num_arcs = sizeof(edge_array) / sizeof(Edge);
  graph_traits<graph_t>::vertex_iterator i, iend;

  graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
  property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight,
g);
// Manually intialize the vertex index and name maps
  property_map<graph_t, vertex_index_t>::type indexmap = get(vertex_index,
g);
  property_map<graph_t, vertex_name_t>::type name = get(vertex_name, g);
  int c = 0;
  for (boost::tie(i, iend) = vertices(g); i != iend; ++i, ++c) {
    indexmap[*i] = c;
    name[*i] = 'A' + c;
  }

  vertex_descriptor s = vertex(A, g);

  property_map<graph_t, vertex_distance_t>::type
    d = get(vertex_distance, g);
  property_map<graph_t, vertex_predecessor_t>::type
    p = get(vertex_predecessor, g);

  dijkstra_shortest_paths(g, s, predecessor_map(p).distance_map(d));

  std::cout << "distances and parents:" << std::endl;
  graph_traits < graph_t >::vertex_iterator vi, vend;
  for (boost::tie(vi, vend) = vertices(g); vi != vend; ++vi) {
    std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
    std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] << std::
      endl;
  }
  std::cout << std::endl;
*<code snip>*

*<output>*

distances and parents:
distance(A) = 0, parent(A) = A
distance(B) = 1, parent(B) = A*distance(C) = 2, parent(C) = B
     <<<<<<<<<<<<<<<*
distance(D) = 1, parent(D) = A

Regards,
Kathir