[Boost-users] graph all pair shortest path problem

Subject: [Boost-users] graph all pair shortest path problem
From: Nicolas Heine (nheine_at_[hidden])
Date: 2008-09-05 10:07:55

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