|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2008-07-03 08:26:15
Author: asutton
Date: 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
New Revision: 47035
URL: http://svn.boost.org/trac/boost/changeset/47035
Log:
Started bringing directed edge sets into line. They crash. Badly.
Added:
sandbox/SOC/2008/graphs/trunk/boost/graphs/mapped_iterator.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp | 8 ++--
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp | 2
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp | 25 +++++++++++-----
sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp | 6 +-
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp | 3 -
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp | 3 +
sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp | 47 ++++++++++++++++++++++-------
sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp | 61 +++++++++++++++++++++++----------------
sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp | 9 +++++
sandbox/SOC/2008/graphs/trunk/libs/graphs/di.cpp | 22 +++++++-------
11 files changed, 119 insertions(+), 70 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_edge.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -27,7 +27,7 @@
//@{
inline directed_edge()
: _src()
- , _out(0)
+ , _out()
{ }
inline directed_edge(vertex_descriptor v, OutIter o)
@@ -58,17 +58,17 @@
{ return _out; }
inline InIter in_edge() const
- { return _out->third.template get<InIter>(); }
+ { return (*_out).third.template get<InIter>(); }
/** @name Property Accessors
* Return the properties associated with the edge.
*/
//@{
inline edge_properties& properties()
- { return _out->second; }
+ { return (*_out).second; }
inline edge_properties const& properties() const
- { return _out->second; }
+ { return (*_out).second; }
//@}
private:
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_graph.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -81,7 +81,6 @@
typedef directed_edge<typename out_edge_store::iterator, typename in_edge_store::iterator> edge_descriptor;
// Generate the vertex type over the vertex properties, and in/out stores.
- // We can also pull size
// NOTE: Omitting the in-edge store allows us to create half-directed
// graphs.
typedef directed_vertex<vertex_properties, out_edge_store, in_edge_store> vertex_type;
@@ -525,8 +524,8 @@
void
directed_graph<VP,EP,VS,ES>::remove_edges(vertex_descriptor v)
{
- remove_out_edges(v);
remove_in_edges(v);
+ remove_out_edges(v);
}
/**
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/directed_vertex.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -201,7 +201,7 @@
{
// Get the input iterator from the edge.
out_iterator o = e.out_edge();
- in_iterator i = o->third.template get<in_iterator>();
+ in_iterator i = (*o).third.template get<in_iterator>();
_in.remove(i);
}
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_set.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -30,7 +30,7 @@
template <typename EdgeProps>
struct property_store
{
- typedef placeholder<sizeof(std::list<int>::iterator)> dummy_type;
+ typedef typename hold<std::list<int>::iterator>::type dummy_type;
typedef triple<EdgeProps, dummy_type, dummy_type> property;
typedef SecondAlloc<property> allocator;
typedef property_list<property, allocator> type;
@@ -52,22 +52,31 @@
template <typename VertexDesc, typename Props>
struct out_store
{
- typedef std::pair<VertexDesc, Props> out_pair;
+ // Define a dummy type that eventually be used to store iterators to
+ // in edge iterators. The actual out edge type is a tuple of target
+ // vertex, edge properties, and in edge iterator (placeheld). The in
+ // edge type is the source vertex and the out edge iterator (placeheld).
+ typedef typename hold<std::set<int>::iterator>::type dummy_type;
+ typedef triple<VertexDesc, Props, dummy_type> edge;
typedef Compare<VertexDesc> compare;
- typedef FirstAlloc<out_pair> allocator;
- typedef out_set<out_pair, compare, allocator> type;
+ typedef FirstAlloc<edge> allocator;
+ typedef out_set<edge, compare, allocator> type;
};
// The in store metafunction generates the type of list used to store
// incoming edges of directed graph. In edges are represented by the
// referencing vertex and an out edge descriptor.
- template <typename VertexDesc, typename OutDesc>
+ template <typename VertexDesc>
struct in_store
{
- typedef std::pair<VertexDesc, OutDesc> in_pair;
+ // Define a dummy type that will ultimately act as a placeholder for
+ // an iterator into the out edge vector. Use that to define the in edge
+ // pair.
+ typedef typename hold<typename std::set<int>::iterator>::type dummy_type;
+ typedef std::pair<VertexDesc, dummy_type> edge;
typedef Compare<VertexDesc> compare;
- typedef SecondAlloc<in_pair> allocator;
- typedef in_set<in_pair, compare, allocator> type;
+ typedef SecondAlloc<edge> allocator;
+ typedef in_set<edge, compare, allocator> type;
};
};
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/edge_vector.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -48,7 +48,7 @@
// Define a dummy type that will eventually container iterators into
// an incidence container. Use this as part of the triple for each
// edge store - the properties and "out-facing" iterators.
- typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
+ typedef typename hold<typename std::vector<int>::iterator>::type dummy_type;
typedef triple<EdgeProps, dummy_type, dummy_type> property;
typedef SecondAlloc<property> allocator;
typedef property_vector<property, allocator> type;
@@ -73,7 +73,7 @@
// in edge iterators. The actual out edge type is a tuple of target
// vertex, edge properties, and in edge iterator (placeheld). The in
// edge type is the source vertex and the out edge iterator (placeheld).
- typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
+ typedef typename hold<typename std::vector<int>::iterator>::type dummy_type;
typedef triple<VertexDesc, Props, dummy_type> edge;
typedef FirstAlloc<edge> allocator;
typedef out_vector<edge, allocator> type;
@@ -88,7 +88,7 @@
// Define a dummy type that will ultimately act as a placeholder for
// an iterator into the out edge vector. Use that to define the in edge
// pair.
- typedef placeholder<sizeof(typename std::vector<int>::iterator)> dummy_type;
+ typedef typename hold<typename std::vector<int>::iterator>::type dummy_type;
typedef std::pair<VertexDesc, dummy_type> edge;
typedef SecondAlloc<edge> allocator;
typedef in_vector<edge, allocator> type;
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_iterator.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -63,9 +63,8 @@
inline basic_in_iterator& operator--()
{ --_iter; return *this; }
- // Iterators are equivalent if they reference the same edge.
inline bool operator==(basic_in_iterator const& x) const
- { return **this == *x; }
+ { return (_base == x._base) && (_iter == x._iter); }
inline bool operator!=(basic_in_iterator const& x) const
{ return !this->operator==(x); }
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_list.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -51,7 +51,8 @@
}
/**
- * Find the edge with the given iterator.
+ * Find the edge with the given iterator. Is this function ever actually
+ * called? I have no idea...
* @complexity O(deg(u))
*/
iterator find(vertex_descriptor v) const
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/in_set.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -4,6 +4,8 @@
#include <map>
+#include "mapped_iterator.hpp"
+
/**
* The in-edge set references incoming edges from other vertices. Each edge
* can be uniquely identified by its source vertex and property descriptor.
@@ -17,12 +19,15 @@
public:
typedef Edge in_pair;
typedef typename Edge::first_type vertex_descriptor;
- typedef typename Edge::second_type out_descriptor;
private:
- typedef std::map<vertex_descriptor, out_descriptor, Compare, Alloc> store_type;
+ typedef typename Edge::second_type out_edge_place;
+ typedef std::map<
+ vertex_descriptor,
+ std::pair<vertex_descriptor const, out_edge_place>,
+ Compare, Alloc
+ > store_type;
public:
- typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
+ typedef mapped_iterator<typename store_type::iterator> iterator;
typedef typename store_type::size_type size_type;
in_set()
@@ -33,20 +38,29 @@
* Add the edge to the set.
* @complexity O(deg(u))
*/
- void add(in_pair e)
- { _edges.insert(e); }
+ iterator add(vertex_descriptor v)
+ {
+ return _edges.insert(std::make_pair(v,
+ std::make_pair(v, out_edge_place()))
+ ).first;
+ }
/** Find the edge with the given vertex. */
iterator find(vertex_descriptor v)
{ return _edges.find(v); }
- /** Find the edge with the given vertex. */
- const_iterator find(vertex_descriptor v) const
+ /**
+ * Find the edge with the given vertex. Is this function ever called?
+ */
+ iterator find(vertex_descriptor v) const
{ return _edges.find(v); }
- /** Remove the edge with the given descriptor. */
- void remove(vertex_descriptor v)
- { _edges.erase(find(v)); }
+ /**
+ * Remove the edge with the given descriptor.
+ * @complexity O(log(in-deg(v)))
+ */
+ void remove(iterator i)
+ { _edges.erase(i.iter); }
/** Remove all edges. */
void clear()
@@ -56,8 +70,17 @@
size_type size() const
{ return _edges.size(); }
+ /** @name Iterators */
+ //@{
+ inline iterator begin() const
+ { return _edges.begin(); }
+
+ inline iterator end() const
+ { return _edges.end(); }
+ //@}
+
private:
- store_type _edges;
+ mutable store_type _edges;
};
#endif
Added: sandbox/SOC/2008/graphs/trunk/boost/graphs/mapped_iterator.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/mapped_iterator.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -0,0 +1,54 @@
+
+#ifndef MAPPED_ITERATOR_HPP
+#define MAPPED_ITERATOR_HPP
+
+/**
+ * A map iterator adapter that returns references to the mapped edge.
+ */
+template <typename Iter>
+struct mapped_iterator
+{
+ typedef typename Iter::iterator_category iterator_category;
+ typedef typename Iter::difference_type difference_type;
+
+ // Deconstruct and reconstruct the value type. Yikes.
+ typedef typename Iter::value_type::second_type value_type;
+ typedef value_type& reference;
+ typedef value_type* pointer;
+
+ inline mapped_iterator()
+ : iter()
+ { }
+
+ inline mapped_iterator(Iter x)
+ : iter(x)
+ { }
+
+ inline mapped_iterator& operator++()
+ { ++iter; return *this; }
+
+ inline mapped_iterator& operator--()
+ { --iter; return *this; }
+
+ inline bool operator==(mapped_iterator const& x) const
+ { return iter == x.iter; }
+
+ inline bool operator!=(mapped_iterator const& x) const
+ { return !operator==(x); }
+
+ inline reference operator*()
+ { return iter->second; }
+
+ inline const reference operator*() const
+ { return iter->second; }
+
+ inline pointer operator->()
+ { return &iter->second; }
+
+ inline const pointer operator->() const
+ { return &iter->second; }
+
+ Iter iter;
+};
+
+#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/out_set.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -3,8 +3,11 @@
#define OUT_SET_HPP
#include <map>
+#include <memory>
-#include "out_descriptor.hpp"
+#include <boost/type_traits.hpp>
+
+#include "mapped_iterator.hpp"
/**
* The out set implements set-based, out-edge storage for directed graphs.
@@ -26,64 +29,72 @@
class out_set
{
public:
- typedef Edge out_pair;
+ typedef Edge out_tuple;
typedef typename Edge::first_type vertex_descriptor;
typedef typename Edge::second_type edge_properties;
private:
- typedef std::map<vertex_descriptor, edge_properties, Compare, Alloc> store_type;
+ typedef typename Edge::third_type in_edge_place;
+
+ // Reconstruct the edge triple into a key/value type thing for the map.
+ // Unfortunately, we're storing the descriptor twice, but this does make
+ // iteration and referencing a bit easier.
+ typedef std::map<
+ vertex_descriptor,
+ triple<vertex_descriptor, edge_properties, in_edge_place>,
+ Compare, Alloc
+ > store_type;
public:
- typedef typename store_type::iterator iterator;
- typedef typename store_type::const_iterator const_iterator;
+ typedef mapped_iterator<typename store_type::iterator> iterator;
typedef typename store_type::size_type size_type;
- typedef basic_out_descriptor<iterator> out_descriptor;
-
inline out_set()
: _edges()
{ }
/** Allow the edge insertion? */
- std::pair<out_descriptor, bool> allow(vertex_descriptor v)
- { return std::make_pair(out_descriptor(find(v)), true); }
+ std::pair<iterator, bool> allow(vertex_descriptor v) const
+ { return std::make_pair(_edges.find(v), true); }
- /** Add the edge to the set. */
- out_descriptor add(out_pair e)
- { return out_descriptor(_edges.insert(e).first); }
-
- /** Find the edge with the given vertex descriptor. */
- iterator find(vertex_descriptor v)
- { return _edges.find(v); }
+ /**
+ * Add the edge to the set.
+ * @complexity O(log(deg(v)))
+ */
+ iterator add(vertex_descriptor v, edge_properties const& ep)
+ { return _edges.insert(std::make_pair(v, make_triple(v, ep, in_edge_place()))).first; }
- /** Find the edge with the given vertex descriptor. */
- const_iterator find(vertex_descriptor v) const
+ /**
+ * Find the edge with the given vertex descriptor.
+ * @complexity O(log(deg(v)))
+ */
+ iterator find(vertex_descriptor v) const
{ return _edges.find(v); }
/**
* Remove the edge with the given vertex descriptor.
* @complexity O(log(deg(u)))
*/
- void remove(out_descriptor d)
+ void remove(iterator d)
{ _edges.erase(d.iter); }
/** Remove all edges. */
void clear()
{ _edges.clear(); }
- /** @name Iterators and Size */
+ /** @name Iterators */
//@{
- inline const_iterator begin() const
+ inline iterator begin() const
{ return _edges.begin(); }
- inline const_iterator end() const
- { return _edges.end(); }
+ inline iterator end() const
+ { return iterator(); }
+ //@}
/** Get the number of outgoing edges. */
inline size_type size() const
{ return _edges.size(); }
- //@{
private:
- store_type _edges;
+ mutable store_type _edges;
};
#endif
Modified: sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/boost/graphs/placeholder.hpp 2008-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -42,7 +42,7 @@
/** Get the value of the placeholder and return it as an object of type T. */
template <typename T>
- inline T get() const
+ inline T& get() const
{
BOOST_STATIC_ASSERT(sizeof(T) == N);
return *reinterpret_cast<T*>(mem);
@@ -51,4 +51,11 @@
mutable char mem[N];
};
+/** A metafunction to make declaring placeholders a little easier. */
+template <typename T>
+struct hold
+{
+ typedef placeholder<sizeof(T)> type;
+};
+
#endif
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-07-03 08:26:14 EDT (Thu, 03 Jul 2008)
@@ -204,7 +204,9 @@
g.add_edge(v, u);
g.remove_edges(u, v);
- BOOST_ASSERT(g.num_edges() == 0);
+ BOOST_ASSERT(g.num_edges() == 2);
+ BOOST_ASSERT(g.out_degree(v) == 2);
+ BOOST_ASSERT(g.in_degree(u) == 2);
}
template <typename Graph>
@@ -268,27 +270,25 @@
test_add_remove_vertices<Graph>();
test_add_remove_edges<Graph>();
test_disconnect_vertex<Graph>();
- /*
- // test_implicit_disconnect_vertex<Graph>();
- // test_add_multi_edges<Graph>();
- // test_remove_multi_edges<Graph>();
+ test_implicit_disconnect_vertex<Graph>();
+ test_add_multi_edges<Graph>();
+ test_remove_multi_edges<Graph>();
// test_incidence_iterator<Graph>();
// test_adjacency_iterator<Graph>();
- */
}
void set_set()
{
- /*
cout << "---- set/set ----" << endl;
typedef directed_graph<City, Road, vertex_set<>, edge_set<> > Graph;
test_add_remove_vertices<Graph>();
- // test_add_remove_edges<Graph>();
- // test_disconnect_vertex<Graph>();
- // test_implicit_disconnect_vertex<Graph>();
+ test_add_remove_edges<Graph>();
+ /*
+ test_disconnect_vertex<Graph>();
+ test_implicit_disconnect_vertex<Graph>();
test_add_multi_edges<Graph>();
- // test_remove_multi_edges<Graph>();
+ test_remove_multi_edges<Graph>();
// test_incidence_iterator<Graph>();
// test_adjacency_iterator<Graph>();
*/
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