Adding upstream version 14.2.21.upstream/14.2.21upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 189 insertions, 0 deletions

diff --git a/src/boost/libs/graph/example/file_dependencies.cpp b/src/boost/libs/graph/example/file_dependencies.cpp
new file mode 100644
index 00000000..9bce7334
--- /dev/null
+++ b/src/boost/libs/graph/example/file_dependencies.cpp
@@ -0,0 +1,189 @@
+//=======================================================================
+// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
+// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
+//
+// 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)
+//=======================================================================
+
+// Some small modifications are done by Alexander Holler
+
+/*
+
+  Paul Moore's request:
+
+  As an example of a practical problem which is not restricted to graph
+  "experts", consider file dependencies. It's basically graph construction,
+  plus topological sort, but it might make a nice "tutorial" example. Build a
+  dependency graph of files, then use the algorithms to do things like
+
+  1. Produce a full recompilation order (topological sort, by modified date)
+  2. Produce a "parallel" recompilation order (same as above, but group files
+  which can be built in parallel)
+  3. Change analysis (if I change file x, which others need recompiling)
+  4. Dependency changes (if I add a dependency between file x and file y, what
+  are the effects)
+
+*/
+
+#include <boost/config.hpp> // put this first to suppress some VC++ warnings
+
+#include <iostream>
+#include <iterator>
+#include <algorithm>
+#include <time.h>
+
+#include <boost/utility.hpp>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/topological_sort.hpp>
+#include <boost/graph/depth_first_search.hpp>
+#include <boost/graph/dijkstra_shortest_paths.hpp>
+#include <boost/graph/visitors.hpp>
+
+using namespace std;
+using namespace boost;
+
+enum files_e { dax_h, yow_h, boz_h, zow_h, foo_cpp, 
+               foo_o, bar_cpp, bar_o, libfoobar_a,
+               zig_cpp, zig_o, zag_cpp, zag_o, 
+                 libzigzag_a, killerapp, N };
+const char* name[] = { "dax.h", "yow.h", "boz.h", "zow.h", "foo.cpp",
+                       "foo.o", "bar.cpp", "bar.o", "libfoobar.a",
+                       "zig.cpp", "zig.o", "zag.cpp", "zag.o",
+                       "libzigzag.a", "killerapp" };
+
+
+struct print_visitor : public bfs_visitor<> {
+  template <class Vertex, class Graph>
+  void discover_vertex(Vertex v, Graph&) {
+    cout << name[v] << " ";
+  }
+};
+
+
+struct cycle_detector : public dfs_visitor<>
+{
+  cycle_detector(bool& has_cycle) 
+    : m_has_cycle(has_cycle) { }
+
+  template <class Edge, class Graph>
+  void back_edge(Edge, Graph&) { m_has_cycle = true; }
+protected:
+  bool& m_has_cycle;
+};
+
+
+
+
+int main(int,char*[])
+{
+
+  typedef pair<int,int> Edge;
+  Edge used_by[] = {
+    Edge(dax_h, foo_cpp), Edge(dax_h, bar_cpp), Edge(dax_h, yow_h),
+    Edge(yow_h, bar_cpp), Edge(yow_h, zag_cpp),
+    Edge(boz_h, bar_cpp), Edge(boz_h, zig_cpp), Edge(boz_h, zag_cpp),
+    Edge(zow_h, foo_cpp), 
+    Edge(foo_cpp, foo_o),
+    Edge(foo_o, libfoobar_a),
+    Edge(bar_cpp, bar_o),
+    Edge(bar_o, libfoobar_a),
+    Edge(libfoobar_a, libzigzag_a),
+    Edge(zig_cpp, zig_o),
+    Edge(zig_o, libzigzag_a),
+    Edge(zag_cpp, zag_o),
+    Edge(zag_o, libzigzag_a),
+    Edge(libzigzag_a, killerapp)
+  };
+  const std::size_t nedges = sizeof(used_by)/sizeof(Edge);
+
+  typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
+#if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
+  // VC++ can't handle the iterator constructor
+  Graph g(N);
+  for (std::size_t j = 0; j < nedges; ++j) {
+    graph_traits<Graph>::edge_descriptor e; bool inserted;
+    boost::tie(e, inserted) = add_edge(used_by[j].first, used_by[j].second, g);
+  }
+#else
+  Graph g(used_by, used_by + nedges, N);
+#endif
+  typedef graph_traits<Graph>::vertex_descriptor Vertex;
+
+  // Determine ordering for a full recompilation
+  // and the order with files that can be compiled in parallel
+  {
+    typedef list<Vertex> MakeOrder;
+    MakeOrder::iterator i;
+    MakeOrder make_order;
+
+    topological_sort(g, std::front_inserter(make_order));
+    cout << "make ordering: ";
+    for (i = make_order.begin();
+         i != make_order.end(); ++i) 
+      cout << name[*i] << " ";
+  
+    cout << endl << endl;
+
+    // Parallel compilation ordering
+    std::vector<int> time(N, 0);
+    for (i = make_order.begin(); i != make_order.end(); ++i) {    
+      // Walk through the in_edges an calculate the maximum time.
+      if (in_degree (*i, g) > 0) {
+        Graph::in_edge_iterator j, j_end;
+        int maxdist=0;
+        // Through the order from topological sort, we are sure that every 
+        // time we are using here is already initialized.
+        for (boost::tie(j, j_end) = in_edges(*i, g); j != j_end; ++j)
+          maxdist=(std::max)(time[source(*j, g)], maxdist);
+        time[*i]=maxdist+1;
+      }
+    }
+
+    cout << "parallel make ordering, " << endl
+         << "vertices with same group number can be made in parallel" << endl;
+    {
+      graph_traits<Graph>::vertex_iterator i, iend;
+      for (boost::tie(i,iend) = vertices(g); i != iend; ++i)
+        cout << "time_slot[" << name[*i] << "] = " << time[*i] << endl;
+    }
+
+  }
+  cout << endl;
+
+  // if I change yow.h what files need to be re-made?
+  {
+    cout << "A change to yow.h will cause what to be re-made?" << endl;
+    print_visitor vis;
+    breadth_first_search(g, vertex(yow_h, g), visitor(vis));
+    cout << endl;
+  }
+  cout << endl;
+
+  // are there any cycles in the graph?
+  {
+    bool has_cycle = false;
+    cycle_detector vis(has_cycle);
+    depth_first_search(g, visitor(vis));
+    cout << "The graph has a cycle? " << has_cycle << endl;
+  }
+  cout << endl;
+
+  // add a dependency going from bar.cpp to dax.h
+  {
+    cout << "adding edge bar_cpp -> dax_h" << endl;
+    add_edge(bar_cpp, dax_h, g);
+  }
+  cout << endl;
+
+  // are there any cycles in the graph?
+  {
+    bool has_cycle = false;
+    cycle_detector vis(has_cycle);
+    depth_first_search(g, visitor(vis));
+    cout << "The graph has a cycle now? " << has_cycle << endl;
+  }
+
+  return 0;
+}