|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-05-29 08:57:12
Author: asutton
Date: 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
New Revision: 45902
URL: http://svn.boost.org/trac/boost/changeset/45902
Log:
Added initial test dir for new graph code.
Added:
sandbox/SOC/2008/graphs/libs/graphs/
sandbox/SOC/2008/graphs/libs/graphs/Jamfile (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/Jamroot (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/color.hpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/concepts.hpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/demangle.hpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/doc/
sandbox/SOC/2008/graphs/libs/graphs/doc/concepts.dot (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/hash.cpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/ordered_pair.cpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/print_vertices.hpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/unordered_pair.cpp (contents, props changed)
Added: sandbox/SOC/2008/graphs/libs/graphs/Jamfile
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/Jamfile 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,5 @@
+
+exe ordered_pair : ordered_pair.cpp : <include>../../ ;
+exe unordered_pair : unordered_pair.cpp : <include>../../ ;
+exe adjacency_list : adjacency_list.cpp : <include>../../ <include>/usr/local/include ;
+exe bfs : bfs.cpp : <include>../../ <include>/usr/local/include ;
\ No newline at end of file
Added: sandbox/SOC/2008/graphs/libs/graphs/Jamroot
==============================================================================
Added: sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,178 @@
+
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include <typeinfo>
+#include <cxxabi.h>
+
+#include <boost/graphs/adjacency_list.hpp>
+#include "print_vertices.hpp"
+
+using namespace std;
+using namespace boost::graphs;
+using namespace boost::graphs::adj_list;
+
+string demangle(string const& name)
+{
+ return string(abi::__cxa_demangle(name.c_str(), 0, 0, 0));
+}
+
+static void test_graph();
+static void test_multigraph();
+
+static void vector_simple_graph();
+static void list_simple_graph();
+static void set_simple_graph();
+static void map_simple_graph();
+
+int
+main(int argc, char *argv[])
+{
+ test_graph();
+ test_multigraph();
+
+ cout << "*** vector simple graph ***" << endl;
+ vector_simple_graph();
+
+ cout << "*** list simple graph ***" << endl;
+ list_simple_graph();
+
+ cout << "*** set simple graph ***" << endl;
+ set_simple_graph();
+
+ cout << "*** map simple graph ***" << endl;
+ map_simple_graph();
+
+ return 0;
+}
+
+void
+test_graph()
+{
+ graph<> g;
+}
+
+void
+test_multigraph()
+{
+ multigraph<> g;
+}
+
+void
+vector_simple_graph()
+{
+ static string V[] = {
+ "Houston", "Dallas", "Fort Worth", "Austin", "San Antonio", "El Paso",
+ "Austin", "Dallas"
+ };
+ int N = sizeof(V) / sizeof(string);
+
+ typedef adjacency_list<
+ undirected,
+ string,
+ none,
+ vertex_vector,
+ edge_vector
+ > Graph;
+ Graph g;
+
+ for(int i = 0; i < N; ++i) {
+ g.add_vertex(V[i]);
+ }
+
+ print_vertices(g);
+}
+
+void
+list_simple_graph()
+{
+ static string V[] = {
+ "Houston", "Dallas", "Fort Worth", "Austin", "San Antonio", "El Paso",
+ "Austin", "Dallas"
+ };
+ int N = sizeof(V) / sizeof(string);
+
+ typedef adjacency_list<
+ undirected,
+ string,
+ none,
+ vertex_list
+ > Graph;
+ Graph g;
+
+ for(int i = 0; i < N; ++i) {
+ g.add_vertex(V[i]);
+ }
+
+ print_vertices(g);
+}
+
+void
+set_simple_graph()
+{
+ static string V[] = {
+ "Houston", "Dallas", "Fort Worth", "Austin", "San Antonio", "El Paso",
+ "Austin", "Dallas"
+ };
+ int N = sizeof(V) / sizeof(string);
+
+ typedef adjacency_list<
+ undirected,
+ string,
+ none,
+ vertex_set
+ > Graph;
+ Graph g;
+
+ for(int i = 0; i < N; ++i) {
+ g.add_vertex(V[i]);
+ }
+
+ print_vertices(g);
+}
+
+void
+map_simple_graph()
+{
+ static string V[] = {
+ "Houston", "Dallas", "Fort Worth", "Austin", "San Antonio", "El Paso",
+ "Austin", "Dallas"
+ };
+ int N = sizeof(V) / sizeof(string);
+
+ typedef adjacency_list<
+ undirected,
+ int,
+ none,
+ string_to_vertex_map,
+ edge_list,
+ vertex_edge_list,
+ no_loops_policy
+ > Graph;
+ Graph g;
+
+ for(int i = 0; i < N; ++i) {
+ g.add_vertex(V[i], i);
+ }
+
+ Graph::vertex_descriptor houston = g.find_vertex("Houston");
+ Graph::vertex_descriptor dallas = g.find_vertex("Dallas");
+ Graph::vertex_descriptor ftworth = g.find_vertex("Fort Worth");
+
+ std::cout << "Houston: " << houston.get() << endl;
+ std::cout << "Dallas: " << dallas.get() << endl;
+ std::cout << "Fort Worth: " << ftworth.get() << endl;
+
+ Graph::edge_descriptor hd = g.add_edge(houston, dallas);
+ Graph::edge_descriptor fw = g.add_edge(ftworth, houston);
+
+ cout << "edges: " << g.num_edges() << endl;
+ g.remove_edge(hd);
+ g.remove_edge(houston, ftworth);
+ cout << "edges: " << g.num_edges() << endl;
+
+ // print_vertices(g);
+
+}
+
Added: sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,134 @@
+
+#include <iostream>
+#include <string>
+#include <vector>
+
+#include <boost/utility.hpp>
+
+#include <boost/graphs/adjacency_list.hpp>
+#include <boost/graphs/breadth_first_search.hpp>
+
+#include <boost/date_time.hpp>
+
+#include "demangle.hpp"
+
+using namespace std;
+using namespace boost::graphs;
+using namespace boost::graphs::adj_list;
+using namespace boost::posix_time;
+
+struct VertexProps
+{
+ string name;
+ int age;
+};
+
+struct EdgeProps
+{
+ string relation;
+ double weight;
+};
+
+// Notes on timing...
+// Obviously (and somewhat unfortunately), hashed property containers will
+// never perform as efficiently as a vector - that's just the way of things.
+// However, there's a serious tradeoff between flexibility (which is what
+// you're getting with lists, sets, maps) and speed (which you get with vectors
+// at the cost of half-mutability).
+
+static const size_t N = 1000;
+
+void test_1();
+void test_2();
+void test_3();
+
+int main()
+{
+ test_1();
+ cout << endl << endl;
+ test_2();
+ cout << endl << endl;
+ test_3();
+
+ return 0;
+}
+
+void test_1()
+{
+ typedef graph<int, double, vertex_set> Graph;
+ typedef exterior_vertex_property<Graph, color>::container_type ColorContainer;
+ typedef exterior_vertex_property<Graph, color>::map_type ColorMap;
+
+ Graph g;
+
+ // Add a couple thousand vertices
+ for(size_t i = 0; i < N; ++i) {
+ g.add_vertex(i);
+ }
+
+ // Create a color map for the vertices.
+ ColorContainer colors(g.vertices());
+ ColorMap cm(colors);
+
+ ptime start = microsec_clock::local_time();
+ for(Graph::vertex_iterator i = g.begin_vertices(); i != g.end_vertices(); ++i) {
+ colors[*i] = black_color;
+ }
+ ptime stop = microsec_clock::local_time();
+ cout << "time: " << stop - start << endl;
+
+ Graph::vertex_descriptor v = *g.begin_vertices();
+ put(cm, v, color_traits<color>::red());
+ cout << get(cm, v) << endl;
+
+ interior_vertex_property<Graph>::map_type im(g);
+ put(im, v, 12);
+ cout << "test: " << get(im, v) << endl;
+}
+
+void test_2()
+{
+ typedef graph<int, int, vertex_vector> Graph;
+ typedef exterior_vertex_property<Graph, color>::container_type ColorContainer;
+
+ Graph g;
+
+ // Add a couple thousand vertices
+ for(size_t i = 0; i < N; ++i) {
+ g.add_vertex(i);
+ }
+
+ // Create a color map for the vertices.
+ ptime start = microsec_clock::local_time();
+ ColorContainer colors(g.vertices());
+ for(Graph::vertex_iterator i = g.begin_vertices(); i != g.end_vertices(); ++i) {
+ colors[*i] = black_color;
+ }
+ ptime stop = microsec_clock::local_time();
+ cout << "time: " << stop - start << endl;
+
+}
+
+void test_3()
+{
+ typedef graph<VertexProps, EdgeProps, vertex_list> Graph;
+ typedef interior_vertex_property<Graph, string VertexProps::*>::map_type NameMap;
+ typedef interior_vertex_property<Graph, double EdgeProps::*>::map_type WeightMap;
+
+ Graph g;
+
+ // Add a couple thousand vertices
+ for(size_t i = 0; i < N; ++i) {
+ g.add_vertex();
+ }
+
+ NameMap nm(g, &VertexProps::name);
+ Graph::vertex_descriptor v = *g.begin_vertices();
+
+ WeightMap wm(g, &EdgeProps::weight);
+
+ put(nm, v, "Bob");
+ cout << "test: " << get(nm, v) << endl;
+
+
+}
Added: sandbox/SOC/2008/graphs/libs/graphs/color.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/color.hpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,34 @@
+
+#if BOOST_HAS_CONCEPTS
+/**
+ * The Color concept defines the requirements for colors in this library.
+ */
+concept Color<typename C>
+{
+ // The color type must provide an underlying color representation that is
+ // a regular type. This is the return type of all color functions.
+ Regular color_type;
+
+ // Color functions.
+ color_type white();
+ color_type gray();
+ color_type black();
+ color_type red();
+ color_type green();
+ color_type blue();
+};
+
+/**
+ * Adapt the color enum to the Color concept.
+ */
+concept_map<color>
+{
+ typedef color color_type;
+ color white() { return white_color; }
+ color gray() { return gray_color; }
+ color black() { return black_color; }
+ color red() { return red_color; }
+ color green() { return green_color; }
+ color blue() { return blue_color; }
+};
+#endif
\ No newline at end of file
Added: sandbox/SOC/2008/graphs/libs/graphs/concepts.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/concepts.hpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,415 @@
+// This is just a stab at a concept hierarchy for graph. For right now, the
+// trend is to require member functions for the graphs. Obviously, this can
+// be easily rewritten to free functions, but I prefer the object paradigm to
+// the procedural paradigm.
+
+// Recall that a graph is defined as the mathematical object G = (V, E) with
+// V being a set of vertices and E a set of edges. While mathematically
+// consistent, the meaning of "set" can vary greatly depending on the specific
+// graph application. These concepts are intended to provide several alternative
+// definitions of the meanings of the term "set".
+
+// Is this overengineering or is it just an extremely thorough analysis of the
+// domain?
+
+/**
+ * Descriptors are the cornerstone of the graph library. In order to be usable
+ * they must be both regular and hashable.
+ *
+ * The hashability requirements is only really required if you want to use these
+ * in hash tables and sets.
+ */
+concept Descriptor<typename Desc>
+ : Regular<Desc>
+ , Hashable<Desc>
+{ }
+
+/**
+ * The base of all graph concepts, this simply requires type names for vertex
+ * and edge descriptors. Note that descriptors are regular types.
+ */
+concept GraphBase<typename Graph>
+ : DefaultConstructible<Graph>
+ , CopyConstructible<Graph>
+{
+ Descriptor vertex_descriptor;
+ Descriptor edge_descriptor;
+};
+
+/**
+ * A VertexListGraph provides iterators over the graph's vertex set.
+ *
+ * The term "list" in the name does not connote storage requirements, but simply
+ * expresses the fact that vertices can be accessed in sequential order.
+ *
+ * Although it may seem that this is a no-brainer and all graphs should support
+ * vertex iteration, this not necessarily the case. A sequence of pairs can
+ * be used to model a very lightweight graph type that has no explicit vertex
+ * iteration capabilities.
+ */
+concept VertexListGraph<typename Graph>
+ : GraphBase<Graph>
+{
+ // Should this be mutable forward? Probably not since we don't really like
+ // modifying the store structure via iterators.
+ ForwardIterator vertex_iterator;
+ requires SameType<vertex_iterator::dereference_result, vertex_descriptor>;
+
+ // Just for ease of expression.
+ typename vertex_range = std::pair<vertex_iterator, vertex_iterator>;
+
+ // Number of vertices.
+ typename vertices_size_type;
+
+ vertex_iterator Graph::begin_vertices() const;
+ vertex_iterator Graph::end_vertices() const;
+ vertex_range Graph::vertices() const;
+ vertices_size_type Graph::num_vertices() const;
+};
+
+/**
+ * An EdgeListGraph provides iterator over the graph's edge set.
+ *
+ * The term "list" in the name does not connote storage requirements, but simply
+ * expresses the fact that edges can be accessed in sequential order.
+ */
+concept EdgeListGraph<typename Graph>
+ : GraphBase<Graph>
+{
+ // Again, not mutable because we don't use these to modify edge storage.
+ ForwardIterator edge_iterator;
+ requires SameType<edge_iterator::dereference_result, edge_descriptor>;
+
+ typename edge_range = std::pair<edge_iterator, edge_iterator>;
+ typename edges_size_type;
+
+ edge_iterator Graph::begin_edges() const;
+ edge_iterator Graph::end_edges() const;
+ edge_range Graph::edges() const;
+ edges_size_type num_edges() const;
+};
+
+/**
+ * A PropertyVertexGraph is a graph whose vertices have properties. The graph
+ * must therefore provide a method for mapping between a vertex and its
+ * properties.
+ */
+concept PropertyVertexGraph<typename Graph>
+ : GraphBase<Graph>
+{
+ Semiregular vertex_properties;
+
+ vertex_properties& Graph::properties(vertex_descriptor);
+ vertex_properties const& Graph::properties() const;
+};
+
+/**
+ * This concept requires that vertex properties are sortable (i.e., less than
+ * comparable).
+ */
+concept SortableVertexPropertyGraph<typename Graph>
+ : PropertyVertexGraph<Graph>
+{
+ requires LessThanComparable<vertex_properties>
+};
+
+/**
+ * This concept requires that vertex properties are hashable (i.e., can be
+ * hased and are equality comparable).
+ */
+concept HashableVertexPropertyGraph<typename Graph>
+ : PropertyVertexGraph<Graph>
+{
+ requires Hashable<vertex_properties>;
+};
+
+/**
+ * A KeyVertexGraph is a graph whose vertices are mapped to a key. Graphs
+ * that model this concept must provide a function that maps from a vertex
+ * descriptor to its key.
+ */
+concept KeyVertexGraph<typename Graph>
+ : GraphBase<Graph>
+{
+ typename vertex_key;
+
+ vertex_key Graph::key(vertex_descriptor) const;
+};
+
+/**
+ * This concept requires that the vertex keys are sortable (i.e., less than
+ * comparable.
+ */
+concept SortableVertexKeyGraph<typename Graph>
+ : VertexKeyGraph<Graph>
+{
+ requires LessThanComparable<vertex_key>;
+};
+
+/**
+ * This concept requires that the vertex keys are hashable.
+ */
+concept HashableVertexKeyGraph<typename Graph>
+ : VertexKeyGraph<Graph>
+{
+ requires Hashable<vertex_key>;
+};
+
+// We need a couple of empty concepts to group vertex sets and maps because
+// the add/remove concepts are orthoganal to the find functions. These conepts
+// are analagous to parts of the STL container concepts. Note that any specific
+// graph type is probably only exactly one of these.
+
+concept SequentialVertexGraph<typename Graph>
+ : GraphBase<Graph>
+{ }
+
+concept AssociativeVertexGraph<typename Graph>
+{ }
+
+concept SimpleAssociativeVertexGraph<typename Graph>
+ : AssociativeVertexGraph<Graph>
+ , VertexPropertyGraph<Graph>
+{ };
+
+concept PairAssociativeVertexGraph<typename Graph>
+ : AssociativeVertexGraph<Graph>
+ , VertexKeyGraph<Graph>
+{ }
+
+// All of the following essentially describe requirements on storage types
+// that enable the efficient lookup of vertices based on either properties
+// or some key type.
+
+/**
+ * A UniqueVertexGraph is a property graph whose vertex properties comprise a
+ * unique identify for that vertex within the graph.
+ *
+ * This concept does not define the method by which the uniqueness constraint
+ * is enforced. That is done by derived vertices.
+ *
+ * @todo Should this be called VertexSetGraph?
+ */
+concept VertexSetGraph<typename Graph>
+ : SimpleAssociativeVertexGraph<Graph>
+{
+ vertex_descriptor Graph::find(vertex_properties);
+};
+
+/** V == std::set */
+concept SortedVertexSetGraph<typename Graph>
+ : VeretxSetGraph<Graph>
+ , SortableVertexPropertyGraph<Graph>
+{ }
+
+/** V == std::unordered_set */
+concept HashedVertexSetGraph<typename Graph>
+ : VertexSetGraph<Graph>
+ , HashableVertexPropertyGraph<Graph>
+{ }
+
+/**
+ * A UniqueMappedVertexGraph is a property graph whose vertices are mapped
+ * one-to-one to a key type. These types of graphs are often used in favor of
+ * simple vertex graphs when the vertex properties have many attributes, but
+ * only one attribute that is intended to be a key.
+ *
+ * This graph concept refines a property graph because it makes little sense
+ * not to.
+ */
+concept VertexMapGraph<typename Graph>
+ : PairAssociativeVertexGraph<Graph>
+{
+ typename vertex_key;
+
+ vertex_descriptor Graph::find(vertex_key);
+};
+
+/** V == std::map */
+concept SortedVertexMapGraph<typename Graph>
+ : VertexMapGraph<Graph>
+ , SortableVertexPropertyGraph<Graph>
+{ }
+
+/** V = std::unordered_map */
+concept HashedVertexMapGraph<typename Graph>
+ : VertexMapGraph<Graph>
+ , SortableVertexPropertyGraph<Graph>
+{ }
+
+/**
+ * A MultiSimpleVertexGraph is a property graph and vertex list graph that can
+ * stores multiple vertices with the same identity. Note this is also a
+ * vertex list graph because the find operation returns a range of vertices.
+ *
+ * I am not entirely sure of the applications of multisets for vertices. There
+ * may be some interesting applications since the equality of vertices denotes
+ * an implicit relation between them.
+ */
+concept VertexMultisetGraph<typename Graph>
+ : VertexListGraph<Graph>
+ , SimpleAssociativeVertexGraph<Graph>
+{
+ vertex_range Graph::find(vertex_properties);
+};
+
+concept SortedVertexMultisetGraph<typename Graph>
+ : VertexMultisetGraph<Graph>
+ , SortableVertexPropertyGraph<Graph>
+{ }
+
+concept HashedVertexMultisetGraph<typename Graph>
+ : VertexMultisetGraph<Graph>
+ , HashableVertexPropertyGraph<Graph>
+{ }
+
+/**
+ * A MultiMappedVertexGraph is a property grapbh and vertex list graph that
+ * can map multiple vertices to the same key.
+ *
+ * As with above, I am not certain of the specific applications of multimaps
+ * for vertices.
+ */
+concept VertexMulitmapGraph<typename Graph>
+ : VertexListLGraph<Graph>
+ , PairAssociativeVertexGraph<Graph>
+{
+ typename vertex_key;
+
+ vertex_range Graph::find(vertex_key);
+};
+
+concept SortedVertexMultisetGraph<typename Graph>
+ : VertexMultisetGraph<Graph>
+ , SortableVertexPropertyGraph<Graph>
+{ }
+
+concept HashedVertexMultisetGraph<typename Graph>
+ : VertexMultisetGraph<Graph>
+ , HashableVertexPropertyGraph<Graph>
+{ }
+
+
+// The add vertex functionality... These concepts embody graph types that allow
+// the programmatic expansion of the graph.
+//
+// TODO: This is pretty nasty. I'd like a single add_vertex() function that
+// takes no parameters, and is available for all graph types. Unfortunately,
+// it doesn't make sense for PropertyGraphs or map-like graphs. Besides, you
+// can't add an element to a set or map without specific properties although
+// you can force them to default values.
+
+/**
+ * A base concept for all extendible graphs. This concept does not actually
+ * require anything of the graph type and should never be explicitly modeled
+ * by any specific graph type. Instead, types should model one of the following
+ * concepts.
+ */
+concept ExtendableGraph<typename Graph>
+{
+};
+
+/**
+ * For sequential graphs with that has no properties. This essentially provides
+ * functionality for adding another vertex to the graph.
+ */
+concept ExtendableSequentialVertexGraph<typename Graph>
+ : ExtendableGraph<Graph>
+ , SequentialVertexGraph<Graph>
+{
+ vertex_descriptor Graph::add_vertex();
+};
+
+/**
+ * For sequential graphs with properties. Note that this is not a refinement
+ * of ExtendableSequentialVertexGraph because the vertex properties are not
+ * guaranteed to be default constructible (although they almost always are).
+ *
+ * @todo Consider refinement from the ExtendableSequentialVertexGraph. Again,
+ * this would only be supported if
+ */
+concept ExtendableSequentialVertexPropertyGraph<typename Graph>
+ : ExtendableGraph<Graph>
+ , SequentialVertexGraph<Graph>
+ , VertexPropertyGraph<Graph>
+{
+ vertex_descriptor Graph::add_vertex(vertex_properties);
+};
+
+/**
+ * For set-like graphs, provides the ability to add a vertex that is identified
+ * by the given properties.
+ *
+ * Although this supports the same requirements as the previous concept, it has
+ * different semantics (and complexity).
+ *
+ * @todo Consider merging this with the previous function.
+ */
+concept ExtendableSimpleAssociativeVertexGraph<typename Graph>
+ : ExtendableGraph<Graph>
+ , SimpleAssociativeVertexGraph<Graph>
+{
+ vertex_descriptor Graph::add_vertex(vertex_properties);
+};
+
+/**
+ * For map-like graphs, provides the ability to add a vertex that is identified
+ * by the given vertex key.
+ */
+concept ExtendablePairAssociativeVertexGraph<typename Graph>
+ : ExtendableGraph<Graph>
+ , PairAssociativeVertexGraph<Graph>
+{
+ vertex_descriptor Graph::add_vertex(vertex_key)
+};
+
+// Remove vertex functionality. Unlike the add
+
+concept ReducibleVertexGraph<typename Graph>
+ : GraphBase<Graph>
+{
+ void Graph::remove_vertex(vertex_descriptor);
+};
+
+/**
+ * For set-like vertex sets, provides the ability to remove all vertices with
+ * the given properties. To remove specific vertices use the remove_vertex()
+ * function that takes a descriptor.
+ *
+ * @todo We could provide a default implementation as remove_vertex(find(p))
+ * except that find() returns a range of iterators for multisets and multimaps.
+ * We can create more functions like remove_vertices() that takes a range.
+ */
+concept ReducibleSimpleAssociativeVertexGraph<typename Graph>
+ : ReducibleVertexGraph<Graph>
+ , SimpleAssociativeVertexGraph<Graph>
+{
+ void Graph::remove_vertex(vertex_properties);
+};
+
+/**
+ * For map-like vertex sets, provides the ability to remove all vertices with
+ * the given key. To remove specific vertices use the remove_vertex() function
+ * that takes a given descriptor.
+ */
+concept ReduciblePairAssociativeVertexGraph<typename Graph>
+ : ReducibleVertexGraph<Graph>
+ , PairAssociativeVertexGraph<Graph>
+{
+ void Graph::remove_vertex(vertex_key);
+};
+
+// I guess we could ultimately end up with somethig like this.
+
+concept Graph<typename G>
+ : AssociativeVertexGraph<G>
+ , EdgeSetGraph<G>
+{
+};
+
+concept Multigraph<G>
+ : AssociativeVertexGraph<G>
+ , EdgeMultisetGraph<G>
+{ }
+
+
Added: sandbox/SOC/2008/graphs/libs/graphs/demangle.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/demangle.hpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,14 @@
+
+#ifndef DEMANGLE_HPP
+#define DEMANGLE_HPP
+
+#include <string>
+#include <typeinfo>
+#include <cxxabi.h>
+
+std::string demangle(std::string const& name)
+{
+ return std::string(abi::__cxa_demangle(name.c_str(), 0, 0, 0));
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/libs/graphs/doc/concepts.dot
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/doc/concepts.dot 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,118 @@
+
+digraph G {
+ rankdir = BT;
+ node [shape = box];
+
+ GraphBase;
+ VertexListGraph;
+
+ /** For graphs with vertex properties. */
+ VertexPropertyGraph;
+ SortableVertexPropertyGraph;
+ HashableVertexPropertyGraph;
+
+ /** For graphs with vertex keys. */
+ VertexKeyGraph;
+ SortableVertexKeyGraph;
+ HashableVertexKeyGraph;
+
+ /** Basic types of vertex sets */
+ SequentialVertexGraph;
+ SimpleAssociativeVertexGraph;
+ PairAssociativeVertexGraph;
+
+ /** Vertex sets */
+ VertexSetGraph;
+ SortedVertexSetGraph;
+ HashedVertexSetGraph;
+
+ /** Vertex maps */
+ VertexMapGraph;
+ SortedVertexMapGraph;
+ HashedVertexMapGraph;
+
+ /** Vertex multisets */
+ /*
+ VertexMultisetGraph;
+ SortedVertexMultisetGraph;
+ HashedVertexMultisetGraph;
+ */
+
+ /** Vertex multimaps */
+ /*
+ VertexMultimapGraph;
+ SortedVertexMultimapGraph;
+ HashedVertexMultimapGraph;
+ */
+
+ /** Extendability */
+ ExtendableVertexGraph;
+ ExtendableSequentialVertexGraph;
+ ExtendableSequentialVertexPropertyGraph;
+ ExtendableSimpleAssociativeVertexGraph;
+ ExtendablePairAssociativeVertexGraph;
+
+ /** Reducibility */
+ ReducibleVertexGraph;
+ ReducibleSimpleAssociativeVertexGraph;
+ ReduciblePairAssociativeVertexGraph;
+
+ // Edges
+ VertexListGraph -> GraphBase;
+ VertexPropertyGraph -> GraphBase;
+ VertexKeyGraph -> GraphBase;
+
+ SortableVertexPropertyGraph -> VertexPropertyGraph;
+ HashableVertexPropertyGraph -> VertexPropertyGraph;
+ SortableVertexKeyGraph -> VertexKeyGraph;
+ HashableVertexKeyGraph -> VertexKeyGraph;
+
+ SequentialVertexGraph -> GraphBase;
+ SimpleAssociativeVertexGraph -> VertexPropertyGraph;
+ PairAssociativeVertexGraph -> VertexKeyGraph;
+
+ VertexSetGraph -> SimpleAssociativeVertexGraph;
+ SortedVertexSetGraph -> SortableVertexPropertyGraph;
+ SortedVertexSetGraph -> VertexSetGraph;
+ HashedVertexSetGraph -> HashableVertexPropertyGraph;
+ HashedVertexSetGraph -> VertexSetGraph;
+
+ VertexMapGraph -> PairAssociativeVertexGraph;
+ SortedVertexMapGraph -> SortableVertexKeyGraph;
+ SortedVertexMapGraph -> VertexMapGraph;
+ HashedVertexMapGraph -> HashableVertexKeyGraph;
+ HashedVertexMapGraph -> VertexMapGraph;
+
+ /*
+ VertexMultisetGraph -> VertexListGraph;
+ VertexMultisetGraph -> SimpleAssociativeVertexGraph;
+ SortedVertexMultisetGraph -> SortableVertexPropertyGraph;
+ SortedVertexMultisetGraph -> VertexMultisetGraph;
+ HashedVertexMultisetGraph -> HashableVertexPropertyGraph;
+ HashedVertexMultisetGraph -> VertexMultisetGraph;
+
+ VertexMultimapGraph -> VertexListGraph;
+ VertexMultimapGraph -> PairAssociativeVertexGraph;
+ SortedVertexMultimapGraph -> SortableVertexKeyGraph;
+ SortedVertexMultimapGraph -> VertexMultimapGraph;
+ HashedVertexMultimapGraph -> HashableVertexKeyGraph;
+ HashedVertexMultimapGraph -> VertexMultimapGraph;
+ */
+
+ ExtendableSequentialVertexGraph -> ExtendableVertexGraph;
+ ExtendableSequentialVertexGraph -> SequentialVertexGraph;
+ ExtendableSequentialVertexPropertyGraph -> ExtendableVertexGraph;
+ ExtendableSequentialVertexPropertyGraph -> SequentialVertexGraph;
+ ExtendableSequentialVertexPropertyGraph -> VertexPropertyGraph;
+ ExtendableSimpleAssociativeVertexGraph -> ExtendableVertexGraph;
+ ExtendableSimpleAssociativeVertexGraph -> SimpleAssociativeVertexGraph;
+ ExtendablePairAssociativeVertexGraph -> ExtendableVertexGraph;
+ ExtendablePairAssociativeVertexGraph -> PairAssociativeVertexGraph;
+
+ ReducibleVertexGraph -> GraphBase;
+ ReducibleSimpleAssociativeVertexGraph -> ReducibleVertexGraph;
+ ReducibleSimpleAssociativeVertexGraph -> SimpleAssociativeVertexGraph;
+ ReduciblePairAssociativeVertexGraph -> ReducibleVertexGraph;
+ ReduciblePairAssociativeVertexGraph -> PairAssociativeVertexGraph;
+
+}
Added: sandbox/SOC/2008/graphs/libs/graphs/hash.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/hash.cpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,50 @@
+
+#include <iostream>
+#include <vector>
+#include <tr1/unordered_map>
+#include <cstdlib>
+#include <ctime>
+
+#include <boost/date_time.hpp>
+
+using namespace std;
+using namespace std::tr1;
+using namespace boost::posix_time;
+
+int
+main(int argc, char *argv[])
+{
+ srand(time(0));
+
+ // Create a vector of 1000 elements.
+ vector<int> v(1000);
+ for(size_t i = 0; i < 1000; ++i) {
+ v[i] = rand() % 100;
+ }
+
+ // Create a map of 1000 elements
+ unordered_map<int*, int> m;
+ for(size_t i = 0; i < 1000; ++i) {
+ m[&v[i]] = rand() % 100;
+ }
+
+ ptime start, stop;
+
+ // Time accesses
+ start = microsec_clock::local_time();
+ for(size_t i = 0; i < 1000; ++i) {
+ int x = v[rand() % 1000];
+ }
+ stop = microsec_clock::local_time();
+ cout << "Vector: " << stop - start << endl;
+
+ // Time accesses
+ start = microsec_clock::local_time();
+ for(size_t i = 0; i < 1000; ++i) {
+ cout << m[&v[rand() % 1000]] << " ";
+ }
+ stop = microsec_clock::local_time();
+ cout << "Hash: " << stop - start << endl;
+
+ return 0;
+}
Added: sandbox/SOC/2008/graphs/libs/graphs/ordered_pair.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/ordered_pair.cpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,17 @@
+
+#include <iostream>
+
+#include <boost/graphs/utility.hpp>
+
+using namespace std;
+using namespace boost::graphs;
+
+int
+main(int argc, char *argv[])
+{
+ ordered_pair<int> a(0, 3);
+ ordered_pair<int> b = make_ordered_pair(1, 4);
+
+ cout << a.first() << " " << a.second() << endl;
+ cout << b.first() << " " << b.second() << endl;
+}
Added: sandbox/SOC/2008/graphs/libs/graphs/print_vertices.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/print_vertices.hpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,17 @@
+
+#ifndef PRINT_VERTICES_HPP
+#define PRINT_VERTICES_HPP
+
+template <typename Graph>
+void print_vertices(Graph const& g)
+{
+ typename Graph::vertex_iterator
+ i = g.begin_vertices(),
+ end = g.end_vertices();
+ for( ; i != end; ++i) {
+ typename Graph::vertex_descriptor v = *i;
+ std::cout << g.properties(v) << std::endl;
+ }
+}
+
+#endif
Added: sandbox/SOC/2008/graphs/libs/graphs/unordered_pair.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/unordered_pair.cpp 2008-05-29 08:57:10 EDT (Thu, 29 May 2008)
@@ -0,0 +1,17 @@
+
+#include <iostream>
+
+#include <boost/graphs/utility.hpp>
+
+using namespace std;
+using namespace boost::graphs;
+
+int
+main(int argc, char *argv[])
+{
+ unordered_pair<int> a(3, 0);
+ unordered_pair<int> b = make_unordered_pair(4, 1);
+
+ cout << a.first() << " " << a.second() << endl;
+ cout << b.first() << " " << b.second() << endl;
+}
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