|
|
Boost-Commit : |
From: asutton_at_[hidden]
Date: 2007-05-22 10:05:22
Author: asutton
Date: 2007-05-22 10:05:21 EDT (Tue, 22 May 2007)
New Revision: 4175
URL: http://svn.boost.org/trac/boost/changeset/4175
Log:
added a graph_as_matrix adapter. this really just implementes the edges() function
for adjacency_lists, undirected_graphs and directed_graphs. it should be optimized
to use minimal degree iterations for bidirectional and undirected graphs.
changed default type selectors of [un]directed_graph from vecS to listS in order
to satisfy more general purpose problems - listS provides the most iterator and
descriptor stability.
implemented the adjacent_vertices() method (i forgot to satisfy that concept
earlier) for both [un]directed graphs.
Added:
sandbox/SOC/2007/graphs/boost/graph/graph_as_matrix.hpp
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/directed_graph.hpp | 35 +++++++++++++++++++++++++++++++-
sandbox/SOC/2007/graphs/boost/graph/undirected_graph.hpp | 42 +++++++++++++++++++++++++++++++++++++--
2 files changed, 72 insertions(+), 5 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-05-22 10:05:21 EDT (Tue, 22 May 2007)
@@ -19,8 +19,8 @@
class directed_graph
{
public:
- typedef adjacency_list<vecS,
- vecS,
+ typedef adjacency_list<listS,
+ listS,
bidirectionalS,
VertexProperty,
EdgeProperty,
@@ -78,6 +78,21 @@
: m_graph(n, p)
{}
+ // bundled property support
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+ vertex_bundled& operator [](vertex_descriptor v)
+ { return m_graph[v]; }
+
+ const vertex_bundled& operator [](vertex_descriptor v) const
+ { return m_graph[v]; }
+
+ edge_bundled& operator [](edge_descriptor e)
+ { return m_graph[e]; }
+
+ const edge_bundled& operator [](edge_descriptor e) const
+ { return m_graph[e]; }
+#endif
+
// Graph concepts
static inline vertex_descriptor null_vertex()
{ return type::null_vertex(); }
@@ -105,6 +120,10 @@
inline degree_size_type degree(vertex_descriptor v)
{ return boost::degree(v, m_graph); }
+ // AdjacencyGraph concepts
+ inline std::pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor v) const
+ { return boost::adjacent_vertices(v, m_graph); }
+
// VertexListGraph concepts
inline vertices_size_type num_vertices() const
{ return boost::num_vertices(m_graph); }
@@ -250,6 +269,18 @@
return g.in_edges(v);
}
+ // AdjacencyGraph concepts
+ template <class VP, class EP, class GP>
+ inline std::pair<
+ typename directed_graph<VP,EP,GP>::adjacency_iterator,
+ typename directed_graph<VP,EP,GP>::adjacency_iterator
+ >
+ adjacent_vertices(typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+ const directed_graph<VP,EP,GP>& g)
+ {
+ return g.adjacent_vertices(v);
+ }
+
// VertexListGraph concepts
template <class VP, class EP, class GP>
inline typename directed_graph<VP,EP,GP>::vertices_size_type
Added: sandbox/SOC/2007/graphs/boost/graph/graph_as_matrix.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2007/graphs/boost/graph/graph_as_matrix.hpp 2007-05-22 10:05:21 EDT (Tue, 22 May 2007)
@@ -0,0 +1,145 @@
+// (C) Copyright Andrew Sutton 2007
+//
+// Use, modification and distribution are subject to the
+// Boost Software License, Version 1.0 (See accompanying file
+// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
+
+#ifndef BOOST_GRPAPH_GRAPH_AS_MATRIX_HPP
+#define BOOST_GRPAPH_GRAPH_AS_MATRIX_HPP
+
+#include <utility>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/directed_graph.hpp>
+
+namespace boost
+{
+ // NOTE:
+ // The adjacency list must be a model of an incidence graph since it needs
+ // out_edge_iterator and out_edges().
+ //
+ // NOTE:
+ // This are _not_ constant time operations, but it is optimized (sort of) for
+ // the type of graph. If directed, there isn't much choice in search algorithm.
+ // Specifically, this will run in O(out_degree(u)). For bidirectional graphs,
+ // we can optimize somewhat and search either the out edges of u or the in
+ // edges of v for the requested edge. This will run in O(min{out_degree(u), in_degree(v)}).
+ // A clever trick... Likewise, for undirected graphs, we can search either
+ // the out edges of u or v so it runs in O(min{out_degree(u), out_degree(v)}).
+
+ template <typename OEL, typename VL, typename VP,
+ typename EP, typename GP, typename EL>
+ std::pair<
+ typename adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>::edge_descriptor,
+ bool
+ >
+ edges(typename adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>::vertex_descriptor u,
+ typename adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>::vertex_descriptor v,
+ const adjacency_list<OEL,VL,directedS,VP,EP,GP,EL>& g)
+ {
+ typedef adjacency_list<OEL,VL,directedS,VP,EP,GP,EL> Graph;
+
+ bool found = false;
+ typename Graph::edge_descriptor edge;
+
+ // iterate over the out_edges of u, looking for v
+ typename Graph::out_edge_iterator i, j;
+ for(tie(i, j) = out_edges(u, g); i != j; ++i) {
+ if(target(*i, g) == v) {
+ edge = *i;
+ found = true;
+ break;
+ }
+ }
+ return std::make_pair(edge, found);
+ }
+
+ template <typename OEL, typename VL, typename VP,
+ typename EP, typename GP, typename EL>
+ std::pair<
+ typename adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>::edge_descriptor,
+ bool
+ >
+ edges(typename adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>::vertex_descriptor u,
+ typename adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>::vertex_descriptor v,
+ const adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL>& g)
+ {
+ typedef adjacency_list<OEL,VL,bidirectionalS,VP,EP,GP,EL> Graph;
+
+ bool found = false;
+ typename Graph::edge_descriptor edge;
+
+ // iterate over either the out_edges or in_edges depending on the minimum
+ // degreer (this should save some time if done repeatedly).
+ if(out_degree(u) < in_degree(v)) {
+ typename Graph::out_edge_iterator i, j;
+ for(tie(i, j) = out_edges(u, g); i != j; ++i) {
+ if(target(*i, g) == v) {
+ edge = *i;
+ found = true;
+ break;
+ }
+ }
+ }
+ else {
+ typename Graph::in_edge_iterator i, j;
+ for(tie(i, j) = in_edges(v, g); i != j; ++i) {
+ if(target(*i, g) == v) {
+ edge = *i;
+ found = true;
+ break;
+ }
+ }
+ }
+ return std::make_pair(edge, found);
+ }
+
+ template <typename OEL, typename VL, typename VP,
+ typename EP, typename GP, typename EL>
+ std::pair<
+ typename adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>::edge_descriptor,
+ bool
+ >
+ edges(typename adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>::vertex_descriptor u,
+ typename adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>::vertex_descriptor v,
+ const adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL>& g)
+ {
+ typedef adjacency_list<OEL,VL,undirectedS,VP,EP,GP,EL> Graph;
+
+ bool found = false;
+ typename Graph::edge_descriptor edge;
+
+ typename Graph::vertex_descriptor p = out_degree(u) < out_degree(v) ? u : v;
+
+ // iterate over the out_edges of u, looking for v
+ typename Graph::out_edge_iterator i, j;
+ for(tie(i, j) = out_edges(p, g); i != j; ++i) {
+ if(target(*i, g) == v) {
+ edge = *i;
+ found = true;
+ break;
+ }
+ }
+ return std::make_pair(edge, found);
+ }
+
+ template <typename VP, typename EP, typename GP>
+ std::pair<undirected_graph<VP,EP,GP>, bool>
+ edges(typename undirected_graph<VP,EP,GP>::vertex_descriptor u,
+ typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ const undirected_graph<VP,EP,GP>& g)
+ {
+ edges(g.impl());
+ }
+
+ template <typename VP, typename EP, typename GP>
+ std::pair<directed_graph<VP,EP,GP>, bool>
+ edges(typename directed_graph<VP,EP,GP>::vertex_descriptor u,
+ typename directed_graph<VP,EP,GP>::vertex_descriptor v,
+ const directed_graph<VP,EP,GP>& g)
+ {
+ edges(g.impl());
+ }
+}
+
+#endif
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-05-22 10:05:21 EDT (Tue, 22 May 2007)
@@ -19,8 +19,8 @@
class undirected_graph
{
public:
- typedef adjacency_list<vecS,
- vecS,
+ typedef adjacency_list<listS,
+ listS,
undirectedS,
VertexProperty,
EdgeProperty,
@@ -78,6 +78,27 @@
: m_graph(n, p)
{}
+ inline type& impl()
+ { return m_graph; }
+
+ inline const type& impl() const
+ { return m_graph; }
+
+ // bundled property support
+#ifndef BOOST_GRAPH_NO_BUNDLED_PROPERTIES
+ vertex_bundled& operator [](vertex_descriptor v)
+ { return m_graph[v]; }
+
+ const vertex_bundled& operator [](vertex_descriptor v) const
+ { return m_graph[v]; }
+
+ edge_bundled& operator [](edge_descriptor e)
+ { return m_graph[e]; }
+
+ const edge_bundled& operator [](edge_descriptor e) const
+ { return m_graph[e]; }
+#endif
+
// Graph concepts
static inline vertex_descriptor null_vertex()
{ return type::null_vertex(); }
@@ -105,6 +126,10 @@
inline degree_size_type degree(vertex_descriptor v)
{ return boost::degree(v, m_graph); }
+ // AdjacencyGraph concepts
+ inline std::pair<adjacency_iterator, adjacency_iterator> adjacent_vertices(vertex_descriptor v) const
+ { return boost::adjacent_vertices(v, m_graph); }
+
// VertexListGraph concepts
inline vertices_size_type num_vertices() const
{ return boost::num_vertices(m_graph); }
@@ -238,7 +263,6 @@
return g.degree(v);
}
-
template <class VP, class EP, class GP>
inline std::pair<
typename undirected_graph<VP,EP,GP>::in_edge_iterator,
@@ -250,6 +274,18 @@
return g.in_edges(v);
}
+ // AdjacencyGraph concepts
+ template <class VP, class EP, class GP>
+ inline std::pair<
+ typename undirected_graph<VP,EP,GP>::adjacency_iterator,
+ typename undirected_graph<VP,EP,GP>::adjacency_iterator
+ >
+ adjacent_vertices(typename undirected_graph<VP,EP,GP>::vertex_descriptor v,
+ const undirected_graph<VP,EP,GP>& g)
+ {
+ return g.adjacent_vertices(v);
+ }
+
// VertexListGraph concepts
template <class VP, class EP, class GP>
inline typename undirected_graph<VP,EP,GP>::vertices_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