From: asutton_at_[hidden]
Date: 2007-06-12 12:32:45
Author: asutton
Date: 2007-06-12 12:32:45 EDT (Tue, 12 Jun 2007)
New Revision: 7003
URL: http://svn.boost.org/trac/boost/changeset/7003
Log:
Added a program for detecting cycles in Makefiles.
Made build_order record time slots for parallel builds.
Added:
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp
Text files modified:
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/Jamfile.v2 | 5 +++++
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp | 18 ++++++++++++++----
sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files | 24 ++++++++++--------------
3 files changed, 29 insertions(+), 18 deletions(-)
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/Jamfile.v2
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/makefile/Jamfile.v2 (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/Jamfile.v2 2007-06-12 12:32:45 EDT (Tue, 12 Jun 2007)
@@ -1,4 +1,9 @@
exe build_order
: build_order.cpp
: <include>../../../../
+ ;
+
+exe cycle
+ : cycle.cpp
+ : <include>../../../../
;
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/build_order.cpp 2007-06-12 12:32:45 EDT (Tue, 12 Jun 2007)
@@ -11,6 +11,7 @@
// boost includes
#include <boost/tokenizer.hpp>
+#include <boost/algorithm/string.hpp>
#include <boost/graph/directed_graph.hpp>
#include <boost/graph/topological_sort.hpp>
@@ -95,8 +96,8 @@
if(index == string::npos) {
continue;
}
- string target(line, 0, index);
- string deps(line, index + 1);
+ string target = trim_copy(line.substr(0, index));
+ string deps = trim_copy(line.substr(index + 1));
// add the target to the build graph
Vertex u = add_target(g, targets, target);
@@ -127,9 +128,18 @@
vertex_index_map(indices)
);
- // write out the build order...
+ // write out the build order and compute time slots at the
+ // same time...
+ vector<int> time(num_vertices(g), 0);
BuildOrder::iterator i = order.begin(), j = order.end();
for( ; i != j; ++i) {
- cout << g[*i].name << "\n";
+ int slot = -1;
+ Graph::in_edge_iterator j, k;
+ for(tie(j, k) = in_edges(*i, g); j != k; ++j) {
+ slot = std::max(time[g[source(*j, g)].index], slot);
+ }
+ time[g[*i].index] = slot + 1;
+
+ cout << g[*i].name << " [" << time[g[*i].index] << "]\n";
}
}
Added: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/cycle.cpp 2007-06-12 12:32:45 EDT (Tue, 12 Jun 2007)
@@ -0,0 +1,149 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+// std includes
+#include <iostream>
+#include <string>
+#include <map>
+
+// boost includes
+#include <boost/tokenizer.hpp>
+#include <boost/algorithm/string.hpp>
+#include <boost/graph/directed_graph.hpp>
+#include <boost/graph/depth_first_search.hpp>
+
+using namespace std;
+using namespace boost;
+
+struct Target
+{
+ int index;
+ string name;
+};
+
+typedef directed_graph<Target> Graph;
+typedef Graph::vertex_descriptor Vertex;
+typedef Graph::edge_descriptor Edge;
+typedef property_map<Graph::type, int Target::*>::type TargetIndexMap;
+typedef property_map<Graph::type, string Target::*>::type TargetNameMap;
+
+typedef map<string, Vertex> TargetMap;
+
+struct CycleDetector : public dfs_visitor<>
+{
+ CycleDetector(bool& c)
+ : has_cycle(c)
+ {}
+
+ template <class Edge, class Graph>
+ void back_edge(Edge, Graph&)
+ {
+ has_cycle = true;
+ }
+
+ bool& has_cycle;
+};
+
+CycleDetector detect_cycles(bool& c)
+{
+ return CycleDetector(c);
+}
+
+Vertex
+add_target(Graph& g, TargetMap& targets, const string& name)
+{
+ // try inserting the actors name into the actors map
+ Vertex v;
+ TargetMap::iterator it;
+ bool inserted;
+ tie(it, inserted) = targets.insert(make_pair(name, Vertex()));
+ if(inserted) {
+ // create a vertex for the name
+ v = add_vertex(g);
+
+ // associate the vertex with the name
+ it->second = v;
+
+ // configure the vertex properties
+ g[v].index = num_vertices(g) - 1;
+ g[v].name = name;
+ }
+ else {
+ // otherwise, the name is already in the map, so just
+ // return the iterator associated with it
+ v = it->second;
+ }
+
+ return v;
+}
+
+// Look very carefully at the add_edge() call in this function and
+// you'll notice that it switches the ordering of the vertices in
+// the edge that's being created. Unfortunately, the problem requires
+// that we model the direction of edges as "used-by", although our
+// input format is more of a "dependency" listing. This isn't really
+// a problem as long as we recognize the difference.
+Edge
+add_dependency(Graph &g, Vertex u, Vertex v)
+{
+ Edge e;
+ bool inserted;
+ tie(e, inserted) = add_edge(v, u, g);
+ return e;
+}
+
+int
+main(int argc, char* argv[])
+{
+ typedef list<Vertex> BuildOrder;
+ typedef boost::char_separator<char> separator;
+ typedef boost::tokenizer<separator> tokenizer;
+
+ Graph g;
+ TargetMap targets;
+
+ for(string line; getline(cin, line); ) {
+ // skip comment and blank lines
+ if(line[0] == '#' || line.empty()) {
+ continue;
+ }
+
+ // split the string on the dependency
+ size_t index = line.find_first_of(':');
+ if(index == string::npos) {
+ continue;
+ }
+ string target = trim_copy(line.substr(0, index));
+ string deps = trim_copy(line.substr(index + 1));
+
+ // add the target to the build graph
+ Vertex u = add_target(g, targets, target);
+
+ // tokenize the dependencies
+ separator sep(" \t");
+ tokenizer tok(deps, sep);
+ tokenizer::iterator i = tok.begin(), j = tok.end();
+ for( ; i != j; ++i) {
+ string dep = *i;
+
+ // add this dependency as a target
+ Vertex v = add_target(g, targets, dep);
+
+ // add the edge
+ add_dependency(g, u, v);
+ }
+ }
+
+ // we need to create a vertex index map for the graph before
+ // we can generate the build order
+ TargetIndexMap indices = get(&Target::index, g);
+
+ bool cycle = false;
+ depth_first_search(g,
+ vertex_index_map(indices).
+ visitor(detect_cycles(cycle)));
+ cout << "has cycle: " << cycle << "\n";
+}
Modified: sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files (original)
+++ sandbox/SOC/2007/graphs/libs/graph/examples/makefile/files 2007-06-12 12:32:45 EDT (Tue, 12 Jun 2007)
@@ -5,18 +5,14 @@
# Example:
# <target>: <dep1> <dep2>
-killerapp: libzigzag.a
-libzigzag.a: libfoobar.a zig.o zag.o
-libfoobar.a: foo.o bar.o
-foo.o: foo.cpp
-foo.cpp: zow.h dax.h
-bar.o: bar.cpp
-bar.cpp: boz.h yow.h dax.h
-yow.h: dax.h
-zig.o: zig.cpp
-zig.cpp: boz.h
-zag.o: zag.cpp
-zag.cpp: boz.h yow.h
+undirected_graph.hpp : adjacency_list.hpp
+directed_graph.hpp : adjacency_list.hpp
+movies.hpp : undirected_graph.hpp
+movies.cpp : movies.hpp tokenizer.hpp
+kevin_bacon.cpp : movies.hpp visitors.hpp breadth_first_search.hpp
+kevin_bacon.exe : movies.cpp kevin_bacon.cpp
+build_order.cpp : directed_graph.hpp topological_sort.hpp
+build_order.exe : build_order.cpp
-# uncomment this line to add a cycle
-# dax.h: bar.cpp
+movies.cpp : kevin_bacon.cpp
+kevin_bacon.cpp : movies.cpp
\ No newline at end of file