From: asutton_at_[hidden]
Date: 2007-07-18 11:17:23
Author: asutton
Date: 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
New Revision: 7466
URL: http://svn.boost.org/trac/boost/changeset/7466
Log:
Completely rewrote the connectivty code.
Text files modified:
sandbox/SOC/2007/graphs/boost/graph/clique.hpp | 14 +-
sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp | 167 ++++++++++++++++++++++++++++-----------
sandbox/SOC/2007/graphs/boost/graph/cycle.hpp | 18 ----
sandbox/SOC/2007/graphs/boost/graph/distance.hpp | 29 +++++-
sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp | 6
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk | 4
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk | 8
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk | 127 +++++++++++++++++++++---------
sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk | 10 ++
sandbox/SOC/2007/graphs/libs/graph/test/components.cpp | 124 ++++++++++++++++-------------
10 files changed, 325 insertions(+), 182 deletions(-)
Modified: sandbox/SOC/2007/graphs/boost/graph/clique.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/clique.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/clique.hpp 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -74,11 +74,11 @@
typename Container, // candidates/not type
typename Visitor
>
- void extend(const Graph& g,
- Clique& clique,
- Container& cands,
- Container& nots,
- Visitor vis)
+ void extend_clique(const Graph& g,
+ Clique& clique,
+ Container& cands,
+ Container& nots,
+ Visitor vis)
{
typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
@@ -147,7 +147,7 @@
}
else {
// recurse to explore the new candidates
- extend(g, clique, new_cands, new_nots, vis);
+ extend_clique(g, clique, new_cands, new_nots, vis);
}
// we're done with this vertex, so we need to move it
@@ -174,7 +174,7 @@
VertexSet cands(i, end); // start with all vertices as candidates
VertexSet nots; // start with no vertices visited
Clique clique; // the first clique is an empty vertex set
- detail::extend(g, clique, cands, nots, vis);
+ detail::extend_clique(g, clique, cands, nots, vis);
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/connectivity.hpp 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -7,84 +7,153 @@
#ifndef BOOST_GRAPH_CONNECTIVITY_HPP
#define BOOST_GRAPH_CONNECTIVITY_HPP
-// boost includes
#include <boost/graph/named_parameters.hpp>
-#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/exterior_property.hpp>
#include <boost/graph/connected_components.hpp>
namespace boost
{
namespace detail
{
+ template <typename Graph, typename CompMap, typename Components>
+ inline void
+ assign_vertices_to_components(const Graph& g,
+ size_t n,
+ CompMap comps_map,
+ Components& comps)
+ {
+ comps.resize(n);
+ typename graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ comps[comps_map[*i]].push_back(*i);
+ }
+ }
+
+ // Notes on fetch_connected_components()
+ //
+ // If the component map is non-void, then we don't need to fetch
+ // the connected components - we'll just assume that it's already
+ // been done. If, however, the component map is void, then we
+ // actually have to get them using the algorithm.
+
+ // This is the catch-all version, where component map is non-void.
+ // Here, we have to find the max element... Note that if the user
+ // passes the return from connected_components, we can effectively
+ // bypass the computation of the number of components - which would
+ // probably be prefereable.
template <
- typename Graph,
- typename CompMap,
- typename ColorMap,
- typename IndexMap
- >
- inline size_t
- forward_connected_components(const Graph& g,
- CompMap comps,
- ColorMap colors,
- IndexMap indices)
+ typename Graph, typename Components, typename VertexIndexMap,
+ typename SizeType, typename ComponentMap, typename ColorMap>
+ inline SizeType
+ fetch_connected_components(const Graph& g,
+ Components& comps,
+ VertexIndexMap,
+ SizeType number,
+ ComponentMap comps_map,
+ ColorMap)
{
- return connected_components(g, comps,
- color_map(colors).
- vertex_index_map(indices));
+ SizeType ret(0);
+ if(number == 0) {
+ typename graph_traits<Graph>::vertex_iterator i, end;
+ for(tie(i, end) = vertices(g); i != end; ++i) {
+ ret = std::max(comps_map[*i] + 1, ret);
+ }
+ }
+ else {
+ ret = number;
+ }
+ assign_vertices_to_components(g, ret, comps_map, comps);
+ return ret;
}
- template <typename Graph, typename CompMap, typename IndexMap>
- inline size_t
- forward_connected_components(const Graph& g,
- CompMap comps,
- not_given,
- IndexMap indices)
+
+ template <
+ typename Graph, typename Components,
+ typename VertexIndexMap, typename SizeType
+ >
+ inline SizeType
+ fetch_connected_components(const Graph& g,
+ Components& comps,
+ VertexIndexMap indices,
+ SizeType,
+ parameter::void_,
+ parameter::void_)
{
- return connected_components(g, comps,
+ typedef exterior_vertex_property<Graph, std::size_t> ComponentProperty;
+ typedef typename ComponentProperty::container_type ComponentContainer;
+ typedef typename ComponentProperty::map_type ComponentMap;
+
+ ComponentContainer comps_store(num_vertices(g));
+ ComponentMap comps_map(make_property_map(comps_store));
+
+ // get the compoents first
+ SizeType ret = connected_components(g, comps_map,
vertex_index_map(indices));
+
+ // and assign them to the output
+ assign_vertices_to_components(g, ret, comps_map, comps);
+ return ret;
}
- template <typename Graph, typename CompMap, typename Components>
- inline void assign_vertices_to_components(const Graph& g, size_t n,
- CompMap comp_map,
- Components& comps)
+ template <
+ typename Graph, typename VertexIndexMap, typename Components,
+ typename SizeType, typename ColorMap
+ >
+ inline SizeType
+ fetch_connected_components(const Graph& g,
+ Components& comps,
+ VertexIndexMap indices,
+ SizeType,
+ parameter::void_,
+ ColorMap colors)
{
- comps.resize(n);
- typename graph_traits<Graph>::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- comps[comp_map[*i]].push_back(*i);
- }
+ typedef exterior_vertex_property<Graph, size_t> ComponentProperty;
+ typedef typename ComponentProperty::container_type ComponentContainer;
+ typedef typename ComponentProperty::map_type ComponentMap;
+
+ ComponentContainer comps_store(num_vertices(g));
+ ComponentMap comps_map(make_property_map(comps_store));
+
+ // get the components
+ SizeType ret = connected_components(g, comps_map,
+ vertex_index_map(indices).
+ color_map(colors));
+
+ // and assign them to the output
+ assign_vertices_to_components(g, ret, comps_map, comps);
+ return ret;
}
-
- template <typename Graph, typename CompMap>
- inline void assign_vertices_to_components(const Graph& g, size_t n,
- CompMap comp_map,
- not_given)
- { }
}
+ // TODO: There seems to be a bug in Boost.Parameter that prevents the
+ // actual use of more than 5 parameters - even when the arity is
+ // jacked up - unless I'm doing something wrong. For the time being,
+ // the number parameter is not specified, and simply defaults to 0
+ // since the only way to get around it would be to pass something
+ // as a pair - and I'm not interested in that right now.
// the connectivity function
BOOST_PARAMETER_FUNCTION(
(std::size_t), connectivity, tag,
(required
(graph, *)
- (out(component_map), *))
+ (out(components), *))
(optional
- (color_map, *, not_given())
- (vertex_index_map, *, get(vertex_index, graph))
- (out(components), *, not_given()))
+ // (number, std::size_t, 0)
+ (component_map, *, parameter::void_())
+ (out(color_map), *, parameter::void_())
+ (vertex_index_map, *, get(vertex_index, graph)))
)
{
- size_t n = detail::forward_connected_components(graph,
- component_map,
- color_map,
- vertex_index_map);
-
- // possibly allocate components, could be a non-call
- detail::assign_vertices_to_components(graph, n, component_map, components);
+ typename graph_traits<graph_type>::vertices_size_type number(0);
- return n;
+ // step 1, get the components (maybe), returning the number
+ return detail::fetch_connected_components(graph,
+ components,
+ vertex_index_map,
+ number,
+ component_map,
+ color_map);
}
}
Modified: sandbox/SOC/2007/graphs/boost/graph/cycle.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/cycle.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/cycle.hpp 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -62,21 +62,6 @@
// address = {New York, NY, USA},
// }
- // TODO: The algorithm, as presented, suffers from a number of disappoinments (not
- // just being slow. It only really works on the most simple directed and undirected
- // graphs. Because of the requirement on increasingly large vertex indices, the
- // algorithm will never follow bidirected or reflexive edges. This failure causes
- // the algorithm to miss a number cycles that end up bridging those reflexive
- // humps.
- //
- // An interesting tradeoff would be to remove the test for increasing indices
- // in detail::ignore_vertex(), causing the algorithm to visit every permutation
- // of each cycle - that actually hits them all. Some extra work could be done
- // mapping permuations into combinations - if you really want to.
- //
- // However, I should point out that this never miscomputes triangles - which
- // is what I'd intended it for.
-
struct cycle_visitor
{
template <class Vertex, class Graph>
@@ -310,9 +295,6 @@
}
}
- // TODO: I may need to templatize the path type - it would add a little extra
- // flexibility, but I'm not certain its a great idea.
-
template <typename Graph, typename Visitor>
inline void
visit_cycles(const Graph& g,
Modified: sandbox/SOC/2007/graphs/boost/graph/distance.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/distance.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/distance.hpp 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -69,22 +69,37 @@
return double(detail::sum_distances(g, dist)) / double(num_vertices(g));
}
- /*
- template <typename Graph, typename DistanceMap, typename T = double>
+ // Arbitrary numeric version uses T as some numeric type.
+ // T must be constructible from degree_size_type and
+ // DistanceMap::value_type. Note that above T == double.
+ template <typename Graph, typename DistanceMap, typename T>
inline T
mean_geodesic_distance(const Graph& g,
- DistanceMap dist)
+ DistanceMap dist,
+ const T& dummy)
{
return T(detail::sum_distances(g, dist)) / T(num_vertices(g));
}
- */
+
template <typename Graph, typename DistanceMap>
inline double
closeness(const Graph& g,
DistanceMap dist)
{
- return double(1.0) / double(detail::sum_distances(g, dist));
+ return double(1) / double(detail::sum_distances(g, dist));
+ }
+
+ // Arbitrary numeric version uses T as some numeric type.
+ // T must be constructible from integral and DistanceMap::value_type.
+ // Note that above T == double.
+ template <typename Graph, typename DistanceMap, typename T>
+ inline T
+ closeness(const Graph& g,
+ DistanceMap dist,
+ const T& dummy)
+ {
+ return dummy(1) / double(detail::sum_distances(g, dist));
}
// Can we abstract the computation of max on distances to max of
@@ -92,12 +107,14 @@
// this is the max of geodesics... What if we wanted some other
// operator?
+ // Note that the DistanceMap::value_type must be constructible
+ // as 0 - basically indicating an acceptable default value.
template <typename Graph, typename DistanceMap>
inline typename property_traits<DistanceMap>::value_type
eccentricity(const Graph& g,
DistanceMap dist)
{
- typename property_traits<DistanceMap>::value_type ret = 0;
+ typename property_traits<DistanceMap>::value_type ret(0);
typename graph_traits<Graph>::vertex_iterator i, end;
for(tie(i, end) = vertices(g); i != end; ++i) {
ret = std::max(ret, dist[*i]);
Modified: sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp
==============================================================================
--- sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp (original)
+++ sandbox/SOC/2007/graphs/boost/graph/named_parameters.hpp 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -7,7 +7,9 @@
#ifndef BOOST_GRAPH_NAMED_PARAMETERS_HPP
#define BOOST_GRAPH_NAMED_PARAMETERS_HPP
-// boost includes
+// TODO: There's a problem with Boost.Parameter library - it just
+// doesn't like > 5 parameters.
+
#include <boost/parameter.hpp>
namespace boost
@@ -22,7 +24,7 @@
BOOST_PARAMETER_NAME(in_histogram)
BOOST_PARAMETER_NAME(out_histogram)
BOOST_PARAMETER_NAME(components)
- BOOST_PARAMETER_NAME(is_connected)
+ BOOST_PARAMETER_NAME(number)
// various map-type parameters
BOOST_PARAMETER_NAME(distance_map)
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_concepts.qbk 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -9,6 +9,7 @@
/ This file contains Boost-defined concepts
/]
+
[template BoostMultiPassInputIterator[] [@http://www.boost.org/libs/utility/MultiPassInputIterator.html MultipPassInputIterator]]
[template BoostReadablePropertyMap[] [@http://www.boost.org/libs/property_map/ReadablePropertyMap.html ReadablePropertyMap]]
@@ -35,3 +36,6 @@
[template BoostAStarVisitor[] [link boost_graph.concepts.visitor_concepts.a_star_visitor A\*Visitor]]
[template BoostEventVisitor[] [link boost_graph.concepts.visitor_concepts.event_visitor EventVisitor]]
[template BoostEventVisitorList[] [link boost_graph.concepts.visitor_concepts.event_visitor_list EventVisitorList]]
+
+[/ A bunch of miscellaneus concepts]
+[template BoostColorValue[] [link boost_graph.concepts.miscellaneous_concepts.color_value ColorValue]]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/boost_reference.qbk 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -20,10 +20,10 @@
[template boost_null_visitor[] [link boost_graph.reference_guide.visitor_types.null_visitor [^null_visitor]]]
[template boost_bfs_visitor[] [link boost_graph.reference_guide.visitor_types.bfs_visitor [^bfs_visitor]]]
[template boost_dfs_visitor[] [link boost_graph.reference_guide.visitor_types.dfs_visitor [^dfs_visitor]]]
-[template boost_predecessor_recorder[] [link boost.graph_reference_guide.event_visitors.predecessor_recorder [^predecessor_recorder]]]
-[template boost_distance_recorder[] [link boost.graph_reference_guide.event_visitors.distance_recorder [^distance_recorder]]]
-[template boost_time_stamper[] [link boost.graph_reference_guide.event_visitors.time_stamper [^time_stamper]]]
-[template boost_property_writer[] [link boost.graph_reference_guide.event_visitors.property_writer [^property_writer]]]
+[template boost_predecessor_recorder[] [link boost_graph.reference_guide.event_visitors.predecessor_recorder [^predecessor_recorder]]]
+[template boost_distance_recorder[] [link boost_graph.reference_guide.event_visitors.distance_recorder [^distance_recorder]]]
+[template boost_time_stamper[] [link boost_graph.reference_guide.event_visitors.time_stamper [^time_stamper]]]
+[template boost_property_writer[] [link boost_graph.reference_guide.event_visitors.property_writer [^property_writer]]]
[/ Core algorithms /]
[template boost_breadth_first_search[] [link boost_graph.reference_guide.algorithms.core_algorithms.breadth_first_search [^breadth_first_search()]]]
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/connectivity.qbk 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -9,10 +9,10 @@
size_t connectivity(
_graph,
- _component_map,
- _color_map = not_given(),
- _vertex_index_map = not_given(),
- _components = not_given())
+ _components,
+ _component_map = ``['not given]``,
+ _color_map = ``['not given]``,
+ _vertex_index_map = get(vertex_index, _graph));
The `connectivity()` algorithm is a wrapper around the [boost_connected_components]
algorithm, that provides some convenience for working with resultant concept maps.
@@ -25,8 +25,23 @@
`_component_map` with component id 0, will be placed into the vertex set
at index 0 of the `_components` argument.
-This function returns the number of connected components in the graph. Note
-that the graph is connected if and only if this function returns 1.
+This function returns the number of connected components in the graph. The graph
+is connected if and only if this function returns exactly 1.
+
+There are two distinct methods for calling this function: with or without the
+`_component_map` parameter. If the `_component_map` /is not/ given, then the
+algorithm must first compute the connected components of `_graph`. In this case,
+the user may need to supply the `_vertex_index_map` or an alternate `_color_map`.
+
+If the _component_map /is/ given, then the algorithm assumes that connected
+components have already been assigned in the `_component_map`. The `_color_map`
+and `_vertex_index_map` parameters are effectively ignored in this case.
+
+[note
+First, this hasn't been tested very will for directed graphs. In fact, testing
+will probably result in the creation of `strong_connecity` which forwards the
+call to `strong_connected_components`.
+]
[h5 Where Defined]
`boost/graph/connectivity.hpp`
@@ -45,60 +60,94 @@
]
]
[
- [optional, out]
+ [required, out] [`_components`]
[
- `_distribution`
-
- `_out_distribution`
-
- `_in_distribution`
+ The components parameter provides storage for the assignment of
+ vertices to components. The `_components` parameter must be a
+ model of [SgiRandomAccessContainer] whose index type must be convertible
+ to the graphs `vertices_size_type`, and whose `value_type` must be
+ a model of [SgiBackInsertionSequence]. In turn, the `value_type` of
+ this [SgiBackInsertionSequence] must be the `vertex_descriptor` type
+ of `_graph`.
]
+ ]
+ [
+ [optional, in] [`_component_map`]
[
- The distribution parameters maps instances of vertex degree to the
- number of observed vertices in the graph with that degree.
-
- These parameters must model both the [SgiSequence] and
- [SgiRandomAccessContainer] concepts (e.g., `std::vector`). The index type of the
- distribution must be the same as `degree_size_type`. The `value_type` must
- be integral (preferably unsigned).
+ The component map that represents the assignment of vertices to
+ distinct components in the graph. The `_component_map` must be
+ a model of [BoostReadablePropertyMap]. the `value_type` should be
+ integral, preferably the same as `vertices_size_type` for the
+ graph. The `key_type` must be the graph's `vertex_descriptor`.
- If not supplied, these parameters assume the default value of `not_given`,
- implying that no computation is performed.
+ *Default* /not given/
]
]
[
- [optional, out]
+ [optional, in] [`_color_map`]
[
- `_histogram`
+ This is used by the [boost_connected_components] algorithm to keep
+ track of its progress through the graph. The type of `ColorMap` must
+ be a model of [BoostReadWritePropertyMap], it's `key_type` must be
+ the `vertex_descriptor` type of `_graph` and its `value_type` must
+ be a model of [BoostColorValue].
- `_out_histogram`
-
- `_in_histogram`
+ *Default* /not given/
]
+ ]
+ [
+ [optional, in] [`_vertex_index_map`]
[
- The distribution parameters maps instances of vertex degree to the
- number of observed vertices in the graph with that degree.
-
- The histogram output parameter must be a model of both [SgiSequence]
- and [SgiRandomAccessContainer] (e.g., `std::vector`). The index type of the
- distribution must be the same as `degree_size_type`. Additionally `value_type`
- must be a model of the [SgiBackInsertionSequence] (e.g., `std::vector`).
+ This maps each vertex to an integer in the range \[0, `num_vertices(g)`).
+ This parameter is necessary only _graph does not have built-in vertices
+ and/or a correct ordering on them.
- If not supplied, these parameters assume the default value of `not_given`,
- implying that no computation is performed.
+ *Default* `get(vertex_index, g)`
]
]
]
[h5 Return Value]
-This function returns the number of connected components.
+This function returns the number of connected components. When the return value of
+this function is equal to `1`, then the graph is a single connected component.
[h5 Complexity]
-
-[h5 Notes]
+This function has time complexity /O(V)/, and space complexity /O(V)/ since each
+vertex is assigned to a component in the _components_vector.
[h5 Examples]
-[h5 Rationale]
+[note These are going to be expanded...]
+
+When a component map is not provided:
+
+ typedef undirected_graph<> Graph;
+ typedef graph_traits<Graph>::vertex_descriptor Vertex;
+ typedef vector<Vertex> Component;
+ typedef vector<Component> ComponentList;
+
+ Graph g;
+ // build a graph
+
+ ComponentList components;
+ connected_components(g, components);
+
+ size_t c = 0;
+ BOOST_FOREACH(Component comp, components) {
+ cout << "component: " << c++ << ": ";
+ BOOST_FOREACH(Vertex v, comp) {
+ cout << get(vertex_index, g, v) << " ";
+ }
+ cout << "\n";
+ }
+
+If the component map /is/ available...
+
+ // write some code to that effect.
+
+[h5 Details]
+The signature of this function may change in the future to include a new parameter, `_number`,
+which indicates the number of components computed by [boost_connected_components]. This
+introduces a new calling "profile" that would bypass the computation of the number of components.
[endsect]
\ No newline at end of file
Modified: sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk (original)
+++ sandbox/SOC/2007/graphs/libs/graph/doc/quickbook/reference/reference.qbk 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -11,11 +11,20 @@
[include undirected_graph.qbk]
[include directed_graph.qbk]
[include adjacency_list.qbk]
+[include edge_list.qbk]
[endsect]
[section Traits Classes]
[endsect]
+[section Event Visitor List Adaptors]
+[include bfs_visitor.qbk]
+[include dfs_visitor.qbk]
+[include dijkstra_visitor.qbk]
+[include bellman_visitor.qbk]
+[include astar_visitor.qbk]
+[endsect]
+
[section Event Visitors]
[include predecessor_recorder.qbk]
[include distance_recorder.qbk]
@@ -52,6 +61,7 @@
[section Graph Measures]
[include distributions.qbk]
+[include distance.qbk]
[endsect]
[endsect]
Modified: sandbox/SOC/2007/graphs/libs/graph/test/components.cpp
==============================================================================
--- sandbox/SOC/2007/graphs/libs/graph/test/components.cpp (original)
+++ sandbox/SOC/2007/graphs/libs/graph/test/components.cpp 2007-07-18 11:17:21 EDT (Wed, 18 Jul 2007)
@@ -10,16 +10,17 @@
#include <vector>
#include <map>
#include <tr1/unordered_map>
-#include <typeinfo>
-#include <cxxabi.h>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/undirected_graph.hpp>
+#include <boost/graph/exterior_property.hpp>
#include <boost/graph/connectivity.hpp>
+#include <boost/foreach.hpp>
+
+#define for_each BOOST_FOREACH
using namespace std;
using namespace boost;
-using namespace __cxxabiv1;
template <typename Graph>
void build_graph(Graph& g)
@@ -41,83 +42,92 @@
add_edge(v[2], v[0], g);
add_edge(v[3], v[4], g);
- // add_edge(v[0], v[4], g); // this makes it fully connected
};
-void test_1()
+template <typename Graph>
+void test_external()
{
- typedef adjacency_list<vecS, vecS, undirectedS> Graph;
- Graph g;
- build_graph(g);
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
- vector<int> comps(num_vertices(g));
- connectivity(g, &comps[0]);
-}
+ typedef exterior_vertex_property<Graph, size_t> ComponentProperty;
+ typedef typename ComponentProperty::container_type ComponentContainer;
+ typedef typename ComponentProperty::map_type ComponentMap;
-void test_2()
-{
- typedef adjacency_list<vecS, vecS, undirectedS> Graph;
Graph g;
build_graph(g);
- vector<int> comps(num_vertices(g));
- vector<default_color_type> colors(num_vertices(g));
- connectivity(g, &comps[0],
- _color_map = &colors[0]);
-}
-void test_3()
-{
- typedef adjacency_list<listS, listS, undirectedS> Graph;
- typedef map<Graph::vertex_descriptor, int> IndexMap;
- typedef map<Graph::vertex_descriptor, int> CompMap;
- typedef associative_property_map<IndexMap> IndexProperties;
- typedef associative_property_map<CompMap> CompProperties;
-
- Graph g;
- build_graph(g);
+ ComponentContainer comps(num_vertices(g));
+ ComponentMap comps_map(make_property_map(comps));
- IndexMap indices;
- CompMap comps;
+ connected_components(g, comps_map);
- int x = 0;
- Graph::vertex_iterator i, end;
- for(tie(i, end) = vertices(g); i != end; ++i) {
- indices[*i] = x++;
+ typedef std::vector<Vertex> VertexList;
+ typedef std::vector<VertexList> Component;
+ Component components;
+ connectivity(
+ _graph = g,
+ _components = components,
+ _component_map = comps_map);
+
+ size_t c = 0;
+ for_each(VertexList& vl, components) {
+ cout << "component " << c++ << ": ";
+ for_each(Vertex v, vl) {
+ cout << get(vertex_index, g, v) << " ";
+ }
+ cout << endl;
}
-
- CompProperties comp_map(comps);
- IndexProperties index_map(indices);
- connectivity(g, comp_map,
- _vertex_index_map = index_map);
}
-void test_4()
+template <typename Graph>
+void test_internal()
{
- typedef undirected_graph<> Graph;
- typedef tr1::unordered_map<Graph::vertex_descriptor, int> CompMap;
- typedef associative_property_map<CompMap> CompProperties;
- typedef std::vector<std::vector<Graph::vertex_descriptor> > Components;
+ typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
+
+ typedef exterior_vertex_property<Graph, size_t> ComponentProperty;
+ typedef typename ComponentProperty::container_type ComponentContainer;
+ typedef typename ComponentProperty::map_type ComponentMap;
Graph g;
build_graph(g);
- CompMap comps;
- CompProperties comp_map(comps);
- Components ccomps;
- connectivity(g, comp_map, _components = ccomps);
-
- for(size_t i = 0; i < ccomps.size(); ++i) {
- cout << i << ": " << ccomps[i].size() << "\n";
+ typedef std::vector<Vertex> VertexList;
+ typedef std::vector<VertexList> Component;
+ Component components;
+ connectivity(_graph = g, _components = components);
+
+ size_t c = 0;
+ for_each(VertexList& vl, components) {
+ cout << "component " << c++ << ": ";
+ for_each(Vertex v, vl) {
+ cout << get(vertex_index, g, v) << " ";
+ }
+ cout << endl;
}
}
-
int
main(int argc, char *argv[])
{
- test_1();
- test_2();
- test_3();
- test_4();
+ typedef adjacency_list<vecS, vecS, undirectedS> AdjacencyList;
+ typedef undirected_graph<> Graph;
+
+ std::cout << "*** adjacency_list<vecS, vecS> (external) ***\n";
+ test_external<AdjacencyList>();
+ std::cout << "\n\n";
+
+ std::cout << "*** undirected_graph<> (external) ***\n";
+ test_external<Graph>();
+ std::cout << "\n\n";
+
+ std::cout << "*** adjacency_list<vecS, vecS> (internal) ***\n";
+ test_external<AdjacencyList>();
+ std::cout << "\n\n";
+
+ std::cout << "*** undirected_graph<> (internal) ***\n";
+ test_external<Graph>();
+ std::cout << "\n\n";
+
+ return 0;
}