Subject: [Boost-commit] svn:boost r50034 - in sandbox/SOC/2008/graphs/trunk/libs/graphs: include/boost/graphs/adjacency_list test
From: asutton_at_[hidden]
Date: 2008-11-30 08:33:44
Author: asutton
Date: 2008-11-30 08:33:43 EST (Sun, 30 Nov 2008)
New Revision: 50034
URL: http://svn.boost.org/trac/boost/changeset/50034
Log:
Finished implementing add_vertex.
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp | 4 +-
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp | 64 ++++++++++++++++++---------------------
sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp | 17 ++++++----
3 files changed, 42 insertions(+), 43 deletions(-)
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_store.hpp 2008-11-30 08:33:43 EST (Sun, 30 Nov 2008)
@@ -190,12 +190,12 @@
//@{
template <typename Store>
inline typename edge_store_traits<Store>::edge_label&
-label(Store& store, typename descriptor_traits<Store>::descriptor_type d)
+label(Store& store, typename edge_store_traits<Store>::edge_descriptor d)
{ return graphs::label(*make_iterator(store, d)); }
template <typename Store>
inline typename edge_store_traits<Store>::edge_label const&
-label(Store const& store, typename descriptor_traits<Store>::descriptor_type d)
+label(Store const& store, typename edge_store_traits<Store>::edge_descriptor d)
{ return graphs::label(*make_iterator(store, d)); }
//@}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp 2008-11-30 08:33:43 EST (Sun, 30 Nov 2008)
@@ -58,9 +58,9 @@
// TODO: Implement me
edge_label& operator[](edge_descriptor d)
- { return edge_label(); }
+ { return es::label(e, d); }
edge_label const& operator[](edge_descriptor d) const
- { return edge_label(); }
+ { return es::label(e, d); }
public:
vertex_store v;
@@ -149,23 +149,35 @@
{ return add_edge(g, u, v, typename undirected_graph<VL,EL,VS,ES,IS>::edge_label()); }
namespace detail {
- // Specialize the binding of edge descriptors into the vertex by recognizing
- // that only unique associative containers actually need to test the result
- // of the insertion before binding.
- template <typename VS, typename V, typename Ins, typename Tag>
- inline void bind_edges(VS& vs, V u, V v, Ins ins, Tag)
+ // Build the edge and bind the ends into the incidence stores of each
+ // vertex.
+ template <typename Graph, typename Vertex, typename Label>
+ inline typename Graph::edge_descriptor
+ do_add_edge(Graph& g, Vertex u, Vertex v, Label&& l)
{
- incs::insert(vs::edges(vs, u), v, ins.first);
- incs::insert(vs::edges(vs, v), u, ins.first);
+ std::pair<typename Graph::edge_descriptor, bool> x = es::insert(g.e, u, v, l);
+ incs::insert(vs::edges(g.v, u), v, x.first);
+ incs::insert(vs::edges(g.v, v), u, x.first);
+ return x.first;
}
- template <typename VS, typename V, typename Ins, typename Tag>
- inline void bind_edges(VS& vs, V u, V v, Ins ins, unique_associative_container_tag)
+ // For multigraphs, always add the edge.
+ template <typename Graph, typename Vertex, typename Label, typename Tag>
+ inline typename Graph::edge_descriptor
+ dispatch_add_edge(Graph& g, Vertex u, Vertex v, Label&& l, Tag)
+ { return do_add_edge(g, u, v, l); }
+
+ // For unique-edged graphs, we should be checking if the edge exists before
+ // actually adding it.
+ template <typename Graph, typename Vertex, typename Label>
+ inline typename Graph::edge_descriptor
+ dispatch_add_edge(Graph& g, Vertex u, Vertex v, Label&& l, unique_associative_container_tag)
{
- if(ins.second) {
- incs::insert(vs::edges(vs, u), ins.first);
- incs::insert(vs::edges(vs, v), ins.first);
+ typename Graph::edge_descriptor e = edge(u, v);
+ if(!e) {
+ e = do_add_edge(u, v);
}
+ return e;
}
} /* namespace detail */
@@ -176,26 +188,10 @@
typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v,
typename undirected_graph<VL,EL,VS,ES,IS>::edge_label&& l)
{
- typedef typename undirected_graph<VL,EL,VS,ES,IS>::edge_descriptor Edge;
-
- // This is not a great implementation... (or correct, really).
- std::pair<Edge, bool> x = es::insert(g.e, u, v, l);
- detail::bind_edges(g.v, u, v, x, container_category(g.e));
- return x.first;
-
- // What we should do follows: The primary reason for this is that
-#if NO_COMPILE
- if(has_unique_edges(*this)) { // obviously done at compile time
- Edge e = edge(u, v);
- if(e) return e;
- else {
- // See code above
- }
- }
- else {
- // See code above.
- }
-#endif
+ typedef typename container_traits<
+ typename undirected_graph<VL,EL,VS,ES,IS>::incidence_store
+ >::category Category;
+ return detail::dispatch_add_edge(g, u, v, l, Category());
}
//@}
Modified: sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp (original)
+++ sandbox/SOC/2008/graphs/trunk/libs/graphs/test/undirected.cpp 2008-11-30 08:33:43 EST (Sun, 30 Nov 2008)
@@ -64,6 +64,9 @@
{
arc() : n() { }
arc(int n) : n(n) { }
+
+ bool operator==(arc const& x) const { return n == x.n; }
+
int n;
};
@@ -147,11 +150,11 @@
Edge e1 = add_edge(g, u, v, arc(200));
Edge e2 = add_edge(g, v, w, arc(201));
Edge e3 = add_edge(g, w, u, arc(202));
+ BOOST_ASSERT(num_edges(g) == 3);
Edge t = edge(g, u, v);
BOOST_ASSERT(!t.is_null());
-
- BOOST_ASSERT(num_edges(g) == 3);
+ BOOST_ASSERT(g[t] == arc(200));
}
template <typename Graph>
@@ -175,10 +178,10 @@
typedef undirected_graph<node, arc, vertex_vector<>, edge_list<>, incidence_set<>> V_L_S;
test<V_V_V>();
-// test<L_V_V>();
-// test<S_V_V>();
-// test<M_V_V>();
-// test<V_L_L>();
-// test<V_L_S>();
+ test<L_V_V>();
+ test<S_V_V>();
+ test<M_V_V>();
+ test<V_L_L>();
+ test<V_L_S>();
}