test_undirected_graph.cc
Go to the documentation of this file.
00001 #include <boost/test/auto_unit_test.hpp>
00002 
00003 #include "testsuite.hh"
00004 #include <boost/graph/adjacency_list.hpp>
00005 #include <utilmm/iterator_sequence.hh>
00006 #include <utilmm/undirected_graph.hh>
00007 #include <utilmm/undirected_dfs.hh>
00008 #include <vector>
00009 #include <boost/concept_check.hpp>
00010 #include <boost/graph/connected_components.hpp>
00011 #include <boost/graph/depth_first_search.hpp>
00012 #include <boost/graph/breadth_first_search.hpp>
00013 
00014 using namespace utilmm;
00015 using namespace std;
00016 
00017 BOOST_AUTO_TEST_CASE( test_iterator_sequence )
00018 {
00019     int seq1[] = { 0, 1, 2 };
00020     int seq2[] = { 3, 4, 5 };
00021 
00022     std::vector<int> v1(seq1, seq1 + 3);
00023     std::vector<int> v2(seq2, seq2 + 3);
00024 
00025     typedef iterator_sequence<vector<int>::iterator, vector<int>::iterator>
00026         it_seq_t;
00027 
00028     it_seq_t it_seq_begin(v1.begin(), v1.end(), v2.begin(), v2.begin());
00029     it_seq_t it_seq = it_seq_begin;
00030     it_seq_t it_seq_end(v1.end(), v1.end(), v2.begin(), v2.end());
00031 
00032 
00033     // forward traversal
00034     for (int i = 0; i < 6; ++i, ++it_seq)
00035         BOOST_REQUIRE_EQUAL(*it_seq, i);
00036     BOOST_REQUIRE(it_seq == it_seq_end);
00037 
00038     // backward traversal
00039     for (int i = 0; i < 6; ++i)
00040     {
00041         --it_seq;
00042         BOOST_REQUIRE_EQUAL(*it_seq, 5 - i);
00043     }
00044     BOOST_REQUIRE(it_seq == it_seq_begin);
00045 
00046     // advance
00047     it_seq += 2;
00048     BOOST_REQUIRE_EQUAL(*it_seq, 2);
00049     BOOST_REQUIRE_EQUAL(2, it_seq - it_seq_begin);
00050     it_seq += 2;
00051     BOOST_REQUIRE_EQUAL(*it_seq, 4);
00052     BOOST_REQUIRE_EQUAL(4, it_seq - it_seq_begin);
00053     ++it_seq;
00054     BOOST_REQUIRE_EQUAL(*it_seq, 5);
00055     BOOST_REQUIRE_EQUAL(5, it_seq - it_seq_begin);
00056     it_seq -= 2;
00057     BOOST_REQUIRE_EQUAL(*it_seq, 3);
00058     BOOST_REQUIRE_EQUAL(3, it_seq - it_seq_begin);
00059     it_seq -= 2;
00060     BOOST_REQUIRE_EQUAL(*it_seq, 1);
00061     BOOST_REQUIRE_EQUAL(1, it_seq - it_seq_begin);
00062 }
00063 
00064 // Concept checking
00065 typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
00066         boost::no_property, boost::property<boost::edge_color_t, boost::default_color_type> > BaseGraph;
00067 typedef undirected_graph< BaseGraph, const BaseGraph& > UndirectedGraph;
00068 BOOST_CLASS_REQUIRE(UndirectedGraph, boost, AdjacencyGraphConcept);
00069 BOOST_CLASS_REQUIRE(UndirectedGraph, boost, IncidenceGraphConcept);
00070 
00071 BOOST_AUTO_TEST_CASE( test_undirected_property_maps_adaptor )
00072 {
00073     using namespace boost;
00074     BaseGraph g;
00075     UndirectedGraph undirected(g);
00076     BaseGraph::vertex_descriptor v1, v2;
00077     v1 = add_vertex(g);
00078     v2 = add_vertex(g);
00079     BaseGraph::edge_descriptor e = add_edge(v1, v2, g).first;
00080     UndirectedGraph::edge_descriptor u_e = *edges(undirected).first;
00081 
00082     put(boost::edge_color_t(), g, e, boost::white_color);
00083     
00084     typedef property_map<UndirectedGraph, edge_color_t>::const_type PMap;
00085     undirected_property_map<PMap> u_pmap(get(boost::edge_color_t(), undirected));
00086     int value = get(u_pmap, u_e);
00087     BOOST_REQUIRE_EQUAL(boost::white_color, value);
00088 }
00089 
00090 /* Test that the edges have the proper source() and target() */
00091 BOOST_AUTO_TEST_CASE( test_undirected_incidence )
00092 {
00093     BaseGraph g;
00094     UndirectedGraph undirected(g);
00095     using namespace boost;
00096 
00097     BaseGraph::vertex_descriptor v1, v2, v3;
00098     UndirectedGraph::out_edge_iterator it, end;
00099 
00100     v1 = add_vertex(g);
00101     v2 = add_vertex(g);
00102     v3 = add_vertex(g);
00103     add_edge(v1, v2, g);
00104     add_edge(v2, v3, g);
00105     add_edge(v3, v1, g);
00106 
00107     tie(it, end) = out_edges(v1, undirected);
00108     BOOST_REQUIRE(it->second);
00109     BOOST_REQUIRE(source(*it, undirected) == v1);
00110     BOOST_REQUIRE(target(*it, undirected) == v2 || target(*it, undirected) == v3);
00111     BOOST_REQUIRE(!(++it)->second);
00112     BOOST_REQUIRE(source(*it, undirected) == v1);
00113     BOOST_REQUIRE(target(*it, undirected) == v2 || target(*it, undirected) == v3);
00114     
00115     tie(it, end) = out_edges(v2, undirected);
00116     BOOST_REQUIRE(source(*it, undirected) == v2);
00117     BOOST_REQUIRE(target(*it, undirected) == v1 || target(*it, undirected) == v3);
00118     BOOST_REQUIRE(source(*++it, undirected) == v2);
00119     BOOST_REQUIRE(target(*it, undirected) == v1 || target(*it, undirected) == v3);
00120 }
00121 
00122 
00123 /* Check that some algorithms compile on undirected graph */
00124 // BOOST_AUTO_TEST_CASE( test_undirected_algorithms )
00125 // {
00126 //     BaseGraph g;
00127 //     UndirectedGraph undirected(g);
00128 //     using namespace boost;
00129 // 
00130 //     typedef associative_property_map< std::map<BaseGraph::vertex_descriptor, default_color_type> > 
00131 //      VertexColorMap;
00132 //     associative_property_map< std::map<UndirectedGraph::vertex_descriptor, int> > component_map;
00133 //     VertexColorMap color_map;
00134 //     connected_components(undirected, component_map, boost::color_map(color_map));
00135 // 
00136 //     default_dfs_visitor dfs_vis;
00137 //     depth_first_search(undirected, visitor(dfs_vis));
00138 //     default_bfs_visitor bfs_vis;
00139 //     breadth_first_search(undirected, *vertices(g).first, visitor(bfs_vis));
00140 // 
00141 //     UndirectedGraph::vertex_descriptor v1 = add_vertex(g);
00142 //     // typedef associative_property_map< std::map<BaseGraph::edge_descriptor, default_color_type> > 
00143 //     //     EdgeColorMap;
00144 //     // EdgeColorMap edge_color_map;
00145 //     utilmm::undirected_dfs(undirected, dfs_vis,
00146 //          color_map, make_undirected_edge_map(get(boost::edge_color_t(), g)), v1);
00147 // }


utilmm
Author(s): Sylvain Joyeux/sylvain.joyeux@m4x.org
autogenerated on Mon Oct 6 2014 03:17:01