How to use boost::graph dijkstra's algorithm i

Question

I use boost graph to manage graphs and I need to make a maxmin tree.
Now I'm trying to use boost dijkstra's algorithm, but I use a pointer to my class as a vertex property instead of using typedef property<vertex_index_t, int> my_prop, and I can't change it now.
So how can I create predecessor_map and distance_map for my graph?

My code looks like this (and these predecessor and distance maps don't work):

struct LinkStruct {...};
class Node {...};
typedef Node* NodePtr;

typedef adjacency_list<listS, listS, bidirectionalS, NodePtr, LinkStruct> MyGraph;
typedef MyGraph::vertex_descriptor vertex_descriptor;

MyGraph m_graph;
// Fill the graph
{...}

// Dijkstra parameters
std::vector<vertex_descriptor> result_tree(some_struct.size(), MyGraph::null_vertex());
std::vector<uint32_t> result_distances(some_struct.size(), 0);

// Compute maxmin tree
dijkstra_shortest_paths_no_color_map(
    m_graph, // Graph
    root_vertex, // Start vertex
    weight_map( boost::get(&LinkStruct::weight, m_graph) ). // Link property map
    distance_compare( [](uint32_t first, uint32_t second) -> bool {
                                   return first > second; } ). // Compare maxmin path lengths (if maxmin > maxmin)
    distance_combine( [](uint32_t first, uint32_t second) -> uint32_t {
                        return (first > second) ? second : first; } ). // Get min weight of the path
    predecessor_map( make_iterator_property_map(result_tree.begin(),
                                                boost::get(vertex_index, m_graph)) ). // Result tree
    distance_map( make_iterator_property_map(result_distances.begin(),
                                             boost::get(vertex_index, m_graph)) ) // Result distances
);

P.S.
I use pointer in vertex definition because I have many graphs with the same node.
Maybe there is some way around without changing vertex property in the graph definition?

Answer 1

Q.
If I understant it right, I use make_iterator_property_map to create an external property map, but in order to create it I need to pass the vertex ID property map. But I can't access it through boost::get, because vertex property is a pointer. What type should I pass to boost::get(some_type, m_graph) to get such ID map?

You make /any type of propertymap that satisfies the requirement/. You don't need to associate it with the graph. You can simply pass it to the algorithms when you need to (which also makes it clear at which point you promise to have the graph data and the propertymap in synch).

It just occurred to me that in fact you might be able to get a pass on that last issue - the burden of maintaining the property map. That is, if your index can be derived from the pointer value (perhaps retrieved from the struct it points to).

You can use the

• transform_value_property_map
• function_property_map
• perhaps both combined with e.g. compose_property_map

Each of these types has a corresponding deducing factory method make_transform_value_property_map, make_function_property_map etc. so that you don't have to manually spell out the resulting types.

You can search my older answers for examples of what can be done with these.

Samples:

• Dijkstra graph with a table of weights on each edge
• Weight map as function in Boost Graph Dijkstra algorithm
• General point about Property Map map set/get requests into C++ class/structure changes