Longest Path in Boost Graph
- by TheTSPSolver
Hi,
Sorry if this is a very basic questions for some of you but I'm new to C++ (let alone Boost Graph Library) and couldn't figure out this problem. So far I've been able to formulate/gather code to create a graph using the code below.
Now I'm trying to figure out the code to find the longest path in this graph.
Can someone please help with what would the code be? I was having trouble trying to figure out if/how to traverse through each node and/or edge when trying to find the path?
I have to try to return all the nodes and edges in the longest path.
Any help will be greatly appreciated.
P.S. does anyone know if C++ has organized documentation like Javadoc??
#include <boost/graph/dag_shortest_paths.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <windows.h>
#include <iostream>
int main()
{
using namespace boost;
typedef adjacency_list<vecS, vecS, directedS, property<vertex_distance_t, double>, property<edge_weight_t, double> > graph_t;
graph_t g(6);
enum verts { stationA, stationB, stationC, stationD, stationE, stationF };
char name[] = "rstuvx";
add_edge(stationA, stationB, 5000.23, g);
add_edge(stationA, stationC, 3001, g);
add_edge(stationA, stationD, 2098.67, g);
add_edge(stationA, stationE, 3298.84, g);
add_edge(stationB, stationF, 2145, g);
add_edge(stationC, stationF, 4290, g);
add_edge(stationD, stationF, 2672.78, g);
add_edge(stationE, stationF, 11143.876, g);
add_edge(stationA, stationF, 1, g);
//Display all the vertices
typedef property_map<graph_t, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
std::cout << "vertices(g) = ";
typedef graph_traits<graph_t>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first)
std::cout << index[*vp.first] << " ";
std::cout << std::endl;
// ...
// Display all the edges
// ...
std::cout << "edges(g) = " << std::endl;
graph_traits<graph_t>::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
std::cout << "(" << index[source(*ei, g)] << "," << index[target(*ei, g)] << ") \n";
std::cout << std::endl;
// ...
