|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-05-29 18:37:32
Author: asutton
Date: 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
New Revision: 45928
URL: http://svn.boost.org/trac/boost/changeset/45928
Log:
Finished putting together a simple test of graph construction.
Fixed a number of iterators that were missing a couple of operators.
Text files modified:
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp | 1
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp | 10 ++--
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp | 25 ++++++++++
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp | 6 ++
sandbox/SOC/2008/graphs/libs/graphs/add_vertices.hpp | 4 +
sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp | 100 +++++++++++++--------------------------
sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp | 19 ++++---
7 files changed, 82 insertions(+), 83 deletions(-)
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_vector.hpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -117,7 +117,6 @@
edge_properties const& ep)
{
// Add the edge object. Its descriptor is its index.
- std::cout << "here?" << std::endl;
_edges.push_back(edge_type(u, v, ep));
return _edges.size() - 1;
}
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -25,9 +25,9 @@
template <
typename VertexProps = none,
typename EdgeProps = none,
- template <typename> class VertexStore = vertex_list,
+ template <typename> class VertexStore = vertex_set,
template <typename> class EdgeStore = edge_set,
- template <typename> class VertexEdgeStore = vertex_edge_list
+ template <typename> class VertexEdgeStore = vertex_edge_set
>
struct graph
: adjacency_list<
@@ -55,9 +55,9 @@
template <
typename VertexProps = none,
typename EdgeProps = none,
- template <typename> class VertexStore = vertex_list,
- template <typename> class EdgeStore = edge_list,
- template <typename> class VertexEdgeStore = vertex_edge_list
+ template <typename> class VertexStore = vertex_set,
+ template <typename> class EdgeStore = edge_set,
+ template <typename> class VertexEdgeStore = vertex_edge_set
>
struct multigraph
: adjacency_list<
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/indexed_vertex_iterator.hpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -47,6 +47,25 @@
return *this;
}
+ inline indexed_vertex_iterator& operator=(indexed_vertex_iterator const& x)
+ {
+ indexed_vertex_iterator t(x);
+ swap(t);
+ return *this;
+ }
+
+ inline indexed_vertex_iterator& operator+=(difference_type n)
+ {
+ iter += n;
+ return *this;
+ }
+
+ inline indexed_vertex_iterator& operator-=(difference_type n)
+ {
+ iter -= n;
+ return *this;
+ }
+
// Support addition and subtraction as per random access iterators
inline indexed_vertex_iterator operator+(difference_type n) const
{ return iter + n; }
@@ -68,6 +87,12 @@
inline bool operator!=(indexed_vertex_iterator const& x) const
{ return (store == x.store) && (iter != x.iter); }
+ inline void swap(indexed_vertex_iterator& x)
+ {
+ std::swap(store, x.store);
+ std::swap(iter, x.iter);
+ }
+
Store const* store;
iterator iter;
};
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/vs/value_vertex_iterator.hpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -48,6 +48,12 @@
return *this;
}
+ inline value_vertex_iterator& operator--()
+ {
+ --iter;
+ return *this;
+ }
+
inline reference operator*()
{ return &const_cast<vertex_type&>(*iter); }
Modified: sandbox/SOC/2008/graphs/libs/graphs/add_vertices.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/libs/graphs/add_vertices.hpp (original)
+++ sandbox/SOC/2008/graphs/libs/graphs/add_vertices.hpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -3,7 +3,9 @@
#define ADD_VERTICES_HPP
/**
- * Add numbered vertices to the graph.
+ * Add numbered vertices to the graph. This works for mapped
+ * vertices too - as long as the key type is integers. This
+ * will just default the mapped vertex properties.
*
* @requires ExtendableGraph<Graph>
* @requires PropertyGraph<Graph>
Modified: sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp (original)
+++ sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -6,116 +6,82 @@
#include <boost/graphs/adjacency_list.hpp>
#include "add_vertices.hpp"
+#include "add_edges.hpp"
using namespace std;
using namespace boost::graphs;
using namespace boost::graphs::adj_list;
-// The prurpose of this file is to instantiate every possible combination
-// of structural components for the adjacency list. There are a quite a few.
-// Testing functions are named for the storage components that define each
-// part of the adjacency list. They are:
+// Instantiate a number of graph types. This are what I would think that
+// some of the more common types are.
//
// type_vertex_edge_incident
-//
-// Where type is the predominant structural type of the graph, vertex is the
-// vertex store, edge is the edge store and incidedent is the vertex edge store.
-// Anonymous vertices, multigraph, not reducible.
void undirected_vector_vector_vector();
-void undirected_vector_vector_list();
-void undirected_vector_vector_set();
+void undirected_list_list_list();
+void undirected_set_set_set();
+void undirected_map_set_set();
-// Anonymous vertices, multigraph, fully mutable
-void undirected_vector_list_vector();
-void undirected_vector_list_list();
-void undirected_vector_list_set();
-
-// Anonymous vertices, simple graph, fully mutable
-void undirected_vector_set_vector();
-void undirected_vector_set_list();
-void undirected_vector_set_set();
-
-// Anonymous vertices, simple graph, fully mutable
-// Not implemented
-void undirected_vector_multiset_vector();
-void undirected_vector_multiset_list();
-void undirected_vector_multiset_set();
+static const int V = 100;
+static const int E = 100;
-static const int N = 100;
int
main(int argc, char *argv[])
{
undirected_vector_vector_vector();
- undirected_vector_vector_list();
- undirected_vector_vector_set();
-
- undirected_vector_list_vector();
- undirected_vector_list_list();
- undirected_vector_list_set();
+ undirected_list_list_list();
+ undirected_set_set_set();
+ undirected_map_set_set();
return 0;
}
+// Best used for fast graph construction. Note that you can't remove elements
+// from this graph, and it allows duplicate vertices and edges.
void undirected_vector_vector_vector()
{
typedef adjacency_list<
undirected, int, int, vertex_vector, edge_vector, vertex_edge_vector
> Graph;
Graph g;
- add_vertices(g, N);
-}
-
-void undirected_vector_vector_list()
-{
- typedef adjacency_list<
- undirected, int, int, vertex_vector, edge_vector, vertex_edge_list
- > Graph;
- Graph g;
- add_vertices(g, N);
-}
-
-void undirected_vector_vector_set()
-{
- typedef adjacency_list<
- undirected, int, int, vertex_vector, edge_vector, vertex_edge_set
- > Graph;
- Graph g;
- add_vertices(g, N);
+ add_vertices(g, V);
+ add_edges(g, E);
}
-void undirected_vector_list_vector()
+// Best used for fast graph construction. This graph supports vertex and edge
+// removal, but the edge removal is slower than if you use an incidence set.
+// Also, this allows duplicate vertices and edges.
+void undirected_list_list_list()
{
typedef adjacency_list<
- undirected, int, int, vertex_vector, edge_list, vertex_edge_vector
+ undirected, int, int, vertex_list, edge_list, vertex_edge_list
> Graph;
Graph g;
- add_vertices(g, N);
+ add_vertices(g, V);
+ add_edges(g, E);
}
-void undirected_vector_list_list()
+// This is probably the best all-around implementation of simple graphs
+// if vertices can be uniquely identified. Construction is relatively
+// slow, but the graph is fully mutable at "optimal" complexity. At least
+// its mutation operations are faster than non-sorted/hashed containers.
+void undirected_set_set_set()
{
typedef adjacency_list<
- undirected, int, int, vertex_vector, edge_list, vertex_edge_vector
+ undirected, int, int, vertex_set, edge_set, vertex_edge_set
> Graph;
Graph g;
- add_vertices(g, N);
+ add_vertices(g, V);
}
-void undirected_vector_list_set()
+// Pretty much the same as above, but vertices are mapped to a key.
+void undirected_map_set_set()
{
typedef adjacency_list<
- undirected, int, int, vertex_vector, edge_list, vertex_edge_vector
+ undirected, none, int, int_to_vertex_map, edge_set, vertex_edge_set
> Graph;
Graph g;
- add_vertices(g, N);
+ add_vertices(g, V);
}
-void undirected_vector_set_vector();
-void undirected_vector_set_list();
-void undirected_vector_set_set();
-
-void undirected_vector_multiset_vector();
-void undirected_vector_multiset_list();
-void undirected_vector_multiset_set();
Modified: sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp (original)
+++ sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp 2008-05-29 18:37:32 EDT (Thu, 29 May 2008)
@@ -8,14 +8,16 @@
#include <boost/graphs/adjacency_list.hpp>
#include <boost/graphs/breadth_first_search.hpp>
-#include <boost/date_time.hpp>
+// FIXME: this doesn't compile under g++4.4. Something about the changing
+// the meaning of a type (i'm guessing template to type name).
+// #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;
+// using namespace boost::posix_time;
struct VertexProps
{
@@ -70,12 +72,12 @@
ColorContainer colors(g.vertices());
ColorMap cm(colors);
- ptime start = microsec_clock::local_time();
+ // 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;
+ // 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());
@@ -99,14 +101,13 @@
}
// Create a color map for the vertices.
- ptime start = microsec_clock::local_time();
+ // 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;
-
+ // ptime stop = microsec_clock::local_time();
+ // cout << "time: " << stop - start << endl;
}
void test_3()
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