|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-08-11 17:50:10
Author: asutton
Date: 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
New Revision: 48091
URL: http://svn.boost.org/trac/boost/changeset/48091
Log:
Fixed a bunch of changes while migrating a bunch of files around the
directory structure.
A little bit of cleanup on the search core and BFS/DFS.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directional_edge.hpp
- copied unchanged from r48030, /sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directional_edge.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/dfs.cpp (contents, props changed)
Removed:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directional_edge.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_graph.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_types.hpp | 36 +++++++++++-----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_list.hpp | 1
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_list.hpp | 1
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_set.hpp | 1
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_graph.hpp | 4 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_types.hpp | 32 ++++++++++----------
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_vertex.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_map.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_set.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp | 39 +++++++------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp | 61 ++++++++-------------------------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp | 4 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/bundled_property_map.hpp | 8 ++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp | 4 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/simple_property_map.hpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile | 4 +
sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree | 3 +
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp | 2
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp | 30 +++++++++---------
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp | 6 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp | 6 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp | 6 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp | 8 ++--
sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp | 2
34 files changed, 124 insertions(+), 178 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_graph.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -29,7 +29,7 @@
// the out edge (which could be implemented as an iterator of some kind).
#include <boost/none.hpp>
-#include <boost/graphs/directed_types.hpp>
+#include <boost/graphs/adjacency_list/directed_types.hpp>
template <
typename VertexProps,
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_types.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directed_types.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,32 +3,32 @@
#define DIRECTED_TYPES_HPP
// Vertex stores
-#include <boost/graphs/vertex_vector.hpp>
-#include <boost/graphs/vertex_list.hpp>
-#include <boost/graphs/vertex_set.hpp>
-#include <boost/graphs/vertex_map.hpp>
+#include <boost/graphs/adjacency_list/vertex_vector.hpp>
+#include <boost/graphs/adjacency_list/vertex_list.hpp>
+#include <boost/graphs/adjacency_list/vertex_set.hpp>
+#include <boost/graphs/adjacency_list/vertex_map.hpp>
// Edge stores
-#include <boost/graphs/edge_vector.hpp>
-#include <boost/graphs/edge_list.hpp>
-#include <boost/graphs/edge_set.hpp>
+#include <boost/graphs/adjacency_list/edge_vector.hpp>
+#include <boost/graphs/adjacency_list/edge_list.hpp>
+#include <boost/graphs/adjacency_list/edge_set.hpp>
// Edges store components
-#include <boost/graphs/out_vector.hpp>
-#include <boost/graphs/out_list.hpp>
-#include <boost/graphs/out_set.hpp>
-#include <boost/graphs/out_iterator.hpp>
-#include <boost/graphs/in_vector.hpp>
-#include <boost/graphs/in_list.hpp>
-#include <boost/graphs/in_set.hpp>
-#include <boost/graphs/in_iterator.hpp>
+#include <boost/graphs/adjacency_list/out_vector.hpp>
+#include <boost/graphs/adjacency_list/out_list.hpp>
+#include <boost/graphs/adjacency_list/out_set.hpp>
+#include <boost/graphs/adjacency_list/out_iterator.hpp>
+#include <boost/graphs/adjacency_list/in_vector.hpp>
+#include <boost/graphs/adjacency_list/in_list.hpp>
+#include <boost/graphs/adjacency_list/in_set.hpp>
+#include <boost/graphs/adjacency_list/in_iterator.hpp>
// Vertex and Edge components
-#include <boost/graphs/directed_vertex.hpp>
-#include <boost/graphs/directed_edge.hpp>
+#include <boost/graphs/adjacency_list/directed_vertex.hpp>
+#include <boost/graphs/adjacency_list/directed_edge.hpp>
// Adjacency components
-#include <boost/graphs/adjacency_iterator.hpp>
+#include <boost/graphs/adjacency_list/adjacency_iterator.hpp>
/**
* This class is a metafunction that generates all of the types needed to
Deleted: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directional_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/directional_edge.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
+++ (empty file)
@@ -1,63 +0,0 @@
-
-#ifndef DIRECTIONAL_EDGE_HPP
-#define DIRECTIONAL_EDGE_HPP
-
-// This basically wraps a concept called DirectionalEdge. A DirectionalEdge
-// is one that has directionality being imposed on it. Specializations of
-// these edge should be found with the graph types.
-
-namespace detail
-{
- // By default, we assume that the edge is directed.
- template <typename Edge>
- struct directional_edge_adapter : Edge
- {
- typedef typename Edge::vertex_descriptor Vertex;
-
- inline directional_edge_adapter()
- : Edge()
- { }
-
- inline directional_edge_adapter(Edge e, Vertex)
- : Edge(e)
- { }
-
- inline directional_edge_adapter(Vertex s, Vertex t)
- : Edge(s, t)
- { }
- };
-}
-
-/**
- * The diretional edge type forces directionality onto the given edge structure
- * even when non exists. That this is not the same as a directed edge, which has
- * a distinct direction to it. This simply imposes a direction over the edge
- * with respect to the a source vertex. For directed graphs, this essentially
- * does nothing. For undirected graphs, the source vertex is used to compute
- * the opposite end (target).
- *
- * Directional edges are intended for use in algorithms that walk the graph
- * structure. The act of walking from one vertex to another adds an implicit
- * directionality to the edge. This class embodies that directionality for both
- * directed and undirected graphs.
- *
- * Directional edge descriptors can be used interchangeably with normal edge
- * descriptors.
- */
-template <typename Edge>
-struct directional_edge
- : detail::directional_edge_adapter<Edge>
-{
- typedef Edge edge_descriptor;
- typedef typename Edge::vertex_descriptor vertex_descriptor;
-
- inline directional_edge()
- : detail::directional_edge_adapter<Edge>()
- { }
-
- inline directional_edge(edge_descriptor e, vertex_descriptor v)
- : detail::directional_edge_adapter<Edge>(e, v)
- { }
-};
-
-#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/edge_list.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -4,7 +4,6 @@
#include <list>
-#include <boost/triple.hpp>
#include <boost/descriptors.hpp>
// Forward declarations
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_list.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -5,7 +5,6 @@
#include <list>
#include <algorithm>
-#include <boost/triple.hpp>
#include <boost/descriptors.hpp>
#include <boost/graphs/utility.hpp>
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/out_set.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -5,7 +5,6 @@
#include <map>
#include <memory>
-#include <boost/triple.hpp>
#include <boost/descriptors.hpp>
/**
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_graph.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -5,8 +5,8 @@
#include <boost/assert.hpp>
#include <boost/none.hpp>
-#include <boost/graphs/undirected_types.hpp>
-#include <boost/graphs/adjacency_iterator.hpp>
+#include <boost/graphs/adjacency_list/undirected_types.hpp>
+#include <boost/graphs/adjacency_list/adjacency_iterator.hpp>
template <
typename VertexProps,
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_types.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_types.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,30 +3,30 @@
#define UNDIRECTED_TYPES_HPP
// Vertex stores
-#include <boost/graphs/vertex_vector.hpp>
-#include <boost/graphs/vertex_list.hpp>
-#include <boost/graphs/vertex_set.hpp>
-#include <boost/graphs/vertex_map.hpp>
+#include <boost/graphs/adjacency_list/vertex_vector.hpp>
+#include <boost/graphs/adjacency_list/vertex_list.hpp>
+#include <boost/graphs/adjacency_list/vertex_set.hpp>
+#include <boost/graphs/adjacency_list/vertex_map.hpp>
// Edge stores
-#include <boost/graphs/edge_vector.hpp>
-#include <boost/graphs/edge_list.hpp>
-#include <boost/graphs/edge_set.hpp>
+#include <boost/graphs/adjacency_list/edge_vector.hpp>
+#include <boost/graphs/adjacency_list/edge_list.hpp>
+#include <boost/graphs/adjacency_list/edge_set.hpp>
// Edges store components
-#include <boost/graphs/property_vector.hpp>
-#include <boost/graphs/property_list.hpp>
-#include <boost/graphs/incidence_vector.hpp>
-#include <boost/graphs/incidence_list.hpp>
-#include <boost/graphs/incidence_set.hpp>
-#include <boost/graphs/incidence_iterator.hpp>
+#include <boost/graphs/adjacency_list/property_vector.hpp>
+#include <boost/graphs/adjacency_list/property_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_vector.hpp>
+#include <boost/graphs/adjacency_list/incidence_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_set.hpp>
+#include <boost/graphs/adjacency_list/incidence_iterator.hpp>
// Vertex and Edge components
-#include <boost/graphs/undirected_vertex.hpp>
-#include <boost/graphs/undirected_edge.hpp>
+#include <boost/graphs/adjacency_list/undirected_vertex.hpp>
+#include <boost/graphs/adjacency_list/undirected_edge.hpp>
// Adjacency components
-#include <boost/graphs/adjacency_iterator.hpp>
+#include <boost/graphs/adjacency_list/adjacency_iterator.hpp>
using namespace std;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/undirected_vertex.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -2,7 +2,7 @@
#ifndef UNDIRECTED_VERTEX_HPP
#define UNDIRECTED_VERTEX_HPP
-#include "incidence_iterator.hpp"
+#include <boost/graphs/adjacency_list/incidence_iterator.hpp>
/**
* A vertex, at least for an undirected graph, is simply an repository
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_list.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -6,8 +6,7 @@
#include <boost/none.hpp>
#include <boost/descriptors.hpp>
-
-#include <boost/graphs/vertex_iterator.hpp>
+#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
// Forward declarations
template <typename, typename> class vertices_list;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_map.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -5,8 +5,7 @@
#include <map>
#include <boost/descriptors.hpp>
-
-#include <boost/graphs/vertex_iterator.hpp>
+#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
// Forward declarations
template <typename, typename, typename, typename> class vertices_map;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_set.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -6,9 +6,8 @@
#include <boost/none.hpp>
#include <boost/descriptors.hpp>
-
#include <boost/graphs/utility.hpp>
-#include <boost/graphs/vertex_iterator.hpp>
+#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
// Forward declarations
template <typename, typename, typename> class vertices_set;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/adjacency_list/vertex_vector.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -7,9 +7,8 @@
#include <boost/none.hpp>
#include <boost/descriptors.hpp>
-
#include <boost/graphs/utility.hpp>
-#include <boost/graphs/vertex_iterator.hpp>
+#include <boost/graphs/adjacency_list/vertex_iterator.hpp>
// Forward declarations
template <typename, typename> struct vertices_vector;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/breadth_first.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -9,36 +9,19 @@
#include <boost/graphs/algorithms/utility.hpp>
#include <boost/graphs/algorithms/iterator.hpp>
-struct bfs_visitor
-{
- template <typename Graph, typename Vertex>
- inline void discover_vertex(Graph const& g, Vertex v)
- { }
-
- template <typename Graph, typename Vertex>
- inline void finish_vertex(Graph const& g, Vertex v)
- { }
-
- template <typename Graph, typename Vertex>
- inline void gray_target(Graph const& g, Vertex v)
- { }
+#include <boost/graphs/algorithms/search.hpp>
- template <typename Graph, typename Vertex>
- inline void black_target(Graph const& g, Vertex v)
- { }
+// A BFS search visitor is a basically just a search visitor.
+struct bfs_visitor : search_visitor { };
- template <typename Graph, typename Edge>
- inline void tree_edge(Graph const& g, Edge e)
- { }
- template <typename Graph, typename Edge>
- inline void non_tree_edge(Graph const& g, Edge e)
- { }
-
-};
-
-#include <boost/graphs/algorithms/breadth_first/algorithm.hpp>
-#include <boost/graphs/algorithms/breadth_first/vertex_walk.hpp>
-#include <boost/graphs/algorithms/breadth_first/edge_walk.hpp>
+template <typename Graph, typename Visitor, typename ColorMap = optional_vertex_map<Graph, color>>
+void
+breadth_first_search(Graph const& g, Visitor vis, ColorMap color = ColorMap())
+{
+ std::queue<typename Graph::vertex_descriptor> buf;
+ detail::optional_prop_init(g, color, color_traits<typename ColorMap::value_type>::white());
+ search_graph(g, vis, color, buf);
+}
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/algorithms/depth_first.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -9,55 +9,20 @@
#include <boost/graphs/algorithms/utility.hpp>
#include <boost/graphs/algorithms/iterator.hpp>
-struct dfs_visitor
+#include <boost/graphs/algorithms/search.hpp>
+
+// A DFS search visitor is a just a search visitor.
+struct dfs_visitor : search_visitor { };
+
+
+template <typename Graph, typename Visitor, typename ColorMap = optional_vertex_map<Graph, color>>
+void
+depth_first_search(Graph const& g, Visitor vis, ColorMap color = ColorMap())
{
- // Called when the vertex is popped from the stack. Not all examined
- // vertices are discovered (e.g., a start vertex). Use this event to
- // record the depth-first ordering of vertices.
- template <typename Graph, typename Vertex>
- inline void examine_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when a vertex is encountered for the first time. Discovered
- // vertices are examined unless the algorithm terminates before they are
- // popped from the stack.
- template <typename Graph, typename Vertex>
- inline void discover_vertex(Graph const& g, Vertex v)
- { }
-
- // Called when all of the incident edges of the vertex have been examined.
- template <typename Graph, typename Vertex>
- inline void finish_vertex(Graph const& g, Vertex v)
- { }
-
- // Called for every incident edge of a vertex being examined. Examined
- // edges are classified by the color of their targets at the time of
- // investigation.
- template <typename Graph, typename Edge>
- inline void examine_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge that becomes part of the search tree. A
- // tree edge is one whose source is being examined and whose target is
- // discovered.
- template <typename Graph, typename Edge>
- inline void tree_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge whose target is in the search buffer. Back
- // edges, cross edges, and forward edges are nontree edges.
- template <typename Graph, typename Edge>
- inline void back_edge(Graph const& g, Edge e)
- { }
-
- // Called for each examined edge whose target has already been removed from
- // the search buffer. Technically, this is either a cross edge or a forward
- // edge, but there's no way to easily distinguish them.
- template <typename Graph, typename Edge>
- inline void cross_edge(Graph const& g, Edge e)
- { }
-};
+ std::stack<typename Graph::vertex_descriptor> buf;
+ detail::optional_prop_init(g, color, color_traits<typename ColorMap::value_type>::white());
+ search(g, vis, buf, color);
+}
-#include <boost/graphs/algorithms/depth_first/algorithm.hpp>
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -183,8 +183,8 @@
inline value_type& operator()(key_type const& key)
{ return map(key); }
- inline value_type const& operator()(key_type const& key) const
- { return map(key); }
+ inline void operator()(key_type const& key, value_type const& value) const
+ { return map(key, value); }
inline void swap(property_wrapper& x)
{
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/bundled_property_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/bundled_property_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/bundled_property_map.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -16,11 +16,11 @@
: graph(g), bundle(b)
{ }
- inline value_type& operator()(key_type const& k)
- { return graph[k].*bundle; }
+ inline value_type& operator()(key_type const& key)
+ { return graph[key].*bundle; }
- inline value_type const& operator()(key_type const& k) const
- { return graph[k].*bundle; }
+ inline void operator()(key_type const& key, value_type const& value) const
+ { graph[key].*bundle = value; }
Graph& graph;
Property Bundle::* bundle;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/container_property_map.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -22,8 +22,8 @@
inline value_type& operator()(key_type const& key)
{ return (*container)[key]; }
- inline value_type const& operator()(key_type const& key) const
- { return (*container)[key]; }
+ inline void operator()(key_type const& key, value_type const& value) const
+ { (*container)[key] = value; }
inline void swap(container_property_map& x)
{ std::swap(container, x.container); }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/simple_property_map.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/simple_property_map.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/properties/simple_property_map.hpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -27,8 +27,8 @@
inline value_type& operator()(key_type const& key)
{ return graph[key]; }
- inline value_type const& operator()(key_type const& key) const
- { return graph[key]; }
+ inline void operator()(key_type const& key, value_type const& value) const
+ { graph[key] = value; }
Graph& graph;
};
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/Jamfile 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -17,4 +17,6 @@
exe propmaps : propmaps.cpp ;
-exe bfs : bfs.cpp ;
\ No newline at end of file
+exe bfs : bfs.cpp ;
+exe dfs : dfs.cpp ;
+exe search : search.cpp ;
\ No newline at end of file
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/bfs.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,8 +3,8 @@
#include <fstream>
#include <queue>
-#include <boost/graphs/undirected_graph.hpp>
-#include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
#include <boost/graphs/algorithms/breadth_first.hpp>
#include "typestr.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/data/tree 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -4,3 +4,6 @@
b e 4
c f 5
c g 6
+e h 7
+e i 8
+e j 9
Added: sandbox/SOC/2008/graphs/trunk/libs/graphs/dfs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/dfs.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -0,0 +1,139 @@
+
+#include <iostream>
+#include <fstream>
+#include <queue>
+
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/algorithms/depth_first.hpp>
+
+#include "typestr.hpp"
+#include "read.hpp"
+
+using namespace std;
+
+struct edge_printer : dfs_visitor
+{
+ template <typename Graph, typename Vertex>
+ void discover_vertex(Graph const& g, Vertex v)
+ {
+ // cout << g[v] << " " << endl;
+ }
+
+ template <typename Graph, typename Edge>
+ void tree_edge(Graph const& g, Edge e)
+ {
+ typedef typename Graph::vertex_descriptor Vertex;
+ Vertex u = e.source();
+ Vertex v = e.target();
+ // cout << "(" << g[u] << g[v] << ") ";
+ }
+};
+
+template <typename Graph, typename Walk>
+void iterate(Graph& g, Walk& walk)
+{
+ typedef typename Walk::vertex_descriptor Vertex;
+
+ typedef algorithm_iterator<Walk> Iterator;
+ typedef pair<Iterator, Iterator> Range;
+
+ Range rng(walk.begin(), walk.end());
+ for( ; rng.first != rng.second; ++rng.first) {
+ Vertex u = rng.first->source();
+ Vertex v = rng.first->target();
+ cout << "(" << g[u] << g[v] << ") ";
+ }
+ cout << endl;
+}
+
+template <typename Graph>
+void edge_walk(Graph& g)
+{
+ typedef typename Graph::vertex_descriptor Vertex;
+ typedef typename Graph::edge_descriptor Edge;
+ typedef exterior_vertex_property<Graph, color> ColorProp;
+ typedef exterior_property_map<ColorProp> ColorMap;
+ typedef stack<Vertex> Stack;
+
+ /*
+ {
+ typedef breadth_first_edge_walk<Graph> Walk;
+ cout << "--- default walk ----" << endl;
+ Walk walk(g, *g.begin_vertices());
+ iterate(g, walk);
+ }
+
+ {
+ typedef breadth_first_edge_walk<Graph, ColorMap, Queue> BreadthFirstWalk;
+ cout << "--- custom walk ---" << endl;
+ ColorProp color_prop(g, white_color);
+ ColorMap color(color_prop);
+ BreadthFirstWalk walk(g, *g.begin_vertices(), color);
+ iterate(g, walk);
+ }
+
+
+ {
+ typedef breadth_first_edge_traversal<Graph> Traversal;
+ cout << "--- default traversal ---" << endl;
+ Traversal trav(g);
+ iterate(g, trav);
+ }
+
+ {
+ typedef breadth_first_edge_traversal<Graph, ColorMap, Queue> BreadthFirstTraversal;
+ cout << "--- custom traversal ---" << endl;
+ ColorProp color_prop(g, white_color);
+ ColorMap color(color_prop);
+ BreadthFirstTraversal trav(g, color);
+ iterate(g, trav);
+ }
+ */
+
+ {
+ ColorProp colors(g, white_color);
+ ColorMap color(colors);
+
+ cout << "--- algo visit ---" << endl;
+ depth_first_visit(g, *g.begin_vertices(), edge_printer());
+ cout << endl;
+
+ cout << "--- algo multi visit ---" << endl;
+ // breadth_first_visit(g, g.begin_vertices(), next(g.begin_vertices(), 2), edge_printer());
+ cout << endl;
+
+ cout << "--- algo bfs ---" << endl;
+ // breadth_first_search(g, edge_printer());
+ cout << endl;
+ }
+
+}
+
+int main(int, char* argv[])
+{
+ {
+ typedef undirected_graph<string, string, vertex_set<>, edge_set<>> Graph;
+ Graph g;
+ ifstream f(argv[1]);
+ read(f, g);
+
+ cout << "=== undirected ===" << endl;
+ edge_walk(g);
+ cout << endl;
+ }
+
+ {
+ typedef directed_graph<string, string, vertex_set<>, edge_set<>> Graph;
+ Graph g;
+ ifstream f(argv[1]);
+ read(f, g);
+
+ cout << "=== directed ===" << endl;
+ edge_walk(g);
+ cout << endl;
+ }
+
+
+ return 0;
+}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,7 +3,7 @@
#include <set>
#include <boost/assert.hpp>
-#include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
#include "typestr.hpp"
#include "out_edge_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/edge.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,8 +1,8 @@
#include <iostream>
-#include <boost/graphs/directed_graph.hpp>
-#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
#include "demangle.hpp"
#include "square.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/map.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,7 +1,7 @@
#include <iostream>
-#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/adjeceny_list/undirected_graph.hpp>
using namespace std;
using namespace boost;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/propmaps.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,8 +3,8 @@
#include <iterator>
#include <boost/lexical_cast.hpp>
-#include <boost/graphs/undirected_graph.hpp>
-#include <boost/graphs/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
#include <boost/graphs/properties.hpp>
#include "typestr.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/props.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,8 +3,8 @@
#include <string>
#include <list>
-#include <boost/graphs/directed_graph.hpp>
-#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/directed_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
#include <boost/graphs/properties.hpp>
#include "demangle.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/set.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,7 +1,7 @@
#include <iostream>
-#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
using namespace std;
using namespace boost;
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_es.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,21 +3,21 @@
#include <boost/next_prior.hpp>
-#include <boost/graphs/edge_vector.hpp>
-#include <boost/graphs/edge_list.hpp>
-#include <boost/graphs/edge_set.hpp>
-
-#include <boost/graphs/property_vector.hpp>
-#include <boost/graphs/property_list.hpp>
-#include <boost/graphs/incidence_vector.hpp>
-#include <boost/graphs/incidence_list.hpp>
-#include <boost/graphs/incidence_set.hpp>
-#include <boost/graphs/out_vector.hpp>
-#include <boost/graphs/out_list.hpp>
-#include <boost/graphs/out_set.hpp>
-#include <boost/graphs/in_vector.hpp>
-#include <boost/graphs/in_list.hpp>
-#include <boost/graphs/in_set.hpp>
+#include <boost/graphs/adjacency_list/edge_vector.hpp>
+#include <boost/graphs/adjacency_list/edge_list.hpp>
+#include <boost/graphs/adjacency_list/edge_set.hpp>
+
+#include <boost/graphs/adjacency_list/property_vector.hpp>
+#include <boost/graphs/adjacency_list/property_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_vector.hpp>
+#include <boost/graphs/adjacency_list/incidence_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_set.hpp>
+#include <boost/graphs/adjacency_list/out_vector.hpp>
+#include <boost/graphs/adjacency_list/out_list.hpp>
+#include <boost/graphs/adjacency_list/out_set.hpp>
+#include <boost/graphs/adjacency_list/in_vector.hpp>
+#include <boost/graphs/adjacency_list/in_list.hpp>
+#include <boost/graphs/adjacency_list/in_set.hpp>
#include "typestr.hpp"
#include "properties_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_incs.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,9 +1,9 @@
#include <iostream>
-#include <boost/graphs/incidence_vector.hpp>
-#include <boost/graphs/incidence_list.hpp>
-#include <boost/graphs/incidence_set.hpp>
+#include <boost/graphs/adjacency_list/incidence_vector.hpp>
+#include <boost/graphs/adjacency_list/incidence_list.hpp>
+#include <boost/graphs/adjacency_list/incidence_set.hpp>
#include "typestr.hpp"
#include "incidence_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_ins.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,9 +1,9 @@
#include <iostream>
-#include <boost/graphs/in_vector.hpp>
-#include <boost/graphs/in_list.hpp>
-#include <boost/graphs/in_set.hpp>
+#include <boost/graphs/adjacency_list/in_vector.hpp>
+#include <boost/graphs/adjacency_list/in_list.hpp>
+#include <boost/graphs/adjacency_list/in_set.hpp>
#include "typestr.hpp"
#include "in_edge_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_outs.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,9 +1,9 @@
#include <iostream>
-#include <boost/graphs/out_vector.hpp>
-#include <boost/graphs/out_list.hpp>
-#include <boost/graphs/out_set.hpp>
+#include <boost/graphs/adjacency_list/out_vector.hpp>
+#include <boost/graphs/adjacency_list/out_list.hpp>
+#include <boost/graphs/adjacency_list/out_set.hpp>
#include "typestr.hpp"
#include "out_edge_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_props.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,8 +1,8 @@
#include <iostream>
-#include <boost/graphs/property_vector.hpp>
-#include <boost/graphs/property_list.hpp>
+#include <boost/graphs/adjacency_list/property_vector.hpp>
+#include <boost/graphs/adjacency_list/property_list.hpp>
#include "typestr.hpp"
#include "properties_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test_verts.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -1,10 +1,10 @@
#include <iostream>
-#include <boost/graphs/vertex_vector.hpp>
-#include <boost/graphs/vertex_list.hpp>
-#include <boost/graphs/vertex_set.hpp>
-#include <boost/graphs/vertex_map.hpp>
+#include <boost/graphs/adjacency_list/vertex_vector.hpp>
+#include <boost/graphs/adjacency_list/vertex_list.hpp>
+#include <boost/graphs/adjacency_list/vertex_set.hpp>
+#include <boost/graphs/adjacency_list/vertex_map.hpp>
#include "typestr.hpp"
#include "vertices_traits.hpp"
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/un.cpp 2008-08-11 17:50:07 EDT (Mon, 11 Aug 2008)
@@ -3,7 +3,7 @@
#include <boost/assert.hpp>
#include <boost/utility.hpp>
-#include <boost/graphs/undirected_graph.hpp>
+#include <boost/graphs/adjacency_list/undirected_graph.hpp>
#include "typestr.hpp"
#include "incidence_traits.hpp"
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk