CODEWITHSUNDEEP
c++boostgraphshortest-pathdijkstra
Jacks
Jacks

Reputation: 67

Boost: Create Graph from shortest Path

currently i'm working with boost graph library. My Graph consist of custom Vertex and Edge Properties:

typedef boost::labeled_graph<boost::adjacency_list< boost::listS, boost::vecS, boost::directedS, Vertex, Edge>, int> Graph; Graph g;

I need the functionality of calculating the shortest Path (Dijkstra), thereby the user has to select one or multiple start and end nodes. After selecting the Nodes and calculating the shortest path between every start and end node, a new graph should be created. In the end, the new graph should contain all vertices/edges which are lying on every shortest path.

My idea was:

1: I do a backtracking of the calculated shortest Path of type

   typedef std::vector< VertexDescriptor> Path;

2: I check if the vertex is already contained in the new Graph. (I dont know how to handle that one), if so i copy the vertex into the new Graph.

3: I check if the edge is already contained in the new Graph, if so i copy the edge into the new Graph. 

Graph graphPaths;
Path::reverse_iterator rit;
VertexDescriptor lastNode = *path.rbegin();

for (rit = path.rbegin(); rit != path.rend(); ++rit) {
   //   Vertex v =
        // check if vertices already exist in new GraphPath
    if (graphPaths[indexMap[*rit]] == NULL) {
        Vertex v = g[indexMap[*rit]];
        VertexDescriptor vd = boost::add_vertex(indexMap[*rit], graphPaths);
        graphPaths[indexMap[*rit]] = v;
    }

    // check if edge is already included in new Graph
        if (!boost::edge(lastNode, *rit, graphPaths).second) {

        Graph::edge_descriptor ep = boost::edge(lastNode, *rit, g).first;
        boost::add_edge_by_label(indexMap[lastNode], indexMap[*rit], g[ep],
            graphPaths);
        }

    }
    lastNode = *rit;
}

How can i check the presence of a Vertex in a Graph. Do you have other ideas to improve the process or solve the issue.

Thanks Michael

Upvotes: 1

Views: 159

Answers (1)

sehe
sehe

Reputation: 392833

I'd consider doing a filtered_graph adaptor on the original graph, filtering out all vertices/edges not visited in the interesting paths.

Then it's a a simple copy_graph to create the new graph.

If you change the graph type to a labeled_graph of the filtered_graph then you don't even need the copy, depending on your performance trade-offs.

Upvotes: 1

Related Questions