Changeset 228:b6732e0d38c5 in lemon
- Timestamp:
- 07/21/08 16:30:28 (16 years ago)
- Branch:
- default
- Children:
- 229:aebc0161f6e5, 230:af4e8ba94294
- Phase:
- public
- Location:
- test
- Files:
-
- 1 deleted
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
test/Makefile.am
r203 r228 4 4 noinst_HEADERS += \ 5 5 test/graph_test.h \ 6 test/graph_maps_test.h \7 6 test/test_tools.h 8 7 -
test/bfs_test.cc
r222 r228 20 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 #include <lemon/lgf_reader.h> 22 23 #include <lemon/bfs.h> 23 24 #include <lemon/path.h> … … 27 28 28 29 using namespace lemon; 30 31 char test_lgf[] = 32 "@nodes\n" 33 "label\n" 34 "0\n" 35 "1\n" 36 "2\n" 37 "3\n" 38 "4\n" 39 "5\n" 40 "@arcs\n" 41 " label\n" 42 "0 1 0\n" 43 "1 2 1\n" 44 "2 3 2\n" 45 "3 4 3\n" 46 "0 3 4\n" 47 "0 3 5\n" 48 "5 2 6\n" 49 "@attributes\n" 50 "source 0\n" 51 "target 4\n"; 29 52 30 53 void checkBfsCompile() … … 50 73 n = bfs_test.predNode(n); 51 74 d = bfs_test.distMap(); 75 52 76 p = bfs_test.predMap(); 53 77 // pn = bfs_test.predNodeMap(); … … 81 105 Digraph G; 82 106 Node s, t; 83 PetStruct<Digraph> ps = addPetersen(G, 5);84 107 85 s=ps.outer[2]; 86 t=ps.inner[0]; 108 std::istringstream input(test_lgf); 109 digraphReader(input, G). 110 node("source", s). 111 node("target", t). 112 run(); 87 113 88 114 Bfs<Digraph> bfs_test(G); 89 115 bfs_test.run(s); 90 116 91 check(bfs_test.dist(t)== 3,"Bfs found a wrong path." << bfs_test.dist(t));117 check(bfs_test.dist(t)==2,"Bfs found a wrong path." << bfs_test.dist(t)); 92 118 93 119 Path<Digraph> p = bfs_test.path(t); 94 check(p.length()== 3,"path() found a wrong path.");120 check(p.length()==2,"path() found a wrong path."); 95 121 check(checkPath(G, p),"path() found a wrong path."); 96 122 check(pathSource(G, p) == s,"path() found a wrong path."); … … 98 124 99 125 100 for(ArcIt e(G); e!=INVALID; ++e) {101 Node u=G.source( e);102 Node v=G.target( e);126 for(ArcIt a(G); a!=INVALID; ++a) { 127 Node u=G.source(a); 128 Node v=G.target(a); 103 129 check( !bfs_test.reached(u) || 104 130 (bfs_test.dist(v) <= bfs_test.dist(u)+1), 105 "Wrong output." );131 "Wrong output." << G.id(v) << ' ' << G.id(u)); 106 132 } 107 133 108 134 for(NodeIt v(G); v!=INVALID; ++v) { 109 check(bfs_test.reached(v),"Each node should be reached."); 110 if ( bfs_test.predArc(v)!=INVALID ) { 111 Arc e=bfs_test.predArc(v); 112 Node u=G.source(e); 113 check(u==bfs_test.predNode(v),"Wrong tree."); 114 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, 115 "Wrong distance. Difference: " 116 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 117 - 1)); 135 if (bfs_test.reached(v)) { 136 check(v==s || bfs_test.predArc(v)!=INVALID, "Wrong tree."); 137 if (bfs_test.predArc(v)!=INVALID ) { 138 Arc a=bfs_test.predArc(v); 139 Node u=G.source(a); 140 check(u==bfs_test.predNode(v),"Wrong tree."); 141 check(bfs_test.dist(v) - bfs_test.dist(u) == 1, 142 "Wrong distance. Difference: " 143 << std::abs(bfs_test.dist(v) - bfs_test.dist(u) 144 - 1)); 145 } 118 146 } 119 147 } -
test/dfs_test.cc
r209 r228 20 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 #include <lemon/lgf_reader.h> 23 22 24 #include <lemon/dfs.h> 23 25 #include <lemon/path.h> … … 27 29 28 30 using namespace lemon; 31 32 char test_lgf[] = 33 "@nodes\n" 34 "label\n" 35 "0\n" 36 "1\n" 37 "2\n" 38 "3\n" 39 "4\n" 40 "5\n" 41 "6\n" 42 "@arcs\n" 43 " label\n" 44 "0 1 0\n" 45 "1 2 1\n" 46 "2 3 2\n" 47 "1 4 3\n" 48 "4 2 4\n" 49 "4 5 5\n" 50 "5 0 6\n" 51 "6 3 7\n" 52 "@attributes\n" 53 "source 0\n" 54 "target 5\n"; 29 55 30 56 void checkDfsCompile() … … 40 66 DType::DistMap d(G); 41 67 DType::PredMap p(G); 42 // DType::PredNodeMap pn(G);43 68 44 69 DType dfs_test(G); … … 51 76 d = dfs_test.distMap(); 52 77 p = dfs_test.predMap(); 53 // pn = dfs_test.predNodeMap();54 78 b = dfs_test.reached(n); 55 79 … … 81 105 Digraph G; 82 106 Node s, t; 83 PetStruct<Digraph> ps = addPetersen(G, 5);84 107 85 s=ps.outer[2]; 86 t=ps.inner[0]; 108 std::istringstream input(test_lgf); 109 digraphReader(input, G). 110 node("source", s). 111 node("target", t). 112 run(); 87 113 88 114 Dfs<Digraph> dfs_test(G); … … 96 122 97 123 for(NodeIt v(G); v!=INVALID; ++v) { 98 check(dfs_test.reached(v),"Each node should be reached."); 99 if ( dfs_test.predArc(v)!=INVALID ) { 100 Arc e=dfs_test.predArc(v); 101 Node u=G.source(e); 102 check(u==dfs_test.predNode(v),"Wrong tree."); 103 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, 104 "Wrong distance. (" << dfs_test.dist(u) << "->" 105 <<dfs_test.dist(v) << ')'); 124 if (dfs_test.reached(v)) { 125 check(v==s || dfs_test.predArc(v)!=INVALID, "Wrong tree."); 126 if (dfs_test.predArc(v)!=INVALID ) { 127 Arc e=dfs_test.predArc(v); 128 Node u=G.source(e); 129 check(u==dfs_test.predNode(v),"Wrong tree."); 130 check(dfs_test.dist(v) - dfs_test.dist(u) == 1, 131 "Wrong distance. (" << dfs_test.dist(u) << "->" 132 <<dfs_test.dist(v) << ')'); 133 } 106 134 } 107 135 } -
test/digraph_test.cc
r209 r228 25 25 #include "test_tools.h" 26 26 #include "graph_test.h" 27 #include "graph_maps_test.h"28 27 29 28 using namespace lemon; 30 29 using namespace lemon::concepts; 31 30 32 void check_concepts() { 31 template <class Digraph> 32 void checkDigraph() { 33 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 34 Digraph G; 35 36 checkGraphNodeList(G, 0); 37 checkGraphArcList(G, 0); 38 39 Node 40 n1 = G.addNode(), 41 n2 = G.addNode(), 42 n3 = G.addNode(); 43 checkGraphNodeList(G, 3); 44 checkGraphArcList(G, 0); 45 46 Arc a1 = G.addArc(n1, n2); 47 check(G.source(a1) == n1 && G.target(a1) == n2, "Wrong arc"); 48 checkGraphNodeList(G, 3); 49 checkGraphArcList(G, 1); 50 51 checkGraphOutArcList(G, n1, 1); 52 checkGraphOutArcList(G, n2, 0); 53 checkGraphOutArcList(G, n3, 0); 54 55 checkGraphInArcList(G, n1, 0); 56 checkGraphInArcList(G, n2, 1); 57 checkGraphInArcList(G, n3, 0); 58 59 checkGraphConArcList(G, 1); 60 61 Arc a2 = G.addArc(n2, n1), a3 = G.addArc(n2, n3), a4 = G.addArc(n2, n3); 62 checkGraphNodeList(G, 3); 63 checkGraphArcList(G, 4); 64 65 checkGraphOutArcList(G, n1, 1); 66 checkGraphOutArcList(G, n2, 3); 67 checkGraphOutArcList(G, n3, 0); 68 69 checkGraphInArcList(G, n1, 1); 70 checkGraphInArcList(G, n2, 1); 71 checkGraphInArcList(G, n3, 2); 72 73 checkGraphConArcList(G, 4); 74 75 checkNodeIds(G); 76 checkArcIds(G); 77 checkGraphNodeMap(G); 78 checkGraphArcMap(G); 79 80 } 81 82 83 void checkConcepts() { 33 84 { // Checking digraph components 34 85 checkConcept<BaseDigraphComponent, BaseDigraphComponent >(); … … 52 103 checkConcept<ClearableDigraphComponent<>, ListDigraph>(); 53 104 checkConcept<ErasableDigraphComponent<>, ListDigraph>(); 54 checkDigraphIterators<ListDigraph>();55 105 } 56 106 { // Checking SmartDigraph … … 59 109 checkConcept<ExtendableDigraphComponent<>, SmartDigraph>(); 60 110 checkConcept<ClearableDigraphComponent<>, SmartDigraph>(); 61 checkDigraphIterators<SmartDigraph>();62 111 } 63 112 // { // Checking FullDigraph 64 113 // checkConcept<Digraph, FullDigraph>(); 65 // checkDigraphIterators<FullDigraph>();66 114 // } 67 115 // { // Checking HyperCubeDigraph 68 116 // checkConcept<Digraph, HyperCubeDigraph>(); 69 // checkDigraphIterators<HyperCubeDigraph>();70 117 // } 71 118 } 72 119 73 120 template <typename Digraph> 74 void check _graph_validity() {121 void checkDigraphValidity() { 75 122 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 76 123 Digraph g; … … 93 140 94 141 template <typename Digraph> 95 void check _graph_validity_erase() {142 void checkDigraphValidityErase() { 96 143 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 97 144 Digraph g; … … 121 168 } 122 169 123 void check _digraphs() {170 void checkDigraphs() { 124 171 { // Checking ListDigraph 125 172 checkDigraph<ListDigraph>(); 126 checkGraphNodeMap<ListDigraph>(); 127 checkGraphArcMap<ListDigraph>(); 128 129 check_graph_validity_erase<ListDigraph>(); 173 checkDigraphValidityErase<ListDigraph>(); 130 174 } 131 175 { // Checking SmartDigraph 132 176 checkDigraph<SmartDigraph>(); 133 checkGraphNodeMap<SmartDigraph>(); 134 checkGraphArcMap<SmartDigraph>(); 135 136 check_graph_validity<SmartDigraph>(); 177 checkDigraphValidity<SmartDigraph>(); 137 178 } 138 179 } 139 180 140 181 int main() { 141 check _concepts();142 check _digraphs();182 checkDigraphs(); 183 checkConcepts(); 143 184 return 0; 144 185 } -
test/dijkstra_test.cc
r220 r228 20 20 #include <lemon/smart_graph.h> 21 21 #include <lemon/list_graph.h> 22 #include <lemon/lgf_reader.h> 23 22 24 #include <lemon/dijkstra.h> 23 25 #include <lemon/path.h> … … 27 29 28 30 using namespace lemon; 31 32 char test_lgf[] = 33 "@nodes\n" 34 "label\n" 35 "0\n" 36 "1\n" 37 "2\n" 38 "3\n" 39 "4\n" 40 "@arcs\n" 41 " label length\n" 42 "0 1 0 1\n" 43 "1 2 1 1\n" 44 "2 3 2 1\n" 45 "0 3 4 5\n" 46 "0 3 5 10\n" 47 "0 3 6 7\n" 48 "4 2 7 1\n" 49 "@attributes\n" 50 "source 0\n" 51 "target 3\n"; 29 52 30 53 void checkDijkstraCompile() … … 85 108 Node s, t; 86 109 LengthMap length(G); 87 PetStruct<Digraph> ps = addPetersen(G, 5);88 110 89 for(int i=0;i<5;i++) { 90 length[ps.outcir[i]]=4; 91 length[ps.incir[i]]=1; 92 length[ps.chords[i]]=10; 93 } 94 s=ps.outer[0]; 95 t=ps.inner[1]; 111 std::istringstream input(test_lgf); 112 digraphReader(input, G). 113 arcMap("length", length). 114 node("source", s). 115 node("target", t). 116 run(); 96 117 97 118 Dijkstra<Digraph, LengthMap> … … 99 120 dijkstra_test.run(s); 100 121 101 check(dijkstra_test.dist(t)== 13,"Dijkstra found a wrong path.");122 check(dijkstra_test.dist(t)==3,"Dijkstra found a wrong path."); 102 123 103 124 Path<Digraph> p = dijkstra_test.path(t); 104 check(p.length()== 4,"getPath() found a wrong path.");125 check(p.length()==3,"getPath() found a wrong path."); 105 126 check(checkPath(G, p),"path() found a wrong path."); 106 127 check(pathSource(G, p) == s,"path() found a wrong path."); … … 116 137 } 117 138 118 for(NodeIt v(G); v!=INVALID; ++v){ 119 check(dijkstra_test.reached(v),"Each node should be reached."); 120 if ( dijkstra_test.predArc(v)!=INVALID ) { 121 Arc e=dijkstra_test.predArc(v); 122 Node u=G.source(e); 123 check(u==dijkstra_test.predNode(v),"Wrong tree."); 124 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], 125 "Wrong distance! Difference: " << 126 std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e])); 139 for(NodeIt v(G); v!=INVALID; ++v) { 140 if (dijkstra_test.reached(v)) { 141 check(v==s || dijkstra_test.predArc(v)!=INVALID, "Wrong tree."); 142 if (dijkstra_test.predArc(v)!=INVALID ) { 143 Arc e=dijkstra_test.predArc(v); 144 Node u=G.source(e); 145 check(u==dijkstra_test.predNode(v),"Wrong tree."); 146 check(dijkstra_test.dist(v) - dijkstra_test.dist(u) == length[e], 147 "Wrong distance! Difference: " << 148 std::abs(dijkstra_test.dist(v)-dijkstra_test.dist(u)-length[e])); 149 } 127 150 } 128 151 } -
test/graph_test.cc
r209 r228 25 25 #include "test_tools.h" 26 26 #include "graph_test.h" 27 #include "graph_maps_test.h"28 27 29 28 using namespace lemon; 30 29 using namespace lemon::concepts; 31 30 32 void check_concepts() { 31 template <class Graph> 32 void checkGraph() { 33 TEMPLATE_GRAPH_TYPEDEFS(Graph); 34 35 Graph G; 36 checkGraphNodeList(G, 0); 37 checkGraphEdgeList(G, 0); 38 39 Node 40 n1 = G.addNode(), 41 n2 = G.addNode(), 42 n3 = G.addNode(); 43 checkGraphNodeList(G, 3); 44 checkGraphEdgeList(G, 0); 45 46 Edge e1 = G.addEdge(n1, n2); 47 check((G.u(e1) == n1 && G.v(e1) == n2) || (G.u(e1) == n2 && G.v(e1) == n1), 48 "Wrong edge"); 49 checkGraphNodeList(G, 3); 50 checkGraphArcList(G, 2); 51 checkGraphEdgeList(G, 1); 52 53 checkGraphOutArcList(G, n1, 1); 54 checkGraphOutArcList(G, n2, 1); 55 checkGraphOutArcList(G, n3, 0); 56 57 checkGraphInArcList(G, n1, 1); 58 checkGraphInArcList(G, n2, 1); 59 checkGraphInArcList(G, n3, 0); 60 61 checkGraphIncEdgeList(G, n1, 1); 62 checkGraphIncEdgeList(G, n2, 1); 63 checkGraphIncEdgeList(G, n3, 0); 64 65 checkGraphConArcList(G, 2); 66 checkGraphConEdgeList(G, 1); 67 68 Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3); 69 checkGraphNodeList(G, 3); 70 checkGraphArcList(G, 6); 71 checkGraphEdgeList(G, 3); 72 73 checkGraphOutArcList(G, n1, 2); 74 checkGraphOutArcList(G, n2, 3); 75 checkGraphOutArcList(G, n3, 1); 76 77 checkGraphInArcList(G, n1, 2); 78 checkGraphInArcList(G, n2, 3); 79 checkGraphInArcList(G, n3, 1); 80 81 checkGraphIncEdgeList(G, n1, 2); 82 checkGraphIncEdgeList(G, n2, 3); 83 checkGraphIncEdgeList(G, n3, 1); 84 85 checkGraphConArcList(G, 6); 86 checkGraphConEdgeList(G, 3); 87 88 checkArcDirections(G); 89 90 checkNodeIds(G); 91 checkArcIds(G); 92 checkEdgeIds(G); 93 checkGraphNodeMap(G); 94 checkGraphArcMap(G); 95 checkGraphEdgeMap(G); 96 } 97 98 void checkConcepts() { 33 99 { // Checking graph components 34 100 checkConcept<BaseGraphComponent, BaseGraphComponent >(); … … 52 118 checkConcept<ClearableGraphComponent<>, ListGraph>(); 53 119 checkConcept<ErasableGraphComponent<>, ListGraph>(); 54 checkGraphIterators<ListGraph>();55 120 } 56 121 { // Checking SmartGraph … … 59 124 checkConcept<ExtendableGraphComponent<>, SmartGraph>(); 60 125 checkConcept<ClearableGraphComponent<>, SmartGraph>(); 61 checkGraphIterators<SmartGraph>();62 126 } 63 127 // { // Checking FullGraph … … 72 136 73 137 template <typename Graph> 74 void check _graph_validity() {138 void checkGraphValidity() { 75 139 TEMPLATE_GRAPH_TYPEDEFS(Graph); 76 140 Graph g; … … 95 159 96 160 template <typename Graph> 97 void check _graph_validity_erase() {161 void checkGraphValidityErase() { 98 162 TEMPLATE_GRAPH_TYPEDEFS(Graph); 99 163 Graph g; … … 169 233 // } 170 234 171 void check _graphs() {235 void checkGraphs() { 172 236 { // Checking ListGraph 173 237 checkGraph<ListGraph>(); 174 checkGraphNodeMap<ListGraph>(); 175 checkGraphEdgeMap<ListGraph>(); 176 177 check_graph_validity_erase<ListGraph>(); 238 checkGraphValidityErase<ListGraph>(); 178 239 } 179 240 { // Checking SmartGraph 180 241 checkGraph<SmartGraph>(); 181 checkGraphNodeMap<SmartGraph>(); 182 checkGraphEdgeMap<SmartGraph>(); 183 184 check_graph_validity<SmartGraph>(); 242 checkGraphValidity<SmartGraph>(); 185 243 } 186 244 // { // Checking FullGraph … … 198 256 199 257 int main() { 200 check _concepts();201 check _graphs();258 checkConcepts(); 259 checkGraphs(); 202 260 return 0; 203 261 } -
test/graph_test.h
r220 r228 20 20 #define LEMON_TEST_GRAPH_TEST_H 21 21 22 #include <set> 23 22 24 #include <lemon/core.h> 25 #include <lemon/maps.h> 26 23 27 #include "test_tools.h" 24 28 … … 43 47 for(int i=0;i<cnt;i++) { 44 48 check(e!=INVALID,"Wrong Arc list linking."); 49 check(G.oppositeNode(G.source(e), e) == G.target(e), 50 "Wrong opposite node"); 51 check(G.oppositeNode(G.target(e), e) == G.source(e), 52 "Wrong opposite node"); 45 53 ++e; 46 54 } … … 56 64 check(e!=INVALID,"Wrong OutArc list linking."); 57 65 check(n==G.source(e),"Wrong OutArc list linking."); 66 check(n==G.baseNode(e),"Wrong OutArc list linking."); 67 check(G.target(e)==G.runningNode(e),"Wrong OutArc list linking."); 58 68 ++e; 59 69 } … … 69 79 check(e!=INVALID,"Wrong InArc list linking."); 70 80 check(n==G.target(e),"Wrong InArc list linking."); 81 check(n==G.baseNode(e),"Wrong OutArc list linking."); 82 check(G.source(e)==G.runningNode(e),"Wrong OutArc list linking."); 71 83 ++e; 72 84 } … … 81 93 for(int i=0;i<cnt;i++) { 82 94 check(e!=INVALID,"Wrong Edge list linking."); 95 check(G.oppositeNode(G.u(e), e) == G.v(e), "Wrong opposite node"); 96 check(G.oppositeNode(G.v(e), e) == G.u(e), "Wrong opposite node"); 83 97 ++e; 84 98 } … … 94 108 check(e!=INVALID,"Wrong IncEdge list linking."); 95 109 check(n==G.u(e) || n==G.v(e),"Wrong IncEdge list linking."); 110 check(n==G.baseNode(e),"Wrong OutArc list linking."); 111 check(G.u(e)==G.runningNode(e) || G.v(e)==G.runningNode(e), 112 "Wrong OutArc list linking."); 96 113 ++e; 97 114 } … … 100 117 } 101 118 102 template <class Digraph>103 void checkDigraphIterators() {104 typedef typename Digraph::Node Node;105 typedef typename Digraph::NodeIt NodeIt;106 typedef typename Digraph::Arc Arc;107 typedef typename Digraph::ArcIt ArcIt;108 typedef typename Digraph::InArcIt InArcIt;109 typedef typename Digraph::OutArcIt OutArcIt;110 }111 112 119 template <class Graph> 113 void checkGraphIterators() { 114 checkDigraphIterators<Graph>(); 120 void checkGraphConArcList(const Graph &G, int cnt) { 121 int i = 0; 122 for (typename Graph::NodeIt u(G); u != INVALID; ++u) { 123 for (typename Graph::NodeIt v(G); v != INVALID; ++v) { 124 for (ConArcIt<Graph> a(G, u, v); a != INVALID; ++a) { 125 check(G.source(a) == u, "Wrong iterator."); 126 check(G.target(a) == v, "Wrong iterator."); 127 ++i; 128 } 129 } 130 } 131 check(cnt == i, "Wrong iterator."); 132 } 133 134 template <class Graph> 135 void checkGraphConEdgeList(const Graph &G, int cnt) { 136 int i = 0; 137 for (typename Graph::NodeIt u(G); u != INVALID; ++u) { 138 for (typename Graph::NodeIt v(G); v != INVALID; ++v) { 139 for (ConEdgeIt<Graph> e(G, u, v); e != INVALID; ++e) { 140 check((G.u(e) == u && G.v(e) == v) || 141 (G.u(e) == v && G.v(e) == u), "Wrong iterator."); 142 i += u == v ? 2 : 1; 143 } 144 } 145 } 146 check(2 * cnt == i, "Wrong iterator."); 147 } 148 149 template <typename Graph> 150 void checkArcDirections(const Graph& G) { 151 for (typename Graph::ArcIt a(G); a != INVALID; ++a) { 152 check(G.source(a) == G.target(G.oppositeArc(a)), "Wrong direction"); 153 check(G.target(a) == G.source(G.oppositeArc(a)), "Wrong direction"); 154 check(G.direct(a, G.direction(a)) == a, "Wrong direction"); 155 } 156 } 157 158 template <typename Graph> 159 void checkNodeIds(const Graph& G) { 160 std::set<int> values; 161 for (typename Graph::NodeIt n(G); n != INVALID; ++n) { 162 check(G.nodeFromId(G.id(n)) == n, "Wrong id"); 163 check(values.find(G.id(n)) == values.end(), "Wrong id"); 164 check(G.id(n) <= G.maxNodeId(), "Wrong maximum id"); 165 values.insert(G.id(n)); 166 } 167 } 168 169 template <typename Graph> 170 void checkArcIds(const Graph& G) { 171 std::set<int> values; 172 for (typename Graph::ArcIt a(G); a != INVALID; ++a) { 173 check(G.arcFromId(G.id(a)) == a, "Wrong id"); 174 check(values.find(G.id(a)) == values.end(), "Wrong id"); 175 check(G.id(a) <= G.maxArcId(), "Wrong maximum id"); 176 values.insert(G.id(a)); 177 } 178 } 179 180 template <typename Graph> 181 void checkEdgeIds(const Graph& G) { 182 std::set<int> values; 183 for (typename Graph::EdgeIt e(G); e != INVALID; ++e) { 184 check(G.edgeFromId(G.id(e)) == e, "Wrong id"); 185 check(values.find(G.id(e)) == values.end(), "Wrong id"); 186 check(G.id(e) <= G.maxEdgeId(), "Wrong maximum id"); 187 values.insert(G.id(e)); 188 } 189 } 190 191 template <typename Graph> 192 void checkGraphNodeMap(const Graph& G) { 193 typedef typename Graph::Node Node; 194 typedef typename Graph::NodeIt NodeIt; 195 196 typedef typename Graph::template NodeMap<int> IntNodeMap; 197 IntNodeMap map(G, 42); 198 for (NodeIt it(G); it != INVALID; ++it) { 199 check(map[it] == 42, "Wrong map constructor."); 200 } 201 int s = 0; 202 for (NodeIt it(G); it != INVALID; ++it) { 203 map[it] = 0; 204 check(map[it] == 0, "Wrong operator[]."); 205 map.set(it, s); 206 check(map[it] == s, "Wrong set."); 207 ++s; 208 } 209 s = s * (s - 1) / 2; 210 for (NodeIt it(G); it != INVALID; ++it) { 211 s -= map[it]; 212 } 213 check(s == 0, "Wrong sum."); 214 215 map = constMap<Node>(12); 216 for (NodeIt it(G); it != INVALID; ++it) { 217 check(map[it] == 12, "Wrong operator[]."); 218 } 219 } 220 221 template <typename Graph> 222 void checkGraphArcMap(const Graph& G) { 223 typedef typename Graph::Arc Arc; 224 typedef typename Graph::ArcIt ArcIt; 225 226 typedef typename Graph::template ArcMap<int> IntArcMap; 227 IntArcMap map(G, 42); 228 for (ArcIt it(G); it != INVALID; ++it) { 229 check(map[it] == 42, "Wrong map constructor."); 230 } 231 int s = 0; 232 for (ArcIt it(G); it != INVALID; ++it) { 233 map[it] = 0; 234 check(map[it] == 0, "Wrong operator[]."); 235 map.set(it, s); 236 check(map[it] == s, "Wrong set."); 237 ++s; 238 } 239 s = s * (s - 1) / 2; 240 for (ArcIt it(G); it != INVALID; ++it) { 241 s -= map[it]; 242 } 243 check(s == 0, "Wrong sum."); 244 245 map = constMap<Arc>(12); 246 for (ArcIt it(G); it != INVALID; ++it) { 247 check(map[it] == 12, "Wrong operator[]."); 248 } 249 } 250 251 template <typename Graph> 252 void checkGraphEdgeMap(const Graph& G) { 115 253 typedef typename Graph::Edge Edge; 116 254 typedef typename Graph::EdgeIt EdgeIt; 117 typedef typename Graph::IncEdgeIt IncEdgeIt; 118 } 119 120 // Structure returned by addPetersen() 121 template<class Digraph> 122 struct PetStruct 123 { 124 // Vector containing the outer nodes 125 std::vector<typename Digraph::Node> outer; 126 // Vector containing the inner nodes 127 std::vector<typename Digraph::Node> inner; 128 // Vector containing the arcs of the inner circle 129 std::vector<typename Digraph::Arc> incir; 130 // Vector containing the arcs of the outer circle 131 std::vector<typename Digraph::Arc> outcir; 132 // Vector containing the chord arcs 133 std::vector<typename Digraph::Arc> chords; 134 }; 135 136 // Adds the reverse pair of all arcs to a digraph 137 template<class Digraph> 138 void bidirDigraph(Digraph &G) 139 { 140 typedef typename Digraph::Arc Arc; 141 typedef typename Digraph::ArcIt ArcIt; 142 143 std::vector<Arc> ee; 144 145 for(ArcIt e(G);e!=INVALID;++e) ee.push_back(e); 146 147 for(int i=0;i<int(ee.size());++i) 148 G.addArc(G.target(ee[i]),G.source(ee[i])); 149 } 150 151 // Adds a Petersen digraph to G. 152 // Returns the nodes and arcs of the generated digraph. 153 template<typename Digraph> 154 PetStruct<Digraph> addPetersen(Digraph &G,int num = 5) 155 { 156 PetStruct<Digraph> n; 157 158 for(int i=0;i<num;i++) { 159 n.outer.push_back(G.addNode()); 160 n.inner.push_back(G.addNode()); 161 } 162 163 for(int i=0;i<num;i++) { 164 n.chords.push_back(G.addArc(n.outer[i],n.inner[i])); 165 n.outcir.push_back(G.addArc(n.outer[i],n.outer[(i+1) % num])); 166 n.incir.push_back(G.addArc(n.inner[i],n.inner[(i+2) % num])); 167 } 168 169 return n; 170 } 171 172 // Checks the bidirectioned Petersen digraph 173 template<class Digraph> 174 void checkBidirPetersen(const Digraph &G, int num = 5) 175 { 176 typedef typename Digraph::NodeIt NodeIt; 177 178 checkGraphNodeList(G, 2 * num); 179 checkGraphArcList(G, 6 * num); 180 181 for(NodeIt n(G);n!=INVALID;++n) { 182 checkGraphInArcList(G, n, 3); 183 checkGraphOutArcList(G, n, 3); 184 } 185 } 186 187 // Structure returned by addUPetersen() 188 template<class Graph> 189 struct UPetStruct 190 { 191 // Vector containing the outer nodes 192 std::vector<typename Graph::Node> outer; 193 // Vector containing the inner nodes 194 std::vector<typename Graph::Node> inner; 195 // Vector containing the edges of the inner circle 196 std::vector<typename Graph::Edge> incir; 197 // Vector containing the edges of the outer circle 198 std::vector<typename Graph::Edge> outcir; 199 // Vector containing the chord edges 200 std::vector<typename Graph::Edge> chords; 201 }; 202 203 // Adds a Petersen graph to \c G. 204 // Returns the nodes and edges of the generated graph. 205 template<typename Graph> 206 UPetStruct<Graph> addUPetersen(Graph &G,int num=5) 207 { 208 UPetStruct<Graph> n; 209 210 for(int i=0;i<num;i++) { 211 n.outer.push_back(G.addNode()); 212 n.inner.push_back(G.addNode()); 213 } 214 215 for(int i=0;i<num;i++) { 216 n.chords.push_back(G.addEdge(n.outer[i],n.inner[i])); 217 n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%num])); 218 n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%num])); 219 } 220 221 return n; 222 } 223 224 // Checks the undirected Petersen graph 225 template<class Graph> 226 void checkUndirPetersen(const Graph &G, int num = 5) 227 { 228 typedef typename Graph::NodeIt NodeIt; 229 230 checkGraphNodeList(G, 2 * num); 231 checkGraphEdgeList(G, 3 * num); 232 checkGraphArcList(G, 6 * num); 233 234 for(NodeIt n(G);n!=INVALID;++n) { 235 checkGraphIncEdgeList(G, n, 3); 236 } 237 } 238 239 template <class Digraph> 240 void checkDigraph() { 241 const int num = 5; 242 Digraph G; 243 checkGraphNodeList(G, 0); 244 checkGraphArcList(G, 0); 245 addPetersen(G, num); 246 bidirDigraph(G); 247 checkBidirPetersen(G, num); 248 } 249 250 template <class Graph> 251 void checkGraph() { 252 const int num = 5; 253 Graph G; 254 checkGraphNodeList(G, 0); 255 checkGraphEdgeList(G, 0); 256 addUPetersen(G, num); 257 checkUndirPetersen(G, num); 258 } 255 256 typedef typename Graph::template EdgeMap<int> IntEdgeMap; 257 IntEdgeMap map(G, 42); 258 for (EdgeIt it(G); it != INVALID; ++it) { 259 check(map[it] == 42, "Wrong map constructor."); 260 } 261 int s = 0; 262 for (EdgeIt it(G); it != INVALID; ++it) { 263 map[it] = 0; 264 check(map[it] == 0, "Wrong operator[]."); 265 map.set(it, s); 266 check(map[it] == s, "Wrong set."); 267 ++s; 268 } 269 s = s * (s - 1) / 2; 270 for (EdgeIt it(G); it != INVALID; ++it) { 271 s -= map[it]; 272 } 273 check(s == 0, "Wrong sum."); 274 275 map = constMap<Edge>(12); 276 for (EdgeIt it(G); it != INVALID; ++it) { 277 check(map[it] == 12, "Wrong operator[]."); 278 } 279 } 280 259 281 260 282 } //namespace lemon
Note: See TracChangeset
for help on using the changeset viewer.