|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-08-08 10:02:20
Author: asutton
Date: 2007-08-08 10:02:15 EDT (Wed, 08 Aug 2007)
New Revision: 38506
URL: http://svn.boost.org/trac/boost/changeset/38506
Log:
Implementing edge indexing for [un]directed graphs
Made a generic exterior_property that can be keyed over
vertices or edges.
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp | 130 +++++++++++++++++++++++++++---------
sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp | 44 +++++++++--
sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp | 141 ++++++++++++++++++++++++++++++---------
3 files changed, 238 insertions(+), 77 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp 2007-08-08 10:02:15 EDT (Wed, 08 Aug 2007)
@@ -23,13 +23,14 @@
class directed_graph
{
typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
+ typedef property<edge_index_t, unsigned, EdgeProperty> edge_property;
public:
typedef adjacency_list<listS,
listS,
bidirectionalS,
vertex_property,
- EdgeProperty,
+ edge_property,
GraphProperty,
listS> graph_type;
@@ -71,12 +72,14 @@
typedef typename graph_type::traversal_category traversal_category;
typedef unsigned vertex_index_type;
+ typedef unsigned edge_index_type;
inline directed_graph(const GraphProperty& p = GraphProperty())
: m_graph(p)
, m_num_vertices(0)
, m_num_edges(0)
, m_max_vertex_index(0)
+ , m_max_edge_index(0)
{}
inline directed_graph(const directed_graph& x)
@@ -84,6 +87,7 @@
, m_num_vertices(x.m_num_vertices)
, m_num_edges(x.m_num_edges)
, m_max_vertex_index(x.m_max_vertex_index)
+ , m_max_edge_index(x.m_max_edge_index)
{}
inline directed_graph(vertices_size_type n,
@@ -92,15 +96,17 @@
, m_num_vertices(n)
, m_num_edges(0)
, m_max_vertex_index(n)
+ , m_max_edge_index(0)
{}
inline directed_graph& operator =(const directed_graph& g)
{
if(&g != this) {
- m_graph = g.m_graph;
- m_num_vertices = g.m_num_vertices;
- m_num_edges = g.m_num_edges;
- m_max_vertex_index = g.m_max_vertex_index;
+ m_graph = g.m_graph;
+ m_num_vertices = g.m_num_vertices;
+ m_num_edges = g.m_num_edges;
+ m_max_vertex_index = g.m_max_vertex_index;
+ m_max_edge_index = g.m_max_edge_index;
}
return *this;
}
@@ -149,7 +155,9 @@
{
std::pair<edge_descriptor, bool> ret = boost::add_edge(u, v, m_graph);
if(ret.second) {
+ boost::put(edge_index, m_graph, ret.first, m_max_edge_index);
++m_num_edges;
+ ++m_max_edge_index;
}
return ret;
}
@@ -186,21 +194,46 @@
inline vertex_index_type max_vertex_index() const
{ return m_max_vertex_index; }
- inline void renumber_vertex_indices()
+ inline void
+ renumber_vertex_indices()
{
- vertex_iterator i, i_end;
- tie(i, i_end) = vertices(m_graph);
- m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
+ vertex_iterator i, end;
+ tie(i, end) = vertices(m_graph);
+ m_max_vertex_index = renumber_vertex_indices(i, end, 0);
}
- inline void remove_vertex_and_renumber_indices(vertex_iterator i)
+ inline void
+ remove_vertex_and_renumber_indices(vertex_iterator i)
{
- vertex_iterator j = next(i), j_end = vertices(m_graph).second;
+ vertex_iterator j = next(i), end = vertices(m_graph).second;
vertex_index_type n = get(vertex_index, m_graph, *i);
// remove the offending vertex and renumber everything after
remove_vertex(*i);
- m_max_vertex_index = renumber_vertex_indices(j, j_end, n);
+ m_max_vertex_index = renumber_vertex_indices(j, end, n);
+ }
+
+ inline edge_index_type
+ max_edge_index() const
+ { return m_max_edge_index; }
+
+ inline void
+ renumber_edge_indices()
+ {
+ edge_iterator i, end;
+ tie(i, end) = vertices(m_graph);
+ m_max_edge_index = renumber_edge_indices(i, end, 0);
+ }
+
+ inline void
+ remove_edge_and_renumber_indices(edge_iterator i)
+ {
+ edge_iterator j = next(i), end = vertices(m_graph).second;
+ edge_index_type n = get(edge_index, m_graph, *i);
+
+ // remove the offending edge and renumber everything after
+ remove_edge(*i);
+ m_max_edge_index = renumber_edge_indices(j, end, n);
}
// bundled property support
@@ -225,12 +258,25 @@
private:
inline vertices_size_type
renumber_vertex_indices(vertex_iterator i,
- vertex_iterator i_end,
+ vertex_iterator end,
vertices_size_type n)
{
- typename property_map<graph_type, vertex_index_t>::type
- indices = get(vertex_index, m_graph);
- for( ; i != i_end; ++i) {
+ typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
+ IndexMap indices = get(vertex_index, m_graph);
+ for( ; i != end; ++i) {
+ indices[*i] = n++;
+ }
+ return n;
+ }
+
+ inline vertices_size_type
+ renumber_edge_indices(edge_iterator i,
+ edge_iterator end,
+ vertices_size_type n)
+ {
+ typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
+ IndexMap indices = get(edge_index, m_graph);
+ for( ; i != end; ++i) {
indices[*i] = n++;
}
return n;
@@ -240,6 +286,7 @@
vertices_size_type m_num_vertices;
edges_size_type m_num_edges;
vertex_index_type m_max_vertex_index;
+ edge_index_type m_max_edge_index;
};
// IncidenceGraph concepts
@@ -592,36 +639,53 @@
}
#endif
+ // Vertex index management
+
template <class VP, class EP, class GP>
inline typename directed_graph<VP,EP,GP>::vertex_index_type
get_vertex_index(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
- const directed_graph<VP,EP,GP>& g)
- {
- return get(vertex_index, g, v);
- }
+ const directed_graph<VP,EP,GP>& g)
+ { return get(vertex_index, g, v); }
template <class VP, class EP, class GP>
typename directed_graph<VP,EP,GP>::vertex_index_type
max_vertex_index(const directed_graph<VP,EP,GP>& g)
- {
- return g.max_vertex_index();
- }
+ { return g.max_vertex_index(); }
template <class VP, class EP, class GP>
- void
+ inline void
renumber_vertex_indices(directed_graph<VP,EP,GP>& g)
- {
- g.renumber_vertex_indices();
- }
+ { g.renumber_vertex_indices(); }
template <class VP, class EP, class GP>
inline void
- remove_vertex_and_renumber_indices(
- typename directed_graph<VP,EP,GP>::vertex_iterator i,
- directed_graph<VP,EP,GP>& g)
- {
- g.remove_vertex_and_renumber_indices(i);
- }
+ remove_vertex_and_renumber_indices(typename directed_graph<VP,EP,GP>::vertex_iterator i,
+ directed_graph<VP,EP,GP>& g)
+ { g.remove_vertex_and_renumber_indices(i); }
+
+ // Edge index management
+
+ template <class VP, class EP, class GP>
+ inline typename directed_graph<VP,EP,GP>::edge_index_type
+ get_edge_index(typename directed_graph<VP,EP,GP>::edge_descriptor v,
+ const directed_graph<VP,EP,GP>& g)
+ { return get(edge_index, g, v); }
+
+ template <class VP, class EP, class GP>
+ typename directed_graph<VP,EP,GP>::edge_index_type
+ max_edge_index(const directed_graph<VP,EP,GP>& g)
+ { return g.max_edge_index(); }
+
+ template <class VP, class EP, class GP>
+ inline void
+ renumber_edge_indices(directed_graph<VP,EP,GP>& g)
+ { g.renumber_edge_indices(); }
+
+ template <class VP, class EP, class GP>
+ inline void
+ remove_edge_and_renumber_indices(typename directed_graph<VP,EP,GP>::edge_iterator i,
+ directed_graph<VP,EP,GP>& g)
+ { g.remove_edge_and_renumber_indices(i); }
}
#endif
Modified: sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/exterior_property.hpp 2007-08-08 10:02:15 EDT (Wed, 08 Aug 2007)
@@ -49,24 +49,48 @@
};
}
- template <typename Graph, typename Value>
- struct exterior_vertex_property
+ template <typename Graph, typename Key, typename Value>
+ struct exterior_property
{
- typedef typename graph_traits<Graph>::vertex_descriptor key_type;
+ typedef Key key_type;
typedef Value value_type;
typedef std::vector<Value> container_type;
- typedef detail::vector_matrix<Graph, key_type, Value> matrix_type;
- typedef container_property_map<Graph, container_type, key_type> map_type;
+ typedef detail::vector_matrix<Graph, Key, Value> matrix_type;
+ typedef container_property_map<Graph, container_type, Key> map_type;
+
+ private:
+ exterior_property() { }
+ exterior_property(const exterior_property&) { }
+ };
+
+ template <typename Graph, typename Value>
+ struct exterior_vertex_property
+ {
+ typedef exterior_property<
+ Graph,
+ typename graph_traits<Graph>::vertex_descriptor,
+ Value
+ > property_type;
+ typedef typename property_type::key_type key_type;
+ typedef typename property_type::value_type value_type;
+ typedef typename property_type::container_type container_type;
+ typedef typename property_type::matrix_type matrix_type;
+ typedef typename property_type::map_type map_type;
};
template <typename Graph, typename Value>
struct exterior_edge_property
{
- typedef typename graph_traits<Graph>::edge_descriptor key_type;
- typedef Value value_type;
- typedef std::vector<Value> container_type;
- typedef detail::vector_matrix<Graph, key_type, Value> matrix_type;
- typedef container_property_map<Graph, container_type, key_type> map_type;
+ typedef exterior_property<
+ Graph,
+ typename graph_traits<Graph>::edge_descriptor,
+ Value
+ > property_type;
+ typedef typename property_type::key_type key_type;
+ typedef typename property_type::value_type value_type;
+ typedef typename property_type::container_type container_type;
+ typedef typename property_type::matrix_type matrix_type;
+ typedef typename property_type::map_type map_type;
};
template <typename Matrix>
Modified: sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp 2007-08-08 10:02:15 EDT (Wed, 08 Aug 2007)
@@ -15,21 +15,19 @@
{
struct undirected_graph_tag {};
- template <
- typename VertexProperty = no_property,
- typename EdgeProperty = no_property,
- typename GraphProperty = no_property
- >
+ template <typename VertexProperty = no_property,
+ typename EdgeProperty = no_property,
+ typename GraphProperty = no_property>
class undirected_graph
{
typedef property<vertex_index_t, unsigned, VertexProperty> vertex_property;
-
+ typedef property<edge_index_t, unsigned, EdgeProperty> edge_property;
public:
typedef adjacency_list<listS,
listS,
undirectedS,
vertex_property,
- EdgeProperty,
+ edge_property,
GraphProperty,
listS> graph_type;
@@ -71,12 +69,14 @@
typedef typename graph_type::traversal_category traversal_category;
typedef unsigned vertex_index_type;
+ typedef unsigned edge_index_type;
inline undirected_graph(const GraphProperty& p = GraphProperty())
: m_graph(p)
, m_num_vertices(0)
, m_num_edges(0)
, m_max_vertex_index(0)
+ , m_max_edge_index(0)
{}
inline undirected_graph(const undirected_graph& x)
@@ -84,23 +84,25 @@
, m_num_vertices(x.m_num_vertices)
, m_num_edges(x.m_num_edges)
, m_max_vertex_index(x.m_max_vertex_index)
+ , m_max_edge_index(x.m_max_edge_index)
{}
inline undirected_graph(vertices_size_type n,
- const GraphProperty& p = GraphProperty())
+ const GraphProperty& p = GraphProperty())
: m_graph(n, p)
, m_num_vertices(n)
, m_num_edges(0)
, m_max_vertex_index(n)
+ , m_max_edge_index(0)
{}
inline undirected_graph& operator =(const undirected_graph& g)
{
if(&g != this) {
- m_graph = g.m_graph;
- m_num_vertices = g.m_num_vertices;
- m_num_edges = g.m_num_edges;
- m_max_vertex_index = g.m_max_vertex_index;
+ m_graph = g.m_graph;
+ m_num_vertices = g.m_num_vertices;
+ m_num_edges = g.m_num_edges;
+ m_max_vertex_index = g.m_max_vertex_index;
}
return *this;
}
@@ -149,7 +151,9 @@
{
std::pair<edge_descriptor, bool> ret = boost::add_edge(u, v, m_graph);
if(ret.second) {
+ boost::put(edge_index, m_graph, ret.first, m_max_edge_index);
++m_num_edges;
+ ++m_max_edge_index;
}
return ret;
}
@@ -193,14 +197,43 @@
m_max_vertex_index = renumber_vertex_indices(i, i_end, 0);
}
- inline void remove_vertex_and_renumber_indices(vertex_iterator i)
+ inline void
+ remove_vertex_and_renumber_indices(vertex_iterator i)
{
- vertex_iterator j = next(i), j_end = vertices(m_graph).second;
+ vertex_iterator j = next(i), end = vertices(m_graph).second;
vertex_index_type n = get(vertex_index, m_graph, *i);
// remove the offending vertex and renumber everything after
remove_vertex(*i);
- m_max_vertex_index = renumber_vertex_indices(j, j_end, n);
+ m_max_vertex_index = renumber_vertex_indices(j, end, n);
+ }
+
+
+ inline edge_index_type max_edge_index() const
+ { return m_max_edge_index; }
+
+ inline void renumber_edge_indices()
+ {
+ edge_iterator i, end;
+ tie(i, end) = edges(m_graph);
+ m_max_edge_index = renumber_edge_indices(i, end, 0);
+ }
+
+ inline void
+ remove_edge_and_renumber_indices(edge_iterator i)
+ {
+ edge_iterator j = next(i), end = edges(m_graph.second);
+ edge_index_type n = get(edge_index, m_graph, *i);
+
+ // remove the edge and renumber everything after it
+ remove_edge(*i);
+ m_max_edge_index = renumber_edge_indices(j, end, n);
+ }
+
+ inline void renumber_indices()
+ {
+ renumber_vertex_indices();
+ renumber_edge_indices();
}
// bundled property support
@@ -225,12 +258,25 @@
private:
inline vertices_size_type
renumber_vertex_indices(vertex_iterator i,
- vertex_iterator i_end,
+ vertex_iterator end,
vertices_size_type n)
{
- typename property_map<graph_type, vertex_index_t>::type
- indices = get(vertex_index, m_graph);
- for( ; i != i_end; ++i) {
+ typedef typename property_map<graph_type, vertex_index_t>::type IndexMap;
+ IndexMap indices = get(vertex_index, m_graph);
+ for( ; i != end; ++i) {
+ indices[*i] = n++;
+ }
+ return n;
+ }
+
+ inline edges_size_type
+ renumber_edge_indices(edge_iterator i,
+ edge_iterator end,
+ edges_size_type n)
+ {
+ typedef typename property_map<graph_type, edge_index_t>::type IndexMap;
+ IndexMap indices = get(edge_index, m_graph);
+ for( ; i != end; ++i) {
indices[*i] = n++;
}
return n;
@@ -240,6 +286,7 @@
vertices_size_type m_num_vertices;
edges_size_type m_num_edges;
vertex_index_type m_max_vertex_index;
+ edge_index_type m_max_edge_index;
};
// IncidenceGraph concepts
@@ -612,36 +659,62 @@
}
#endif
+ // Vertex index management
+
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::vertex_index_type
get_vertex_index(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
- const undirected_graph<VP,EP,GP>& g)
- {
- return get(vertex_index, g, v);
- }
+ const undirected_graph<VP,EP,GP>& g)
+ { return get(vertex_index, g, v); }
template <class VP, class EP, class GP>
typename undirected_graph<VP,EP,GP>::vertex_index_type
max_vertex_index(const undirected_graph<VP,EP,GP>& g)
- {
- return g.max_vertex_index();
- }
+ { return g.max_vertex_index(); }
template <class VP, class EP, class GP>
- void
+ inline void
renumber_vertex_indices(undirected_graph<VP,EP,GP>& g)
- {
- g.renumber_vertex_indices();
- }
+ { g.renumber_vertex_indices(); }
+
+ template <class VP, class EP, class GP>
+ inline void
+ remove_vertex_and_renumber_indices(typename undirected_graph<VP,EP,GP>::vertex_iterator i,
+ undirected_graph<VP,EP,GP>& g)
+ { g.remove_vertex_and_renumber_indices(i); }
+
+
+ // Edge index management
+
+ template <class VP, class EP, class GP>
+ inline typename undirected_graph<VP,EP,GP>::edge_index_type
+ get_edge_index(typename undirected_graph<VP,EP,GP>::edge_descriptor v,
+ const undirected_graph<VP,EP,GP>& g)
+ { return get(edge_index, g, v); }
+
+ template <class VP, class EP, class GP>
+ typename undirected_graph<VP,EP,GP>::edge_index_type
+ max_edge_index(const undirected_graph<VP,EP,GP>& g)
+ { return g.max_edge_index(); }
template <class VP, class EP, class GP>
inline void
- remove_vertex_and_renumber_indices(
- typename undirected_graph<VP,EP,GP>::vertex_iterator i,
- undirected_graph<VP,EP,GP>& g)
+ renumber_edge_indices(undirected_graph<VP,EP,GP>& g)
{
- g.remove_vertex_and_renumber_indices(i);
+ g.renumber_edge_indices();
}
+
+ template <class VP, class EP, class GP>
+ inline void
+ remove_edge_and_renumber_indices(typename undirected_graph<VP,EP,GP>::edge_iterator i,
+ undirected_graph<VP,EP,GP>& g)
+ { g.remove_edge_and_renumber_indices(i); }
+
+ // Index management
+ template <class VP, class EP, class GP>
+ inline void
+ renumber_indices(undirected_graph<VP,EP,GP>& g)
+ { g.renumber_indices(); }
}
#endif
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