From: asutton_at_[hidden]
Date: 2008-05-30 11:13:50
Author: asutton
Date: 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
New Revision: 45952
URL: http://svn.boost.org/trac/boost/changeset/45952
Log:
Added an adjacency iterator that may work for a bunch of different types
of graphs - assuming there's a standard incidence iterator for all of
them.
Added:
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_iterator.hpp (contents, props changed)
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/edge.hpp (contents, props changed)
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/vertex.hpp (contents, props changed)
sandbox/SOC/2008/graphs/libs/graphs/incidence.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp | 159 +++++++++--------
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp | 14
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/graphs.hpp | 8
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp | 2
sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/undirected.hpp | 360 ---------------------------------------
sandbox/SOC/2008/graphs/libs/graphs/Jamfile | 3
sandbox/SOC/2008/graphs/libs/graphs/add_vertices.hpp | 8
sandbox/SOC/2008/graphs/libs/graphs/adjacency_list.cpp | 10
sandbox/SOC/2008/graphs/libs/graphs/bfs.cpp | 6
9 files changed, 119 insertions(+), 451 deletions(-)
Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_iterator.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -0,0 +1,123 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_ADJACENCY_ITERATOR_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_ADJACENCY_ITERATOR_HPP
+
+#include <iterator>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * The adjacency iterator is an abstraction over incidence iterators (provided
+ * by the vertex edge store or an incidence sets). The adjacency iterator
+ * actually provides the same functionality as the incidence iterator, but
+ * simply provides access to the other vertices rather than the edges.
+ *
+ * @todo Depending on the underlying incidence iterator provided by the graph,
+ * we could actually possibly make this a random access iterator rather than
+ * just a bidirectional iterator. For now, this is simply a bidi iterator.
+ */
+template <typename Graph>
+class adjacency_iterator
+{
+ typedef typename Graph::incidence_iterator iterator;
+ typedef typename Graph::vertex_descriptor vertex_descriptor;
+ typedef typename Graph::edge_descriptor edge_descriptor;
+public:
+
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef std::size_t difference_type;
+ typedef vertex_descriptor value_type;
+ typedef vertex_descriptor reference;
+ typedef vertex_descriptor pointer;
+
+ // Constructors
+ inline adjacency_iterator();
+ inline adjacency_iterator(Graph const* g, vertex_descriptor v, iterator i);
+
+ inline adjacency_iterator& operator=(adjacency_iterator const& x);
+ inline adjacency_iterator& operator++();
+ inline adjacency_iterator& operator--();
+
+ inline bool operator==(adjacency_iterator const& x) const;
+ inline bool operator!=(adjacency_iterator const& x) const;
+
+ reference operator*();
+
+private:
+ Graph const* graph;
+ vertex_descriptor vertex;
+ iterator iter;
+};
+
+// Functions
+
+template <typename G>
+adjacency_iterator<G>::adjacency_iterator()
+ : graph(0)
+ , vertex()
+ , iter()
+{ }
+
+template <typename G>
+adjacency_iterator<G>::adjacency_iterator(G const* g, vertex_descriptor v, iterator i)
+ : graph(g)
+ , vertex(v)
+ , iter(i)
+{ }
+
+template <typename G>
+adjacency_iterator<G>&
+adjacency_iterator<G>::operator=(adjacency_iterator const& x)
+{
+ graph = x.graph;
+ vertex = x.vertex;
+ iter = x.iter;
+ return *this;
+}
+
+template <typename G>
+adjacency_iterator<G>&
+adjacency_iterator<G>::operator++()
+{
+ ++iter;
+ return *this;
+}
+
+template <typename G>
+adjacency_iterator<G>&
+adjacency_iterator<G>::operator--()
+{
+ --iter;
+ return *this;
+}
+
+template <typename G>
+bool
+adjacency_iterator<G>::operator==(adjacency_iterator const& x) const
+{
+ return (graph == x.graph) && (vertex == x.vertex) && (iter == x.iter);
+}
+
+template <typename G>
+bool
+adjacency_iterator<G>::operator!=(adjacency_iterator const& x) const
+{
+ return !operator==(x);
+}
+
+template <typename G>
+typename adjacency_iterator<G>::reference
+adjacency_iterator<G>::operator*()
+{
+ typename G::edge_type const& e = graph->edge(*iter);
+ return e.opposite(vertex);
+}
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif
+
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/adjacency_list.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -8,6 +8,7 @@
#include <boost/graphs/adjacency_list/types.hpp>
#include <boost/graphs/adjacency_list/storage.hpp>
#include <boost/graphs/adjacency_list/policy.hpp>
+#include <boost/graphs/adjacency_list/adjacency_iterator.hpp>
// I think that if we concept-ize the internals of the adjacency list, then
// we can filter the external interface. This would be a great place to use
@@ -62,17 +63,28 @@
> graph_type;
public:
+ typedef adjacency_list<
+ Type, VertexProps, EdgeProps, VertexStore, EdgeStore, VertexEdgeStore, AllowEdgePolicy
+ > this_type;
+
typedef VertexStore<typename graph_type::vertex_type> vertex_store;
typedef EdgeStore<typename graph_type::edge_type> edge_store;
typedef typename vertex_store::vertex_type vertex_type;
typedef typename vertex_store::vertex_descriptor vertex_descriptor;
+ typedef typename vertex_store::vertex_iterator vertex_iterator;
typedef typename vertex_type::properties_type vertex_properties;
typedef typename edge_store::edge_type edge_type;
typedef typename edge_store::edge_descriptor edge_descriptor;
+ typedef typename edge_store::edge_iterator edge_iterator;
typedef typename edge_type::properties_type edge_properties;
+ typedef typename vertex_type::incidence_iterator incidence_iterator;
+ typedef typename vertex_type::incidence_range incidence_range;
+ typedef adjacency_iterator<this_type> adjacency_iterator;
+ typedef std::pair<adjacency_iterator, adjacency_iterator> adjacency_range;
+
adjacency_list();
// Add edge
@@ -80,15 +92,6 @@
edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v);
edge_descriptor add_edge(vertex_descriptor u, vertex_descriptor v, edge_properties const& ep);
- // requires HasAdd<vertex_store> && UniqueComparableVertex<vertex_type>
- edge_descriptor add_edge(vertex_properties const& u, vertex_properties const& v);
- edge_descriptor add_edge(vertex_properties const& u, vertex_properties const& v, edge_properties const& ep);
-
- // requires HasAdd<vertex_store> && UniqueMappedVertex<vertex_type> &&
- // SameType<Key, typename vertex_store::key_type>
- template <typename Key> edge_descriptor add_edge(Key const& u, Key const& v);
- template <typename Key> edge_descriptor add_edge(Key const& u, Key const& v, edge_properties const& ep);
-
// Insert edge (do we need these functions? - descriptors are evaluable).
// requires HasInsert<vertex_store>
@@ -109,6 +112,15 @@
void remove_edge(vertex_descriptor u, vertex_descriptor v);
+ // Iterators. Lots and lots of iterators.
+ incidence_range incident_edges(vertex_descriptor v) const;
+ incidence_iterator begin_incident_edges(vertex_descriptor v) const;
+ incidence_iterator end_incident_edges(vertex_descriptor v) const;
+
+ adjacency_range adjacent_vertices(vertex_descriptor v) const;
+ adjacency_iterator begin_adjacent_vertices(vertex_descriptor v) const;
+ adjacency_iterator end_adjacent_vertices(vertex_descriptor v) const;
+
// Descriptor accessor. Use these functions to get descriptors...
vertex_descriptor descriptor(vertex_type const& v) const;
edge_descriptor descriptor(edge_type const& e) const;
@@ -184,74 +196,6 @@
return e;
}
-/**
- * Add an edge that connects the two vertices identified by the given
- * properties.
- */
-template <BOOST_GRAPH_ADJLIST_PARAMS>
-typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
-adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
- vertex_properties const& up,
- vertex_properties const& vp)
-{
- return add_edge(up, vp, edge_properties());
-}
-
-/**
- * Add an edge that connects the two vertices identified by the given vertex
- * properties, such that it will contain the have edge properties.
- */
-template <BOOST_GRAPH_ADJLIST_PARAMS>
-typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
-adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
- vertex_properties const& up,
- vertex_properties const& vp,
- edge_properties const& ep)
-{
- // Start by finding the vertices according to their properties.
- vertex_descriptor u = find_vertex(up);
- vertex_descriptor v = find_vertex(vp);
- BOOST_ASSERT(u.is_valid() && v.is_valid());
- return add_edge(u, v, ep);
-}
-
-/**
- * Add an edge that connects the two vertices identified by their keys.
- *
- * @todo Without constrained members, instantiating this function can result in
- * ambigous member functions with the vertex property add_edge() functions if
- * the key type is the same as the vertex properties. We can probably also get
- * rid of the Key template parameter and simply reference the maps key type
- * here.
- *
- * @todo You have to explicitly give the key parameter here because of the
- * other add_vertex() functions.
- */
-template <BOOST_GRAPH_ADJLIST_PARAMS>
-template <typename Key>
-typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
-adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
- Key const& up,
- Key const& vp)
-{
- return add_edge<Key>(up, vp, edge_properties());
-}
-
-template <BOOST_GRAPH_ADJLIST_PARAMS>
-template <typename Key>
-typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::edge_descriptor
-adjacency_list<T,VP,EP,VS,ES,VES,AEP>::add_edge(
- Key const& up,
- Key const& vp,
- edge_properties const& ep)
-{
- // Start by finding the vertices according to their properties.
- vertex_descriptor u = find_vertex(up);
- vertex_descriptor v = find_vertex(vp);
- BOOST_ASSERT(u.is_valid() && v.is_valid());
- return add_edge(u, v, ep);
-}
-
/**
* Add an edge that connects the given properties.
@@ -347,6 +291,67 @@
}
/**
+ * Get an iterator range over the incident edges of the given vertex.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::incidence_range
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::incident_edges(vertex_descriptor v) const
+{
+ return this->vertex(v).incident_edges();
+}
+
+/**
+ * Get an iterator to the beginning of the the incident edges for the given
+ * vertex.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::incidence_iterator
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::begin_incident_edges(vertex_descriptor v) const
+{
+ return this->vertex(v).begin_incident_edges();
+}
+
+/**
+ * Get an iterator past the end of the incident edges of the given vertex.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::incidence_iterator
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::end_incident_edges(vertex_descriptor v) const
+{
+ return this->vertex(v).end_incident_edges();
+}
+
+/**
+ * Get an iterator range over the adjacecnt vertices of the given vertex.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::adjacency_range
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::adjacent_vertices(vertex_descriptor v) const
+{
+ return make_pair(begin_adjacent_vertices(v), end_adjacent_vertices(v));
+}
+
+/**
+ * Get iterator to beginning of the adjacent edges from the given vertex.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::adjacency_iterator
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::begin_adjacent_vertices(vertex_descriptor v) const
+{
+ return adjacency_iterator(this, v, begin_incident_edges(v));
+}
+
+/**
+ * Get an iterator past the end of the adjacent edges of the given vertex.
+ */
+template <BOOST_GRAPH_ADJLIST_PARAMS>
+typename adjacency_list<T,VP,EP,VS,ES,VES,AEP>::adjacency_iterator
+adjacency_list<T,VP,EP,VS,ES,VES,AEP>::end_adjacent_vertices(vertex_descriptor v) const
+{
+ return adjacency_iterator(this, v, end_incident_edges(v));
+}
+
+/**
* Get a descriptor for the given vertex.
*
* This may seem like a strange function, but there's currently no simple way
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/es/edge_set.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -34,7 +34,7 @@
inline basic_edge_set_node(vertex_descriptor u,
vertex_descriptor v,
properties_type const& ep)
- : Edge(ep)
+ : Edge(u, v, ep)
, iter()
{ }
@@ -159,14 +159,16 @@
template <BOOST_GRAPH_ES_PARAMS>
std::pair<typename basic_edge_set<E,C,A>::edge_descriptor, bool>
basic_edge_set<E,C,A>::insert_edge(vertex_descriptor u,
- vertex_descriptor v,
- edge_properties const& ep)
+ vertex_descriptor v,
+ edge_properties const& ep)
{
+ edge_type edge(u, v, ep);
+
std::pair<edge_descriptor, bool> ret;
- std::pair<typename edge_store::iterator, bool> ins =
- _edges.insert(edge_type(u, v, ep));
+ std::pair<typename edge_store::iterator, bool> ins = _edges.insert(edge);
if(ins.second) {
- // Not very pretty...
+ // Not very pretty... the addition succeeds, so re-cast the added edge
+ // and set the descriptor based on that.
edge_type& e = const_cast<edge_type&>(*(ins.first));
e.iter = ins.first;
ret.first = &e;
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-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -29,7 +29,7 @@
template <typename> class EdgeStore = edge_set,
template <typename> class VertexEdgeStore = vertex_edge_set
>
-struct graph
+struct undirected_graph
: adjacency_list<
undirected,
VertexProps,
@@ -56,10 +56,10 @@
typename VertexProps = none,
typename EdgeProps = none,
template <typename> class VertexStore = vertex_set,
- template <typename> class EdgeStore = edge_set,
- template <typename> class VertexEdgeStore = vertex_edge_set
+ template <typename> class EdgeStore = edge_list,
+ template <typename> class VertexEdgeStore = vertex_edge_list
>
-struct multigraph
+struct undirected_multigraph
: adjacency_list<
undirected,
VertexProps,
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/types.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -25,6 +25,6 @@
// It might just be easy enough to build an "incident" edge type and accessor
// for directed vertices that simply returns or something like that.
-#include <boost/graphs/adjacency_list/un/undirected.hpp>
+#include <boost/graphs/adjacency_list/undirected/undirected.hpp>
#endif
Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/edge.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/edge.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -0,0 +1,160 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EDGE_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_EGE_HPP
+
+#include <boost/graphs/utility/unordered_pair.hpp>
+#include <boost/graphs/adjacency_list/edge.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * An undirected edge is an unordered pair of pointers to its endpoints. Note
+ * that because the unordered pair is instantiated over pointers, these are
+ * trivially ordered by their addresses. There is no other way available to
+ * order the vertices (i.e., by custom comparison).
+ *
+ * Note that the edge does allow construction over null endpoints, but that
+ * isn't really recommended since we don't offer any real mutators for the
+ * endpoints. For constructors that do take vertex descriptors, we might also
+ * point out that the ordering is not guaranteed after construction.
+ */
+template <
+ typename VertexProps,
+ typename EdgeProps,
+ typename VertexDesc,
+ typename EdgeDesc
+ >
+class undirected_edge
+ : public edge<EdgeProps>
+{
+public:
+ typedef EdgeDesc descriptor_type;
+ typedef typename edge<EdgeProps>::properties_type properties_type;
+
+ // This seems a little funky, but it turns out that some edge stores can
+ // leverage vertex properties for add/insert functions.
+ typedef VertexDesc vertex_descriptor;
+
+ undirected_edge();
+ undirected_edge(properties_type const& ep);
+ undirected_edge(vertex_descriptor u, vertex_descriptor v);
+ undirected_edge(vertex_descriptor u, vertex_descriptor v, properties_type const& ep);
+
+ unordered_pair<vertex_descriptor> const& ends() const;
+
+ vertex_descriptor source() const;
+ vertex_descriptor target() const;
+ vertex_descriptor opposite(vertex_descriptor v) const;
+
+private:
+ unordered_pair<vertex_descriptor> _ends;
+};
+
+
+// Edge Functions
+
+#define BOOST_GRAPH_UE_PARAMS \
+ typename VP, typename EP, typename V, typename E
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge()
+ : edge<EP>()
+ , _ends()
+{ }
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge(properties_type const& ep)
+ : edge<EP>(ep)
+ , _ends()
+{ }
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u, vertex_descriptor v)
+ : edge<EP>()
+ , _ends(u, v)
+{ }
+
+template <BOOST_GRAPH_UE_PARAMS>
+undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u,
+ vertex_descriptor v,
+ properties_type const& ep)
+ : edge<EP>(ep)
+ , _ends(u, v)
+{ }
+
+/**
+ * Return the endpoints of the edge.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+unordered_pair<typename undirected_edge<VP,EP,V,E>::vertex_descriptor> const&
+undirected_edge<VP,EP,V,E>::ends() const
+{ return _ends; }
+
+/**
+ * Return the source of this edge. The source of an undirected edge is not
+ * necessarily the same as the way it is connected.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+typename undirected_edge<VP,EP,V,E>::vertex_descriptor
+undirected_edge<VP,EP,V,E>::source() const
+{ return _ends.first(); }
+
+/**
+ * Return the target of this edge. The source of an undirected edge is not
+ * necessarily the same as the way it is connected.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+typename undirected_edge<VP,EP,V,E>::vertex_descriptor
+undirected_edge<VP,EP,V,E>::target() const
+{ return _ends.second(); }
+
+/**
+ * Return the vertex opposite the given vertex on this edge.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+typename undirected_edge<VP,EP,V,E>::vertex_descriptor
+undirected_edge<VP,EP,V,E>::opposite(vertex_descriptor u) const
+{
+ return u == _ends.first() ? _ends.second() : _ends.first();
+}
+
+// Operators
+
+// @todo I don't know that I like this. It might be better to build these
+// operators as functors and then typedef them into the edge type rather than
+// simply make these the default operators for the edges.
+
+/**
+ * Edges can be ordered by their end points. This is a lexicographical
+ * comparison of the vertex descriptors in the ends of the edge.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+bool
+operator<(undirected_edge<VP,EP,V,E> const& a,
+ undirected_edge<VP,EP,V,E> const& b)
+{
+ return a.ends() < b.ends();
+}
+
+/**
+ * Edges are also equality comparable by their end points. Note that this does
+ * /not/ compare the properties of vertices.
+ */
+template <BOOST_GRAPH_UE_PARAMS>
+bool
+operator==(undirected_edge<VP,EP,V,E> const& a,
+ undirected_edge<VP,EP,V,E> const& b)
+{
+ return a.ends() == b.ends();
+}
+
+#undef BOOST_GRAPH_UE_PARAMS
+
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif
Modified: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/undirected.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/undirected.hpp (original)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/undirected.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -65,365 +65,11 @@
> edge_type;
};
-/**
- * An undirected vertex tracks the incident edges of the given vertex. Note
- * that the edges actually being stored are pointers to edges in the graph's
- * edge list. The reason for this is so we don't duplicate the properties
- * of each edge.
- *
- * @todo What happens if I store incident edges as a pair... The edge and the
- * opposite end. That might be kind of interesting.
- */
-template <
- typename VertexProps,
- typename EdgeProps,
- typename VertexDesc,
- typename EdgeDesc,
- template <typename> class VertexEdgeStore
- >
-class undirected_vertex
- : public vertex<VertexProps>
-{
-public:
- typedef VertexDesc descriptor_type;
- typedef EdgeDesc edge_descriptor;
- typedef typename vertex<VertexProps>::properties_type properties_type;
-private:
- typedef VertexEdgeStore<edge_descriptor> vertex_edge_store;
-public:
- // Edge iterator types
- typedef typename vertex_edge_store::const_iterator incident_edge_iterator;
- typedef typename vertex_edge_store::size_type degree_type;
-
- undirected_vertex();
- undirected_vertex(VertexProps const& vp);
-
- // Connection interface.
- void connect_to(edge_descriptor e);
- void connect_from(edge_descriptor e);
-
- // Disconnection interface.
- void disconnect_to(edge_descriptor e);
- void disconnect_from(edge_descriptor e);
- void disconnect_all();
-
- std::pair<incident_edge_iterator, incident_edge_iterator> incident_edges() const;
- incident_edge_iterator begin_incident_edges() const;
- incident_edge_iterator end_incident_edges() const;
-
- degree_type degree() const;
-
-private:
- vertex_edge_store _edges;
-};
-
-/**
- * An undirected edge is an unordered pair of pointers to its endpoints. Note
- * that because the unordered pair is instantiated over pointers, these are
- * trivially ordered by their addresses. There is no other way available to
- * order the vertices (i.e., by custom comparison).
- *
- * Note that the edge does allow construction over null endpoints, but that
- * isn't really recommended since we don't offer any real mutators for the
- * endpoints. For constructors that do take vertex descriptors, we might also
- * point out that the ordering is not guaranteed after construction.
- */
-template <
- typename VertexProps,
- typename EdgeProps,
- typename VertexDesc,
- typename EdgeDesc
- >
-class undirected_edge
- : public edge<EdgeProps>
-{
-public:
- typedef EdgeDesc descriptor_type;
- typedef typename edge<EdgeProps>::properties_type properties_type;
-
- // This seems a little funky, but it turns out that some edge stores can
- // leverage vertex properties for add/insert functions.
- typedef VertexDesc vertex_descriptor;
-
- undirected_edge();
- undirected_edge(properties_type const& ep);
- undirected_edge(vertex_descriptor u, vertex_descriptor v);
- undirected_edge(vertex_descriptor u, vertex_descriptor v, properties_type const& ep);
-
- unordered_pair<vertex_descriptor> const& ends() const;
-
- vertex_descriptor source() const;
- vertex_descriptor target() const;
- vertex_descriptor opposite(vertex_descriptor v) const;
-
-private:
- unordered_pair<vertex_descriptor> _ends;
-};
-
-// Vertex Functions
-
-#define BOOST_GRAPH_UV_PARAMS \
- typename VP, typename EP, typename V, typename E, template <typename> class VES
-
-template <BOOST_GRAPH_UV_PARAMS>
-undirected_vertex<VP,EP,V,E,VES>::undirected_vertex()
- : vertex<VP>()
- , _edges()
-{ }
-
-template <BOOST_GRAPH_UV_PARAMS>
-undirected_vertex<VP,EP,V,E,VES>::undirected_vertex(VP const& vp)
- : vertex<VP>(vp)
- , _edges()
- { }
-
-/**
- * Connect this vertex to the vertex at the opposite end of this edge. Note
- * that this vertex is neither truly the source nor target of the edge. This
- * does not guarantee that source(e) == this.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-void
-undirected_vertex<VP,EP,V,E,VES>::connect_to(edge_descriptor e)
-{
- _edges.add(e);
-}
-
-/**
- * Connect this vertex to the vertex at the opposite end of the edge. Note that
- * this does not guarantee that the target(e) == this.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-void
-undirected_vertex<VP,EP,V,E,VES>::connect_from(edge_descriptor e)
-{
- _edges.add(e);
-}
-
-/**
- * Locally remove the given edge that connects this vertex to another endpoint.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-void
-undirected_vertex<VP,EP,V,E,VES>::disconnect_to(edge_descriptor e)
-{
- _edges.remove(e);
-}
-
-/**
- * Locally remove the given edge that connects this vertex to another endpoint.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-void
-undirected_vertex<VP,EP,V,E,VES>::disconnect_from(edge_descriptor e)
-{
- _edges.remove(e);
-}
-
-/**
- * Locally disconnect of all the incident edges from this vertex. Note that
- * this is really only used by the disconnect algorithm.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-void
-undirected_vertex<VP,EP,V,E,VES>::disconnect_all()
-{
- _edges.clear();
-}
-
-/**
- * Get an iterator range over the incident edges of this vertex.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-std::pair<
- typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator,
- typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator
- >
-undirected_vertex<VP,EP,V,E,VES>::incident_edges() const
-{
- return std::make_pair(_edges.begin(), _edges.end());
-}
-
-/**
- * Get an iterator to the first incident edge.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator
-undirected_vertex<VP,EP,V,E,VES>::begin_incident_edges() const
-{
- return _edges.begin();
-}
-
-/**
- * Get an iterator pas the end of the incident edges.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-typename undirected_vertex<VP,EP,V,E,VES>::incident_edge_iterator
-undirected_vertex<VP,EP,V,E,VES>::end_incident_edges() const
-{
- return _edges.end();
-}
-
-/**
- * Return the degree of this vertex. The degree of the vertex is the number
- * of incident edges.
- */
-template <BOOST_GRAPH_UV_PARAMS>
-typename undirected_vertex<VP,EP,V,E,VES>::degree_type
-undirected_vertex<VP,EP,V,E,VES>::degree() const
-{
- return _edges.size();
-}
-
-/**
- * Disconnect the given vertex from the given graph. This is not part of the
- * public interface to this function.
- *
- * @todo This is actually kind of a generic algorithm.
- */
-template <typename Graph>
-void
-disconnect(Graph& g, typename Graph::vertex_type& u, undirected_tag)
-{
- // Undirected - iterate over each of the incident edges I and get the
- // opposite vertex w. Remove all edges from the adjacent vertex that
- // connect to v. Remove all edges I from E.
-
- typedef typename Graph::vertex_type vertex;
- typedef typename vertex::descriptor_type vertex_descriptor;
-
- typedef typename Graph::edge_type edge;
- typedef typename edge::descriptor_type edge_descriptor;
- // typedef typename Graph::edge_store edge_store;
-
- typedef typename vertex::incident_edge_iterator incidence_iterator;
-
- // Get a descriptor for this vertex.
- vertex_descriptor ud = g.descriptor(u);
-
- incidence_iterator
- i = u.begin_incident_edges(),
- end = u.end_incident_edges();
- for( ; i != end; ++i) {
- // Get the vertex at the opposite end of the current edge.
- edge_descriptor ed = *i;
- edge& e = g.edge(ed);
- vertex& v = g.vertex(e.opposite(ud));
-
- // Remove the edge containing this vertex from v.
- v.disconnect_from(ed);
-
- // Remove this edge from the graph's edge set. Note that this is
- // basically just discards the edge from the edge set without actually
- // trying to disconnect it from the edges.
- g.template Graph::edge_store::remove_edge(ed);
- }
- u.disconnect_all();
-}
-
-#undef BOOST_GRAPH_UV_PARAMS
-
-// Edge Functions
-
-#define BOOST_GRAPH_UE_PARAMS \
- typename VP, typename EP, typename V, typename E
-
-template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge()
- : edge<EP>()
- , _ends()
-{ }
-
-template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge(properties_type const& ep)
- : edge<EP>(ep)
- , _ends()
-{ }
-
-template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u, vertex_descriptor v)
- : edge<EP>()
- , _ends(u, v)
-{ }
-
-template <BOOST_GRAPH_UE_PARAMS>
-undirected_edge<VP,EP,V,E>::undirected_edge(vertex_descriptor u,
- vertex_descriptor v,
- properties_type const& ep)
- : edge<EP>(ep)
- , _ends(u, v)
-{ }
-
-/**
- * Return the endpoints of the edge.
- */
-template <BOOST_GRAPH_UE_PARAMS>
-unordered_pair<typename undirected_edge<VP,EP,V,E>::vertex_descriptor> const&
-undirected_edge<VP,EP,V,E>::ends() const
-{ return _ends; }
-
-/**
- * Return the source of this edge. The source of an undirected edge is not
- * necessarily the same as the way it is connected.
- */
-template <BOOST_GRAPH_UE_PARAMS>
-typename undirected_edge<VP,EP,V,E>::vertex_descriptor
-undirected_edge<VP,EP,V,E>::source() const
-{ return _ends.first(); }
-
-/**
- * Return the target of this edge. The source of an undirected edge is not
- * necessarily the same as the way it is connected.
- */
-template <BOOST_GRAPH_UE_PARAMS>
-typename undirected_edge<VP,EP,V,E>::vertex_descriptor
-undirected_edge<VP,EP,V,E>::target() const
-{ return _ends.second(); }
-
-/**
- * Return the vertex opposite the given vertex on this edge.
- */
-template <BOOST_GRAPH_UE_PARAMS>
-typename undirected_edge<VP,EP,V,E>::vertex_descriptor
-undirected_edge<VP,EP,V,E>::opposite(vertex_descriptor u) const
-{
- return u == _ends.first() ? _ends.second() : _ends.first();
-}
-
-// Operators
-
-// @todo I don't know that I like this. It might be better to build these
-// operators as functors and then typedef them into the edge type rather than
-// simply make these the default operators for the edges.
-
-/**
- * Edges can be ordered by their end points. This is a lexicographical
- * comparison of the vertex descriptors in the ends of the edge.
- */
-template <BOOST_GRAPH_UE_PARAMS>
-bool
-operator<(undirected_edge<VP,EP,V,E> const& a,
- undirected_edge<VP,EP,V,E> const& b)
-{
- return a.ends() < b.ends();
-}
-
-/**
- * Edges are also equality comparable by their end points. Note that this does
- * /not/ compare the properties of vertices.
- */
-template <BOOST_GRAPH_UE_PARAMS>
-bool
-operator==(undirected_edge<VP,EP,V,E> const& a,
- undirected_edge<VP,EP,V,E> const& b)
-{
- return a.ends() == b.ends();
-}
-
-#undef BOOST_GRAPH_UE_PARAMS
-
} /* namespace adj_list */
} /* namespace graphs */
} /* namespace boost */
+#include <boost/graphs/adjacency_list/undirected/vertex.hpp>
+#include <boost/graphs/adjacency_list/undirected/edge.hpp>
+
#endif
Added: sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/vertex.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/boost/graphs/adjacency_list/undirected/vertex.hpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -0,0 +1,231 @@
+
+#ifndef BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_VERTEX_HPP
+#define BOOST_GRAPHS_ADJACENCY_LIST_UNDIRECTED_VERTEX_HPP
+
+#include <boost/graphs/adjacency_list/vertex.hpp>
+
+namespace boost {
+namespace graphs {
+namespace adj_list {
+
+/**
+ * An undirected vertex tracks the incident edges of the given vertex. Note
+ * that the edges actually being stored are pointers to edges in the graph's
+ * edge list. The reason for this is so we don't duplicate the properties
+ * of each edge.
+ *
+ * @todo What happens if I store incident edges as a pair... The edge and the
+ * opposite end. That might be kind of interesting.
+ */
+template <
+ typename VertexProps,
+ typename EdgeProps,
+ typename VertexDesc,
+ typename EdgeDesc,
+ template <typename> class VertexEdgeStore
+ >
+class undirected_vertex
+ : public vertex<VertexProps>
+{
+public:
+ typedef VertexDesc descriptor_type;
+ typedef EdgeDesc edge_descriptor;
+ typedef typename vertex<VertexProps>::properties_type properties_type;
+private:
+ typedef VertexEdgeStore<edge_descriptor> vertex_edge_store;
+public:
+ // Edge iterator types
+ typedef typename vertex_edge_store::const_iterator incidence_iterator;
+ typedef std::pair<incidence_iterator, incidence_iterator> incidence_range;
+ typedef typename vertex_edge_store::size_type degree_type;
+
+ undirected_vertex();
+ undirected_vertex(VertexProps const& vp);
+
+ // Connection interface.
+ void connect_to(edge_descriptor e);
+ void connect_from(edge_descriptor e);
+
+ // Disconnection interface.
+ void disconnect_to(edge_descriptor e);
+ void disconnect_from(edge_descriptor e);
+ void disconnect_all();
+
+ std::pair<incidence_iterator, incidence_iterator> incident_edges() const;
+ incidence_iterator begin_incident_edges() const;
+ incidence_iterator end_incident_edges() const;
+
+ degree_type degree() const;
+
+private:
+ vertex_edge_store _edges;
+};
+
+// Functions
+
+#define BOOST_GRAPH_UV_PARAMS \
+ typename VP, typename EP, typename V, typename E, template <typename> class VES
+
+template <BOOST_GRAPH_UV_PARAMS>
+undirected_vertex<VP,EP,V,E,VES>::undirected_vertex()
+ : vertex<VP>()
+ , _edges()
+{ }
+
+template <BOOST_GRAPH_UV_PARAMS>
+undirected_vertex<VP,EP,V,E,VES>::undirected_vertex(VP const& vp)
+ : vertex<VP>(vp)
+ , _edges()
+ { }
+
+/**
+ * Connect this vertex to the vertex at the opposite end of this edge. Note
+ * that this vertex is neither truly the source nor target of the edge. This
+ * does not guarantee that source(e) == this.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::connect_to(edge_descriptor e)
+{
+ _edges.add(e);
+}
+
+/**
+ * Connect this vertex to the vertex at the opposite end of the edge. Note that
+ * this does not guarantee that the target(e) == this.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::connect_from(edge_descriptor e)
+{
+ _edges.add(e);
+}
+
+/**
+ * Locally remove the given edge that connects this vertex to another endpoint.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::disconnect_to(edge_descriptor e)
+{
+ _edges.remove(e);
+}
+
+/**
+ * Locally remove the given edge that connects this vertex to another endpoint.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::disconnect_from(edge_descriptor e)
+{
+ _edges.remove(e);
+}
+
+/**
+ * Locally disconnect of all the incident edges from this vertex. Note that
+ * this is really only used by the disconnect algorithm.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+void
+undirected_vertex<VP,EP,V,E,VES>::disconnect_all()
+{
+ _edges.clear();
+}
+
+/**
+ * Get an iterator range over the incident edges of this vertex.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+std::pair<
+ typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator,
+ typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator
+ >
+undirected_vertex<VP,EP,V,E,VES>::incident_edges() const
+{
+ return std::make_pair(_edges.begin(), _edges.end());
+}
+
+/**
+ * Get an iterator to the first incident edge.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator
+undirected_vertex<VP,EP,V,E,VES>::begin_incident_edges() const
+{
+ return _edges.begin();
+}
+
+/**
+ * Get an iterator pas the end of the incident edges.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+typename undirected_vertex<VP,EP,V,E,VES>::incidence_iterator
+undirected_vertex<VP,EP,V,E,VES>::end_incident_edges() const
+{
+ return _edges.end();
+}
+
+/**
+ * Return the degree of this vertex. The degree of the vertex is the number
+ * of incident edges.
+ */
+template <BOOST_GRAPH_UV_PARAMS>
+typename undirected_vertex<VP,EP,V,E,VES>::degree_type
+undirected_vertex<VP,EP,V,E,VES>::degree() const
+{
+ return _edges.size();
+}
+
+/**
+ * Disconnect the given vertex from the given graph. This is not part of the
+ * public interface to this function.
+ *
+ * @todo This is actually kind of a generic algorithm.
+ */
+template <typename Graph>
+void
+disconnect(Graph& g, typename Graph::vertex_type& u, undirected_tag)
+{
+ // Undirected - iterate over each of the incident edges I and get the
+ // opposite vertex w. Remove all edges from the adjacent vertex that
+ // connect to v. Remove all edges I from E.
+
+ typedef typename Graph::vertex_type vertex;
+ typedef typename vertex::descriptor_type vertex_descriptor;
+
+ typedef typename Graph::edge_type edge;
+ typedef typename edge::descriptor_type edge_descriptor;
+ // typedef typename Graph::edge_store edge_store;
+
+ typedef typename vertex::incidence_iterator incidence_iterator;
+
+ // Get a descriptor for this vertex.
+ vertex_descriptor ud = g.descriptor(u);
+
+ incidence_iterator
+ i = u.begin_incident_edges(),
+ end = u.end_incident_edges();
+ for( ; i != end; ++i) {
+ // Get the vertex at the opposite end of the current edge.
+ edge_descriptor ed = *i;
+ edge& e = g.edge(ed);
+ vertex& v = g.vertex(e.opposite(ud));
+
+ // Remove the edge containing this vertex from v.
+ v.disconnect_from(ed);
+
+ // Remove this edge from the graph's edge set. Note that this is
+ // basically just discards the edge from the edge set without actually
+ // trying to disconnect it from the edges.
+ g.template Graph::edge_store::remove_edge(ed);
+ }
+ u.disconnect_all();
+}
+
+#undef BOOST_GRAPH_UV_PARAMS
+
+} /* namespace adj_list */
+} /* namespace graphs */
+} /* namespace boost */
+
+#endif
Modified: sandbox/SOC/2008/graphs/libs/graphs/Jamfile
==============================================================================
--- sandbox/SOC/2008/graphs/libs/graphs/Jamfile (original)
+++ sandbox/SOC/2008/graphs/libs/graphs/Jamfile 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -2,4 +2,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
+exe bfs : bfs.cpp : <include>../../ <include>/usr/local/include ;
+exe incidence : incidence.cpp : <include>../../ <include>/usr/local/include ;
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-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -19,4 +19,12 @@
}
}
+template <typename Graph>
+void add_mapped_vertices(Graph& g, int n)
+{
+ for(int i = 0; i < n; ++i) {
+ g.add_vertex(i, i);
+ }
+}
+
#endif
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-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -5,6 +5,7 @@
#include <boost/graphs/adjacency_list.hpp>
+#include "demangle.hpp"
#include "add_vertices.hpp"
#include "add_edges.hpp"
@@ -47,6 +48,8 @@
Graph g;
add_vertices(g, V);
add_edges(g, E);
+
+ // cout << demangle(typeid(Graph::this_type).name()) << endl;
}
// Best used for fast graph construction. This graph supports vertex and edge
@@ -76,12 +79,15 @@
}
// Pretty much the same as above, but vertices are mapped to a key.
+//
+// The map here is basically int-to-int, and kind of worthless, but we're just
+// using this to make sure that the class instantiates correctly.
void undirected_map_set_set()
{
typedef adjacency_list<
- undirected, none, int, int_to_vertex_map, edge_set, vertex_edge_set
+ undirected, int, int, int_to_vertex_map, edge_set, vertex_edge_set
> Graph;
Graph g;
- add_vertices(g, V);
+ add_mapped_vertices(g, V);
}
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-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -57,7 +57,7 @@
void test_1()
{
- typedef graph<int, double, vertex_set> Graph;
+ typedef undirected_graph<int, double, vertex_set> Graph;
typedef exterior_vertex_property<Graph, color>::container_type ColorContainer;
typedef exterior_vertex_property<Graph, color>::map_type ColorMap;
@@ -90,7 +90,7 @@
void test_2()
{
- typedef graph<int, int, vertex_vector> Graph;
+ typedef undirected_graph<int, int, vertex_vector> Graph;
typedef exterior_vertex_property<Graph, color>::container_type ColorContainer;
Graph g;
@@ -112,7 +112,7 @@
void test_3()
{
- typedef graph<VertexProps, EdgeProps, vertex_list> Graph;
+ typedef undirected_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;
Added: sandbox/SOC/2008/graphs/libs/graphs/incidence.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/libs/graphs/incidence.cpp 2008-05-30 11:13:48 EDT (Fri, 30 May 2008)
@@ -0,0 +1,41 @@
+
+#include <iostream>
+
+#include <boost/graphs/adjacency_list.hpp>
+
+using namespace std;
+using namespace boost;
+using namespace boost::graphs;
+using namespace boost::graphs::adj_list;
+
+int main()
+{
+ typedef undirected_graph<int, int> Graph;
+ Graph g;
+
+ // Add a bunch of vertices.
+ for(int i = 0; i < 5; ++i) {
+ g.add_vertex(i);
+ }
+
+ // Connect them to create a star graph with 0 at the center.
+ g.add_edge(g.find_vertex(0), g.find_vertex(1), 10);
+ g.add_edge(g.find_vertex(0), g.find_vertex(2), 11);
+ g.add_edge(g.find_vertex(0), g.find_vertex(3), 12);
+ g.add_edge(g.find_vertex(0), g.find_vertex(4), 13);
+
+ cout << "verts: " << g.num_vertices() << endl;
+ cout << "edges: " << g.num_edges() << endl;
+
+ Graph::incidence_range ir = g.incident_edges(g.find_vertex(0));
+ for( ; ir.first != ir.second; ++ir.first) {
+ cout << "inc test: " << g.properties(*ir.first) << endl;
+ }
+
+ Graph::adjacency_range ar = g.adjacent_vertices(g.find_vertex(0));
+ for( ; ar.first != ar.second; ++ar.first) {
+ cout << "adj test: " << g.properties(*ar.first) << endl;
+ }
+
+ return 0;
+}