Changeset 100:4f754b4cf82b in lemon1.2
 Timestamp:
 02/07/08 22:37:07 (15 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 11 added
 4 edited
Legend:
 Unmodified
 Added
 Removed

lemon/Makefile.am
r99 r100 16 16 17 17 lemon_HEADERS += \ 18 lemon/concept_check.h \ 18 lemon/bfs.h \ 19 lemon/bin_heap.h \ 20 lemon/dfs.h \ 21 lemon/dijkstra.h \ 19 22 lemon/dim2.h \ 20 23 lemon/error.h \ 24 lemon/graph_utils.h \ 21 25 lemon/list_graph.h \ 22 26 lemon/maps.h \ … … 33 37 lemon/bits/invalid.h \ 34 38 lemon/bits/map_extender.h \ 39 lemon/bits/path_dump.h \ 35 40 lemon/bits/traits.h \ 36 41 lemon/bits/utility.h \ … … 41 46 lemon/concepts/digraph.h \ 42 47 lemon/concepts/graph.h \ 48 lemon/concepts/heap.h \ 43 49 lemon/concepts/maps.h \ 44 50 lemon/concepts/path.h \ 
lemon/path.h
r98 r100 30 30 #include <lemon/error.h> 31 31 #include <lemon/bits/invalid.h> 32 #include <lemon/concepts/path.h> 32 33 33 34 namespace lemon { 
test/Makefile.am
r99 r100 4 4 noinst_HEADERS += \ 5 5 test/digraph_test.h \ 6 test/heap_test.h \ 6 7 test/map_test.h \ 7 8 test/test_tools.h 8 9 9 10 check_PROGRAMS += \ 11 test/bfs_test \ 12 test/dfs_test \ 10 13 test/digraph_test \ 11 14 test/dim_test \ … … 20 23 XFAIL_TESTS += test/test_tools_fail$(EXEEXT) 21 24 25 test_bfs_test_SOURCES = test/bfs_test.cc 26 test_dfs_test_SOURCES = test/dfs_test.cc 22 27 test_digraph_test_SOURCES = test/digraph_test.cc 23 28 test_dim_test_SOURCES = test/dim_test.cc 24 29 #test_error_test_SOURCES = test/error_test.cc 25 30 test_graph_test_SOURCES = test/graph_test.cc 31 # test_heap_test_SOURCES = test/heap_test.cc 26 32 test_maps_test_SOURCES = test/maps_test.cc 27 33 test_path_test_SOURCES = test/path_test.cc 
test/test_tools.h
r39 r100 21 21 22 22 #include <iostream> 23 #include <vector> 24 25 #include <cstdlib> 26 #include <ctime> 27 28 #include <lemon/concept_check.h> 29 #include <lemon/concepts/digraph.h> 30 31 #include <lemon/random.h> 32 33 using namespace lemon; 23 34 24 35 //! \ingroup misc … … 37 48 ///\code check(0==1,"This is obviously false.");\endcode will 38 49 ///print this (and then exits). 39 ///\verbatim graph_test.cc:123: error: This is obviously false. \endverbatim50 ///\verbatim digraph_test.cc:123: error: This is obviously false. \endverbatim 40 51 /// 41 52 ///\todo It should be in \c error.h … … 46 57 } else { } \ 47 58 59 ///Structure returned by \ref addPetersen(). 60 61 ///Structure returned by \ref addPetersen(). 62 /// 63 template<class Digraph> struct PetStruct 64 { 65 ///Vector containing the outer nodes. 66 std::vector<typename Digraph::Node> outer; 67 ///Vector containing the inner nodes. 68 std::vector<typename Digraph::Node> inner; 69 ///Vector containing the arcs of the inner circle. 70 std::vector<typename Digraph::Arc> incir; 71 ///Vector containing the arcs of the outer circle. 72 std::vector<typename Digraph::Arc> outcir; 73 ///Vector containing the chord arcs. 74 std::vector<typename Digraph::Arc> chords; 75 }; 76 77 78 79 ///Adds a Petersen digraph to \c G. 80 81 ///Adds a Petersen digraph to \c G. 82 ///\return The nodes and arcs of the generated digraph. 83 84 template<typename Digraph> 85 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) 86 { 87 PetStruct<Digraph> n; 88 89 for(int i=0;i<num;i++) { 90 n.outer.push_back(G.addNode()); 91 n.inner.push_back(G.addNode()); 92 } 93 94 for(int i=0;i<num;i++) { 95 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); 96 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); 97 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); 98 } 99 return n; 100 } 101 102 /// \brief Adds to the digraph the reverse pair of all arcs. 103 /// 104 /// Adds to the digraph the reverse pair of all arcs. 105 /// 106 template<class Digraph> void bidirDigraph(Digraph &G) 107 { 108 typedef typename Digraph::Arc Arc; 109 typedef typename Digraph::ArcIt ArcIt; 110 111 std::vector<Arc> ee; 112 113 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); 114 115 for(typename std::vector<Arc>::iterator p=ee.begin();p!=ee.end();p++) 116 G.addArc(G.target(*p),G.source(*p)); 117 } 118 119 120 /// \brief Checks the bidirectioned Petersen digraph. 121 /// 122 /// Checks the bidirectioned Petersen digraph. 123 /// 124 template<class Digraph> void checkBidirPetersen(Digraph &G, int num = 5) 125 { 126 typedef typename Digraph::Node Node; 127 128 typedef typename Digraph::ArcIt ArcIt; 129 typedef typename Digraph::NodeIt NodeIt; 130 131 checkDigraphNodeList(G, 2 * num); 132 checkDigraphArcList(G, 6 * num); 133 134 for(NodeIt n(G);n!=INVALID;++n) { 135 checkDigraphInArcList(G, n, 3); 136 checkDigraphOutArcList(G, n, 3); 137 } 138 } 139 140 ///Structure returned by \ref addUPetersen(). 141 142 ///Structure returned by \ref addUPetersen(). 143 /// 144 template<class Digraph> struct UPetStruct 145 { 146 ///Vector containing the outer nodes. 147 std::vector<typename Digraph::Node> outer; 148 ///Vector containing the inner nodes. 149 std::vector<typename Digraph::Node> inner; 150 ///Vector containing the arcs of the inner circle. 151 std::vector<typename Digraph::Edge> incir; 152 ///Vector containing the arcs of the outer circle. 153 std::vector<typename Digraph::Edge> outcir; 154 ///Vector containing the chord arcs. 155 std::vector<typename Digraph::Edge> chords; 156 }; 157 158 ///Adds a Petersen digraph to the undirected \c G. 159 160 ///Adds a Petersen digraph to the undirected \c G. 161 ///\return The nodes and arcs of the generated digraph. 162 163 template<typename Digraph> 164 UPetStruct<Digraph> addUPetersen(Digraph &G,int num=5) 165 { 166 UPetStruct<Digraph> n; 167 168 for(int i=0;i<num;i++) { 169 n.outer.push_back(G.addNode()); 170 n.inner.push_back(G.addNode()); 171 } 172 173 for(int i=0;i<num;i++) { 174 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); 175 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1)%5])); 176 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2)%5])); 177 } 178 return n; 179 } 180 48 181 #endif
Note: See TracChangeset
for help on using the changeset viewer.