|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r50086 - sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list
From: asutton_at_[hidden]
Date: 2008-12-03 12:14:09
Author: asutton
Date: 2008-12-03 12:14:08 EST (Wed, 03 Dec 2008)
New Revision: 50086
URL: http://svn.boost.org/trac/boost/changeset/50086
Log:
Removing dead code
Removed:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_list.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_multiset.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_set.hpp
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_vector.hpp
Text files modified:
sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/undirected_graph.hpp | 13 ++++++++++---
1 files changed, 10 insertions(+), 3 deletions(-)
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_list.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_list.hpp 2008-12-03 12:14:08 EST (Wed, 03 Dec 2008)
+++ (empty file)
@@ -1,90 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_EDGE_LIST_HPP
-#define BOOST_GRAPHS_ADJLIST_EDGE_LIST_HPP
-
-#include <list>
-
-#include <boost/descriptors.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-// Forward declarations
-template <typename, typename> class property_list;
-template <typename, typename> class incidence_list;
-template <typename, typename> class out_list;
-template <typename, typename> class in_list;
-
-// The edge list does two things. First, it indicates that edges will
-// be stored in an incidence list (as opposed to a vector or set).
-// Second, this will indicate the use of a global property list.
-// Again, as opposed to a vector.
-
-/**
- * The basic_edge_list is the outer part of the metafunctions that generate
- * types for adjacency lists.
- */
-template <
- template <typename> class FirstAlloc = std::allocator,
- template <typename> class SecondAlloc = std::allocator>
-struct edge_list
-{
- // A couple of dummy vectors used to build descriptors.
- typedef std::list<int, FirstAlloc<int>> first_dummy;
- typedef std::list<int, SecondAlloc<int>> second_dummy;
-
- // Descriptor types for undirected graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type label_descriptor;
-
- // The property store metafunction generates the underlying global store
- // type for edge label in undirected graphs.
- template <typename VertexDesc, typename EdgeProps>
- struct property_store
- {
- typedef std::pair<VertexDesc, incidence_descriptor> end;
- typedef std::pair<EdgeProps, std::pair<end, end>> edge;
- typedef SecondAlloc<edge> allocator;
- typedef property_list<edge, allocator> type;
- };
-
- // The incidence store metafunction generates the per-vertex storage type
- // for undirected vertices.
- template <typename VertexDesc>
- struct incidence_store
- {
- typedef std::pair<VertexDesc, label_descriptor> incidence_pair;
- typedef FirstAlloc<incidence_pair> allocator;
- typedef incidence_list<incidence_pair, allocator > type;
- };
-
-
-
- // Descriptor types for directed graphs
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
- // The out store metafunction generates the type of list used to store
- // out edges of a vertex in a directed graph.
- template <typename VertexDesc, typename EdgeProps>
- struct out_store
- {
- typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
- typedef FirstAlloc<edge> allocator;
- typedef out_list<edge, 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>
- struct in_store
- {
- typedef std::pair<VertexDesc, out_descriptor> edge;
- typedef SecondAlloc<edge> allocator;
- typedef in_list<edge, allocator> type;
- };
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_multiset.hpp
==============================================================================
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_set.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_set.hpp 2008-12-03 12:14:08 EST (Wed, 03 Dec 2008)
+++ (empty file)
@@ -1,102 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_EDGE_SET_HPP
-#define BOOST_GRAPHS_ADJLIST_EDGE_SET_HPP
-
-#include <list>
-#include <map>
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-// Forward declarations
-template <typename, typename> class property_list;
-template <typename, typename, typename> class incidence_set;
-template <typename, typename, typename> class out_set;
-template <typename, typename, typename> class in_set;
-
-/**
- * The edge set metafunction defines the basic facets of set-based edge
- * storage. Edge sets are best used to implement simple graphs (that do not
- * allow multiple edges).
- *
- * @param Compare - A unary template class that compares vertex descriptors.
- * @param FirstAlloc - An allocator template for either incident edges or out edges.
- * @param SecondAlloc - An allocator template for either global label or in edges.
- */
-template <
- template <typename> class Compare = std::less,
- template <typename> class FirstAlloc = std::allocator,
- template <typename> class SecondAlloc = std::allocator>
-struct edge_set
-{
- // Several dummy containers used to build descriptors. This looks really
- // weird since we're expecting a set type somewhere around here. However,
- // there isn't actually a real "set" used in these stores. The property
- // store only needs to be a list, and the incidence/in/out stores are
- // actually all maps (vertex to something).
- typedef std::map<int, int, Compare<int>, FirstAlloc<int>> first_dummy;
- typedef std::map<int, int, Compare<int>, SecondAlloc<int>> second_dummy;
- typedef std::list<int, SecondAlloc<int>> prop_dummy;
-
- // Descriptor types for undirected graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
- typedef typename descriptor_traits<prop_dummy>::descriptor_type label_descriptor;
-
- // The property store metafunnction generates the global store type for
- // undirected graphs. The property list only needs to be a list, not a set.
- template <typename VertexDesc, typename EdgeProps>
- struct property_store
- {
- typedef std::pair<VertexDesc, incidence_descriptor> end;
- typedef std::pair<EdgeProps, std::pair<end, end>> edge;
- typedef SecondAlloc<edge> allocator;
- typedef property_list<edge, allocator> type;
- };
-
- // The incidence store metafunction generates the per-vertex stores for
- // incident edges.
- template <typename VertexDesc>
- struct incidence_store
- {
- typedef std::pair<VertexDesc, label_descriptor> value;
- typedef Compare<VertexDesc> compare;
- typedef FirstAlloc<value> allocator;
- typedef incidence_set<value, compare, allocator> type;
- };
-
-
-
- // Descriptor types for directed graphs
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
- // The out store metafunction generates the type of set used to store out
- // edges of a vertex in a directed graph.
- template <typename VertexDesc, typename EdgeProps>
- struct out_store
- {
- typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
- typedef Compare<VertexDesc> compare;
- 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>
- struct in_store
- {
- typedef std::pair<VertexDesc, out_descriptor> edge;
- typedef Compare<VertexDesc> compare;
- typedef SecondAlloc<edge> allocator;
- typedef in_set<edge, compare, allocator> type;
- };
-};
-
-} } }
-
-#endif
-
Deleted: sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_vector.hpp
==============================================================================
--- sandbox/SOC/2008/graphs/trunk/libs/graphs/include/boost/graphs/adjacency_list/edge_vector.hpp 2008-12-03 12:14:08 EST (Wed, 03 Dec 2008)
+++ (empty file)
@@ -1,103 +0,0 @@
-
-#ifndef BOOST_GRAPHS_ADJLIST_EDGE_VECTOR_HPP
-#define BOOST_GRAPHS_ADJLIST_EDGE_VECTOR_HPP
-
-#include <boost/triple.hpp>
-#include <boost/descriptors.hpp>
-
-namespace boost { namespace graphs { namespace adjacency_list {
-
-// Forward declarations
-template <typename, typename> class property_vector;
-template <typename, typename> class incidence_vector;
-template <typename, typename> class out_vector;
-template <typename, typename> class in_vector;
-
-// What's in an edge vector? Basically, an edge vector has to specify
-// the type of property storage and the type of incidence storage. What
-// are the possible parameters to edge storage?
-// 1. The edge label
-// 2. Allocator for the property store
-// 3. Allocator for the incidence store
-
-// How does this generalize for directed graphs? Well... It would essentially
-// rely on variadic templates - or rather variadic template templates. The
-// goal would be to write something like: edge_vector<A, B, C> where A, B, and
-// C are actually interpreted by the callers of the metafunctions - it ain't
-// pretty, but it may actually work.
-
-/**
- * The basic_edge_vector is the outer part of the metafunctions that generate
- * types for adjacency lists.
- *
- * This is not the prettiest solution, but it does reuse the same outer
- * metafunction for both directed and undirected graphs. The meaning of the
- * first and second allocator differ depending on the type of graph. For
- * undirected graphs, FirstAlloc is the allocator for the per-vertex incidence
- * store and the SecondAlloc is the allocator for label. For directed
- * graphs, FirstAlloc and SecondAlloc are the per-vertex allocators for
- * out- and in-edge stores respectively.
- */
-template <
- template <typename> class FirstAlloc = std::allocator,
- template <typename> class SecondAlloc = std::allocator>
-struct edge_vector
-{
- // A couple of dummy vectors used to build descriptors.
- typedef std::vector<int, FirstAlloc<int>> first_dummy;
- typedef std::vector<int, SecondAlloc<int>> second_dummy;
-
- // Descriptor types for undirected graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type incidence_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type label_descriptor;
-
- // The property store metafunction generates the type of vector used to
- // store global label for undirected graphs.
- template <typename VertexDesc, typename EdgeProps>
- struct property_store
- {
- typedef std::pair<VertexDesc, incidence_descriptor> end;
- typedef std::pair<EdgeProps, std::pair<end, end>> edge;
- typedef SecondAlloc<edge> allocator;
- typedef property_vector<edge, allocator> type;
- };
-
- // The incidence store metafunction generates the type of vector used to
- // store edges incident to the an undirected vertex.
- template <typename VertexDesc>
- struct incidence_store
- {
- typedef std::pair<VertexDesc, label_descriptor> incidence_pair;
- typedef FirstAlloc<incidence_pair> incidence_allocator;
- typedef incidence_vector<incidence_pair, incidence_allocator> type;
- };
-
- // Descriptor types for directed graphs.
- typedef typename descriptor_traits<first_dummy>::descriptor_type out_descriptor;
- typedef typename descriptor_traits<second_dummy>::descriptor_type in_descriptor;
-
- // The out store metafunction generates the type of vector used to store
- // out edges of a vertex in a directed graph.
- template <typename VertexDesc, typename EdgeProps>
- struct out_store
- {
- typedef std::pair<VertexDesc, std::pair<EdgeProps, in_descriptor>> edge;
- typedef FirstAlloc<edge> allocator;
- typedef out_vector<edge, allocator> type;
- };
-
- // The in store metafunction generates the type of vector used to store
- // incoming edges of directed graph. In edges are represented by the
- // referencing vertex and an out edge descriptor.
- template <typename VertexDesc>
- struct in_store
- {
- typedef std::pair<VertexDesc, out_descriptor> edge;
- typedef SecondAlloc<edge> allocator;
- typedef in_vector<edge, allocator> type;
- };
-};
-
-} } } /* namespace boost::graphs::adjacency_list */
-
-#endif
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-12-03 12:14:08 EST (Wed, 03 Dec 2008)
@@ -270,13 +270,20 @@
typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor u,
typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v)
{
- // There doesn't seem to be a very clean implementation other than to
- // iterate over all the incident edges of u, find the corresponding edges
- // in v, and then erase all of the edge descriptors.
+ // Remove all edges u connected to v, while erasing the corresponding edge
+ // from the edge set. Then the the same for v.
incs::erase_all(vs::edges(g.v, u), v, detail::erase_edges(g.e));
incs::erase_all(vs::edges(g.v, v), u);
}
+/** Remove all edges incident to the given vertex. */
+template <typename VL, typename EL, typename VS, typename ES, typename IS>
+inline void
+remove_edges(undirected_graph<VL,EL,VS,ES,IS>& g,
+ typename undirected_graph<VL,EL,VS,ES,IS>::vertex_descriptor v)
+{
+}
+
/** Return the number of edges in the graph. */
template <typename VL, typename EL, typename VS, typename ES, typename IS>
inline typename undirected_graph<VL,EL,VS,ES,IS>::edges_size_type
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