[Boost-commit] svn:boost r7003

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