#include <boost/graph/iteration_macros.hpp>
-typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
-typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
-typedef boost::property_traits<weight_map_type>::value_type weight_type;
+typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS,
+ boost::no_property, boost::property< boost::edge_weight_t, int > >
+ undirected_graph;
+typedef boost::property_map< undirected_graph, boost::edge_weight_t >::type
+ weight_map_type;
+typedef boost::property_traits< weight_map_type >::value_type weight_type;
-typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> undirected_unweighted_graph;
+typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS >
+ undirected_unweighted_graph;
std::string test_dir;
-boost::unit_test::test_suite* init_unit_test_suite( int argc, char* argv[] ) {
- if (argc != 2) {
- std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test" << std::endl;
- throw boost::unit_test::framework::setup_error("Invalid command line arguments");
- }
- test_dir = argv[1];
- return 0;
+boost::unit_test::test_suite* init_unit_test_suite(int argc, char* argv[])
+{
+ if (argc != 2)
+ {
+ std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test"
+ << std::endl;
+ throw boost::unit_test::framework::setup_error(
+ "Invalid command line arguments");
+ }
+ test_dir = argv[1];
+ return 0;
}
struct edge_t
{
- unsigned long first;
- unsigned long second;
+ unsigned long first;
+ unsigned long second;
};
-template <typename Graph, typename KeyedUpdatablePriorityQueue>
-class mas_edge_connectivity_visitor : public boost::default_mas_visitor {
- public:
- typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+template < typename Graph, typename KeyedUpdatablePriorityQueue >
+class mas_edge_connectivity_visitor : public boost::default_mas_visitor
+{
+public:
+ typedef typename boost::graph_traits< Graph >::vertex_descriptor
+ vertex_descriptor;
typedef typename KeyedUpdatablePriorityQueue::key_type weight_type;
#if 0
mas_edge_connectivity_visitor(const mas_edge_connectivity_visitor<Graph, KeyedUpdatablePriorityQueue>& r)
- : m_pq(r.m_pq), m_curr(r.m_curr), m_prev(r.m_prev),
+ : m_pq(r.m_pq), m_curr(r.m_curr), m_prev(r.m_prev),
m_reach_weight(r.m_reach_weight) {
BOOST_TEST_MESSAGE( "COPY CTOR" );
}
#endif
explicit mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue& pq)
- : m_pq(pq),
- m_curr(new vertex_descriptor(0)), m_prev(new vertex_descriptor(0)),
- m_reach_weight(new weight_type(0)) {
- // BOOST_TEST_MESSAGE( "CTOR" );
- }
-
- void clear() {
- *m_curr = 0;
- *m_prev = 0;
- *m_reach_weight = 0;
- }
-
- //template <typename Vertex> //, typename Graph>
- //void start_vertex(Vertex u, const Graph& g) {
- void start_vertex(vertex_descriptor u, const Graph& g) {
- *m_prev = *m_curr;
- *m_curr = u;
- //BOOST_TEST_MESSAGE( "Initializing Vertex(weight): " << u << "(" << *m_reach_weight << ")" );
- *m_reach_weight = get(m_pq.keys(), u);
- }
-
- vertex_descriptor curr() const { return *m_curr; }
- vertex_descriptor prev() const { return *m_prev; }
- weight_type reach_weight() const { return *m_reach_weight; }
-
- private:
-
+ : m_pq(pq)
+ , m_curr(new vertex_descriptor(0))
+ , m_prev(new vertex_descriptor(0))
+ , m_reach_weight(new weight_type(0))
+ {
+ // BOOST_TEST_MESSAGE( "CTOR" );
+ }
+
+ void clear()
+ {
+ *m_curr = 0;
+ *m_prev = 0;
+ *m_reach_weight = 0;
+ }
+
+ // template <typename Vertex> //, typename Graph>
+ // void start_vertex(Vertex u, const Graph& g) {
+ void start_vertex(vertex_descriptor u, const Graph& g)
+ {
+ *m_prev = *m_curr;
+ *m_curr = u;
+ // BOOST_TEST_MESSAGE( "Initializing Vertex(weight): " << u << "(" <<
+ // *m_reach_weight << ")" );
+ *m_reach_weight = get(m_pq.keys(), u);
+ }
+
+ vertex_descriptor curr() const { return *m_curr; }
+ vertex_descriptor prev() const { return *m_prev; }
+ weight_type reach_weight() const { return *m_reach_weight; }
+
+private:
const KeyedUpdatablePriorityQueue& m_pq;
- boost::shared_ptr<vertex_descriptor> m_curr, m_prev;
- boost::shared_ptr<weight_type> m_reach_weight;
+ boost::shared_ptr< vertex_descriptor > m_curr, m_prev;
+ boost::shared_ptr< weight_type > m_reach_weight;
};
-
// the example from Stoer & Wagner (1997)
// Check various implementations of the ArgPack where
// the weights are provided in it, and one case where
// they are not.
BOOST_AUTO_TEST_CASE(test0)
{
- typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
-
- edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
- {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
- weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
- undirected_graph g(edges, edges + 12, ws, 8, 12);
-
- weight_map_type weights = get(boost::edge_weight, g);
-
- std::map<vertex_descriptor, vertex_descriptor> assignment;
- boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
-
- typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
- distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
- typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
- typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
- indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
- boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
-
- mas_edge_connectivity_visitor<undirected_graph,boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > > test_vis(pq);
-
- boost::maximum_adjacency_search(g,
- boost::weight_map(weights).
- visitor(test_vis).
- root_vertex(*vertices(g).first).
- vertex_assignment_map(assignments).
- max_priority_queue(pq));
-
- BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
- BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
- BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
-
- test_vis.clear();
- boost::maximum_adjacency_search(g,
- boost::weight_map(weights).
- visitor(test_vis).
- root_vertex(*vertices(g).first).
- max_priority_queue(pq));
-
- BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
- BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
- BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
-
- test_vis.clear();
- boost::maximum_adjacency_search(g,
- boost::weight_map(weights).
- visitor(test_vis).
- max_priority_queue(pq));
-
- BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
- BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
- BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
-
- boost::maximum_adjacency_search(g,
- boost::weight_map(weights).
- visitor(boost::make_mas_visitor(boost::null_visitor())));
-
- boost::maximum_adjacency_search(g,
- boost::weight_map(weights));
-
- boost::maximum_adjacency_search(g,
- boost::root_vertex(*vertices(g).first));
-
- test_vis.clear();
- boost::maximum_adjacency_search(g,
- boost::weight_map(boost::make_constant_property<edge_descriptor>(weight_type(1))).
- visitor(test_vis).
- max_priority_queue(pq));
- BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
- BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
- BOOST_CHECK_EQUAL(test_vis.reach_weight(), 2);
-
+ typedef boost::graph_traits< undirected_graph >::vertex_descriptor
+ vertex_descriptor;
+ typedef boost::graph_traits< undirected_graph >::edge_descriptor
+ edge_descriptor;
+
+ edge_t edges[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
+ { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } };
+ weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 };
+ undirected_graph g(edges, edges + 12, ws, 8, 12);
+
+ weight_map_type weights = get(boost::edge_weight, g);
+
+ std::map< vertex_descriptor, vertex_descriptor > assignment;
+ boost::associative_property_map<
+ std::map< vertex_descriptor, vertex_descriptor > >
+ assignments(assignment);
+
+ typedef boost::shared_array_property_map< weight_type,
+ boost::property_map< undirected_graph,
+ boost::vertex_index_t >::const_type >
+ distances_type;
+ distances_type distances = boost::make_shared_array_property_map(
+ num_vertices(g), weight_type(0), get(boost::vertex_index, g));
+ typedef std::vector< vertex_descriptor >::size_type index_in_heap_type;
+ typedef boost::shared_array_property_map< index_in_heap_type,
+ boost::property_map< undirected_graph,
+ boost::vertex_index_t >::const_type >
+ indicesInHeap_type;
+ indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(
+ num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
+ boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
+ distances_type, std::greater< weight_type > >
+ pq(distances, indicesInHeap);
+
+ mas_edge_connectivity_visitor< undirected_graph,
+ boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
+ distances_type, std::greater< weight_type > > >
+ test_vis(pq);
+
+ boost::maximum_adjacency_search(g,
+ boost::weight_map(weights)
+ .visitor(test_vis)
+ .root_vertex(*vertices(g).first)
+ .vertex_assignment_map(assignments)
+ .max_priority_queue(pq));
+
+ BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+ BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+ BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
+
+ test_vis.clear();
+ boost::maximum_adjacency_search(g,
+ boost::weight_map(weights)
+ .visitor(test_vis)
+ .root_vertex(*vertices(g).first)
+ .max_priority_queue(pq));
+
+ BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+ BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+ BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
+
+ test_vis.clear();
+ boost::maximum_adjacency_search(
+ g, boost::weight_map(weights).visitor(test_vis).max_priority_queue(pq));
+
+ BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+ BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+ BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
+
+ boost::maximum_adjacency_search(g,
+ boost::weight_map(weights).visitor(
+ boost::make_mas_visitor(boost::null_visitor())));
+
+ boost::maximum_adjacency_search(g, boost::weight_map(weights));
+
+ boost::maximum_adjacency_search(g, boost::root_vertex(*vertices(g).first));
+
+ test_vis.clear();
+ boost::maximum_adjacency_search(g,
+ boost::weight_map(
+ boost::make_constant_property< edge_descriptor >(weight_type(1)))
+ .visitor(test_vis)
+ .max_priority_queue(pq));
+ BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+ BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
+ BOOST_CHECK_EQUAL(test_vis.reach_weight(), 2);
}
// Check the unweighted case
// with and without providing a weight_map
BOOST_AUTO_TEST_CASE(test1)
{
- typedef boost::graph_traits<undirected_unweighted_graph>::vertex_descriptor vertex_descriptor;
- typedef boost::graph_traits<undirected_unweighted_graph>::edge_descriptor edge_descriptor;
-
- edge_t edge_list[] = {{0, 1}, {1, 2}, {2, 3},
- {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
- undirected_unweighted_graph g(edge_list, edge_list + 12, 8);
-
- std::map<vertex_descriptor, vertex_descriptor> assignment;
- boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
-
- typedef unsigned weight_type;
- typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
- distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
- typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
- typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
- indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
- boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
-
- mas_edge_connectivity_visitor<undirected_unweighted_graph,boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > > test_vis(pq);
-
- boost::maximum_adjacency_search(g,
- boost::weight_map(boost::make_constant_property<edge_descriptor>(weight_type(1))).visitor(test_vis).max_priority_queue(pq));
-
- BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
- BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
- BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(2));
-
- weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
- std::map<edge_descriptor, weight_type> wm;
-
- weight_type i = 0;
- BGL_FORALL_EDGES(e, g, undirected_unweighted_graph) {
- wm[e] = ws[i];
- ++i;
- }
- boost::associative_property_map<std::map<edge_descriptor, weight_type> > ws_map(wm);
-
- boost::maximum_adjacency_search(g, boost::weight_map(ws_map).visitor(test_vis).max_priority_queue(pq));
- BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
- BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
- BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(5));
-
+ typedef boost::graph_traits<
+ undirected_unweighted_graph >::vertex_descriptor vertex_descriptor;
+ typedef boost::graph_traits< undirected_unweighted_graph >::edge_descriptor
+ edge_descriptor;
+
+ edge_t edge_list[] = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 0, 4 }, { 1, 4 },
+ { 1, 5 }, { 2, 6 }, { 3, 6 }, { 3, 7 }, { 4, 5 }, { 5, 6 }, { 6, 7 } };
+ undirected_unweighted_graph g(edge_list, edge_list + 12, 8);
+
+ std::map< vertex_descriptor, vertex_descriptor > assignment;
+ boost::associative_property_map<
+ std::map< vertex_descriptor, vertex_descriptor > >
+ assignments(assignment);
+
+ typedef unsigned weight_type;
+ typedef boost::shared_array_property_map< weight_type,
+ boost::property_map< undirected_graph,
+ boost::vertex_index_t >::const_type >
+ distances_type;
+ distances_type distances = boost::make_shared_array_property_map(
+ num_vertices(g), weight_type(0), get(boost::vertex_index, g));
+ typedef std::vector< vertex_descriptor >::size_type index_in_heap_type;
+ typedef boost::shared_array_property_map< index_in_heap_type,
+ boost::property_map< undirected_graph,
+ boost::vertex_index_t >::const_type >
+ indicesInHeap_type;
+ indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(
+ num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
+ boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
+ distances_type, std::greater< weight_type > >
+ pq(distances, indicesInHeap);
+
+ mas_edge_connectivity_visitor< undirected_unweighted_graph,
+ boost::d_ary_heap_indirect< vertex_descriptor, 22, indicesInHeap_type,
+ distances_type, std::greater< weight_type > > >
+ test_vis(pq);
+
+ boost::maximum_adjacency_search(g,
+ boost::weight_map(
+ boost::make_constant_property< edge_descriptor >(weight_type(1)))
+ .visitor(test_vis)
+ .max_priority_queue(pq));
+
+ BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+ BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
+ BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(2));
+
+ weight_type ws[] = { 2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3 };
+ std::map< edge_descriptor, weight_type > wm;
+
+ weight_type i = 0;
+ BGL_FORALL_EDGES(e, g, undirected_unweighted_graph)
+ {
+ wm[e] = ws[i];
+ ++i;
+ }
+ boost::associative_property_map< std::map< edge_descriptor, weight_type > >
+ ws_map(wm);
+
+ boost::maximum_adjacency_search(
+ g, boost::weight_map(ws_map).visitor(test_vis).max_priority_queue(pq));
+ BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+ BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+ BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(5));
}
#include <boost/graph/iteration_macros_undef.hpp>
-
projects / ceph.git / blobdiff