1 files changed, 83 insertions, 0 deletions
diff --git a/src/boost/libs/graph/example/johnson-eg.cpp b/src/boost/libs/graph/example/johnson-eg.cpp
new file mode 100644
index 000000000..90d22b280
--- /dev/null
+++ b/src/boost/libs/graph/example/johnson-eg.cpp
@@ -0,0 +1,83 @@
+//=======================================================================
+// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
+//
+// Distributed under the Boost Software License, Version 1.0. (See
+// accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//=======================================================================
+#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 main()
+{
+    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 = 6;
+    typedef std::pair< int, int > Edge;
+    Edge edge_array[] = { Edge(0, 1), Edge(0, 2), Edge(0, 3), Edge(0, 4),
+        Edge(0, 5), Edge(1, 2), Edge(1, 5), Edge(1, 3), Edge(2, 4), Edge(2, 5),
+        Edge(3, 2), Edge(4, 3), Edge(4, 1), Edge(5, 4) };
+    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[] = { 0, 0, 0, 0, 0, 3, -4, 8, 1, 7, 4, -5, 2, 6 };
+    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 (boost::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;
+}