graph all pair shortest path problem

5 Sep 2008

      Hi *,

I have a question about the All Pair Shortest Path (Johnson) algorithm.

Here is my code:

#include <boost/config.hpp>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <boost/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>

int main() {
	using namespace boost;

	typedef property<vertex_index_t, int, property<vertex_name_t,  
std::string> >
			VertexProperty;

	typedef property<edge_weight_t, int, property<edge_weight2_t, int> >
				EdgeProperty;

	typedef property<graph_name_t, std::string> GraphProperty;
	//adjacency_list<OutEdgeList, VertexList, Directed,
	//             VertexProperties, EdgeProperties,
	//           GraphProperties, EdgeList>
	typedef adjacency_list<listS, listS, undirectedS, VertexProperty,
			EdgeProperty, GraphProperty> Graph;

	boost::graph_traits<Graph>::vertex_descriptor u, v, w, first, second;

	int N = 10;
	Graph g;

	first = add_vertex(g);
	put(vertex_index, g, first, num_vertices(g));

	second = add_vertex(g);
	put(vertex_index, g, second, num_vertices(g));

	add_edge(first, second, g);

	u = first;
	v = second;
	for (int i = 2; i < N; i++) {
		w = add_vertex(g);
		put(vertex_index, g, w, i + 1);
		add_edge(u, w, g);
		add_edge(v, w, g);
		u = v;
		v = w;
	}
	add_edge(u, first, g);
	add_edge(v, second, g), add_edge(v, first, g);
	std::cout << "Finished to build Graph" << std::endl;

	//set weights to 1
	typedef graph_traits<Graph>::edge_iterator EdgeIterator;
	EdgeIterator ei, edge_end;
	for ( boost::tie(ei, edge_end) = edges(g); ei != edge_end; ++ei){
		put(edge_weight, g, *ei, 1);
	}

	std::vector<int> d(N, (std::numeric_limits<int>::max)());
	int D[N][N];
	johnson_all_pairs_shortest_paths(g, D, distance_map(&d[0]));

	std::cout << "     ";
	for (int k = 0; k < N; ++k)
		std::cout << std::setw(5) << k;
	std::cout << std::endl;
	for (int i = 0; i < N; ++i) {
		std::cout << i << " -> ";
		for (int j = 0; j < N; ++j) {
			if (D[i][j] > 20 || D[i][j] < -20)
				std::cout << std::setw(5) << "inf";
			else
				std::cout << std::setw(5) << D[i][j];
		}
		std::cout << std::endl;
	}

	return 0;
}

When I compile  I get the error:
../src/BGLTest.cpp: In function 'int main()':
../src/BGLTest.cpp:73: error: no matching function for call to  
'johnson_all_pairs_shortest_paths(main()::Graph&, int [(((long  
unsigned int)(((int)N) - 1)) + 1u)][(((long unsigned int)(((int)N) -  
1)) + 1u)], boost::bgl_named_params<int*, boost::vertex_distance_t,  
boost::no_property>)'

What does that mean? I want to use the Johnson algorithm with a listS  
= Vertexlist and listS = Egelist.   With listS, vecS as in your  
example it works fine. What can I do?

Thanks in advance,
Nico

Nicolas Heine

Steven Watanabe

tags

participants (2)