Ticket #11585: johnsohn_all_pairs.cpp

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

int test() {

                using namespace boost;
                typedef adjacency_list<vecS, vecS, directedS, no_property,
                        property< edge_weight_t, int, property< edge_weight2_t, int > > > Graph;
                const int V = 3;
                typedef std::pair < int, int >Edge;
                Edge edge_array[] =
                { Edge(0, 1), Edge(1, 0), Edge(1, 2), Edge(2, 1), Edge(0, 2),
                        Edge(2, 0)
                };
                const std::size_t E = sizeof(edge_array) / sizeof(Edge);
#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
                // VC++ can't handle the iterator constructor
                Graph g(V);
                for (std::size_t j = 0; j < E; ++j)
                        add_edge(edge_array[j].first, edge_array[j].second, g);
#else
                Graph g(edge_array, edge_array + E, V);
#endif

                property_map < Graph, edge_weight_t >::type w = get(edge_weight, g);
                int weights[] = { 96, 90, 99, 97, 98, 100 };
                int *wp = weights;

                graph_traits < Graph >::edge_iterator e, e_end;
                for (boost::tie(e, e_end) = edges(g); e != e_end; ++e)
                        w[*e] = *wp++;

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

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

                std::ofstream fout("figs/johnson-eg.dot");
                fout << "digraph A {\n"
                        << "  rankdir=LR\n"
                        << "size=\"5,3\"\n"
                        << "ratio=\"fill\"\n"
                        << "edge[style=\"bold\"]\n" << "node[shape=\"circle\"]\n";

                graph_traits < Graph >::edge_iterator ei, ei_end;
                for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
                        fout << source(*ei, g) << " -> " << target(*ei, g)
                        << "[label=" << get(edge_weight, g)[*ei] << "]\n";

                fout << "}\n";
                return 0;
        }