Changeset 432:76287c8caa26 in lemon for test
- Timestamp:
- 11/30/08 19:18:32 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
test/graph_adaptor_test.cc
r431 r432 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 5 * Copyright (C) 2003-2008 … … 26 26 #include<lemon/concepts/graph.h> 27 27 28 #include<lemon/digraph_adaptor.h> 29 #include<lemon/graph_adaptor.h> 28 #include<lemon/adaptors.h> 30 29 31 30 #include <limits> … … 38 37 using namespace lemon; 39 38 40 void checkRev DigraphAdaptor() {41 checkConcept<concepts::Digraph, Rev DigraphAdaptor<concepts::Digraph> >();39 void checkReverseDigraph() { 40 checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >(); 42 41 43 42 typedef ListDigraph Digraph; 44 typedef Rev DigraphAdaptor<Digraph> Adaptor;43 typedef ReverseDigraph<Digraph> Adaptor; 45 44 46 45 Digraph digraph; … … 54 53 Digraph::Arc a2 = digraph.addArc(n1, n3); 55 54 Digraph::Arc a3 = digraph.addArc(n2, n3); 56 55 57 56 checkGraphNodeList(adaptor, 3); 58 57 checkGraphArcList(adaptor, 3); … … 79 78 } 80 79 81 void checkSubDigraph Adaptor() {82 checkConcept<concepts::Digraph, 83 SubDigraph Adaptor<concepts::Digraph,80 void checkSubDigraph() { 81 checkConcept<concepts::Digraph, 82 SubDigraph<concepts::Digraph, 84 83 concepts::Digraph::NodeMap<bool>, 85 84 concepts::Digraph::ArcMap<bool> > >(); … … 88 87 typedef Digraph::NodeMap<bool> NodeFilter; 89 88 typedef Digraph::ArcMap<bool> ArcFilter; 90 typedef SubDigraph Adaptor<Digraph, NodeFilter, ArcFilter> Adaptor;89 typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor; 91 90 92 91 Digraph digraph; … … 124 123 checkGraphArcMap(adaptor); 125 124 126 arc_filter[a2] = false; 125 arc_filter[a2] = false; 127 126 128 127 checkGraphNodeList(adaptor, 3); … … 144 143 checkGraphArcMap(adaptor); 145 144 146 node_filter[n1] = false; 145 node_filter[n1] = false; 147 146 148 147 checkGraphNodeList(adaptor, 2); … … 176 175 } 177 176 178 void check NodeSubDigraphAdaptor() {179 checkConcept<concepts::Digraph, 180 NodeSubDigraphAdaptor<concepts::Digraph,177 void checkFilterNodes1() { 178 checkConcept<concepts::Digraph, 179 FilterNodes<concepts::Digraph, 181 180 concepts::Digraph::NodeMap<bool> > >(); 182 181 183 182 typedef ListDigraph Digraph; 184 183 typedef Digraph::NodeMap<bool> NodeFilter; 185 typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;184 typedef FilterNodes<Digraph, NodeFilter> Adaptor; 186 185 187 186 Digraph digraph; … … 217 216 checkGraphArcMap(adaptor); 218 217 219 node_filter[n1] = false; 218 node_filter[n1] = false; 220 219 221 220 checkGraphNodeList(adaptor, 2); … … 248 247 } 249 248 250 void check ArcSubDigraphAdaptor() {251 checkConcept<concepts::Digraph, 252 ArcSubDigraphAdaptor<concepts::Digraph,249 void checkFilterArcs() { 250 checkConcept<concepts::Digraph, 251 FilterArcs<concepts::Digraph, 253 252 concepts::Digraph::ArcMap<bool> > >(); 254 253 255 254 typedef ListDigraph Digraph; 256 255 typedef Digraph::ArcMap<bool> ArcFilter; 257 typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;256 typedef FilterArcs<Digraph, ArcFilter> Adaptor; 258 257 259 258 Digraph digraph; … … 289 288 checkGraphArcMap(adaptor); 290 289 291 arc_filter[a2] = false; 290 arc_filter[a2] = false; 292 291 293 292 checkGraphNodeList(adaptor, 3); … … 322 321 } 323 322 324 void checkUndir DigraphAdaptor() {325 checkConcept<concepts::Graph, Undir DigraphAdaptor<concepts::Digraph> >();323 void checkUndirector() { 324 checkConcept<concepts::Graph, Undirector<concepts::Digraph> >(); 326 325 327 326 typedef ListDigraph Digraph; 328 typedef Undir DigraphAdaptor<Digraph> Adaptor;327 typedef Undirector<Digraph> Adaptor; 329 328 330 329 Digraph digraph; … … 338 337 Digraph::Arc a2 = digraph.addArc(n1, n3); 339 338 Digraph::Arc a3 = digraph.addArc(n2, n3); 340 339 341 340 checkGraphNodeList(adaptor, 3); 342 341 checkGraphArcList(adaptor, 6); … … 372 371 } 373 372 374 void checkRes DigraphAdaptor() {375 checkConcept<concepts::Digraph, 376 Res DigraphAdaptor<concepts::Digraph,377 concepts::Digraph::ArcMap<int>, 373 void checkResidual() { 374 checkConcept<concepts::Digraph, 375 Residual<concepts::Digraph, 376 concepts::Digraph::ArcMap<int>, 378 377 concepts::Digraph::ArcMap<int> > >(); 379 378 380 379 typedef ListDigraph Digraph; 381 380 typedef Digraph::ArcMap<int> IntArcMap; 382 typedef Res DigraphAdaptor<Digraph, IntArcMap> Adaptor;381 typedef Residual<Digraph, IntArcMap> Adaptor; 383 382 384 383 Digraph digraph; … … 408 407 flow[a] = 0; 409 408 } 410 409 411 410 checkGraphNodeList(adaptor, 4); 412 411 checkGraphArcList(adaptor, 6); … … 426 425 flow[a] = capacity[a] / 2; 427 426 } 428 427 429 428 checkGraphNodeList(adaptor, 4); 430 429 checkGraphArcList(adaptor, 12); … … 450 449 flow[a] = capacity[a]; 451 450 } 452 451 453 452 checkGraphNodeList(adaptor, 4); 454 453 checkGraphArcList(adaptor, 6); … … 471 470 int flow_value = 0; 472 471 while (true) { 473 472 474 473 Bfs<Adaptor> bfs(adaptor); 475 474 bfs.run(n1, n4); 476 475 477 476 if (!bfs.reached(n4)) break; 478 477 479 478 Path<Adaptor> p = bfs.path(n4); 480 479 481 480 int min = std::numeric_limits<int>::max(); 482 481 for (Path<Adaptor>::ArcIt a(p); a != INVALID; ++a) { 483 if (adaptor.rescap(a) < min) min = adaptor.rescap(a); 482 if (adaptor.residualCapacity(a) < min) 483 min = adaptor.residualCapacity(a); 484 484 } 485 485 … … 494 494 } 495 495 496 void checkSplit DigraphAdaptor() {497 checkConcept<concepts::Digraph, Split DigraphAdaptor<concepts::Digraph> >();496 void checkSplitNodes() { 497 checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >(); 498 498 499 499 typedef ListDigraph Digraph; 500 typedef Split DigraphAdaptor<Digraph> Adaptor;500 typedef SplitNodes<Digraph> Adaptor; 501 501 502 502 Digraph digraph; … … 510 510 Digraph::Arc a2 = digraph.addArc(n1, n3); 511 511 Digraph::Arc a3 = digraph.addArc(n2, n3); 512 512 513 513 checkGraphNodeList(adaptor, 6); 514 514 checkGraphArcList(adaptor, 6); … … 531 531 checkNodeIds(adaptor); 532 532 checkArcIds(adaptor); 533 533 534 534 checkGraphNodeMap(adaptor); 535 535 checkGraphArcMap(adaptor); … … 538 538 if (adaptor.origArc(a)) { 539 539 Digraph::Arc oa = a; 540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 541 542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 543 "Wrong split"); 540 check(adaptor.source(a) == adaptor.outNode(digraph.source(oa)), 541 "Wrong split"); 542 check(adaptor.target(a) == adaptor.inNode(digraph.target(oa)), 543 "Wrong split"); 544 544 } else { 545 545 Digraph::Node on = a; … … 550 550 } 551 551 552 void checkSubGraph Adaptor() {553 checkConcept<concepts::Graph, 554 SubGraph Adaptor<concepts::Graph,552 void checkSubGraph() { 553 checkConcept<concepts::Graph, 554 SubGraph<concepts::Graph, 555 555 concepts::Graph::NodeMap<bool>, 556 556 concepts::Graph::EdgeMap<bool> > >(); … … 559 559 typedef Graph::NodeMap<bool> NodeFilter; 560 560 typedef Graph::EdgeMap<bool> EdgeFilter; 561 typedef SubGraph Adaptor<Graph, NodeFilter, EdgeFilter> Adaptor;561 typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor; 562 562 563 563 Graph graph; … … 608 608 checkGraphEdgeMap(adaptor); 609 609 610 edge_filter[e2] = false; 610 edge_filter[e2] = false; 611 611 612 612 checkGraphNodeList(adaptor, 4); … … 639 639 checkGraphEdgeMap(adaptor); 640 640 641 node_filter[n1] = false; 641 node_filter[n1] = false; 642 642 643 643 checkGraphNodeList(adaptor, 3); … … 685 685 } 686 686 687 void check NodeSubGraphAdaptor() {688 checkConcept<concepts::Graph, 689 NodeSubGraphAdaptor<concepts::Graph,687 void checkFilterNodes2() { 688 checkConcept<concepts::Graph, 689 FilterNodes<concepts::Graph, 690 690 concepts::Graph::NodeMap<bool> > >(); 691 691 692 692 typedef ListGraph Graph; 693 693 typedef Graph::NodeMap<bool> NodeFilter; 694 typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;694 typedef FilterNodes<Graph, NodeFilter> Adaptor; 695 695 696 696 Graph graph; … … 739 739 checkGraphEdgeMap(adaptor); 740 740 741 node_filter[n1] = false; 741 node_filter[n1] = false; 742 742 743 743 checkGraphNodeList(adaptor, 3); … … 784 784 } 785 785 786 void check EdgeSubGraphAdaptor() {787 checkConcept<concepts::Graph, 788 EdgeSubGraphAdaptor<concepts::Graph,786 void checkFilterEdges() { 787 checkConcept<concepts::Graph, 788 FilterEdges<concepts::Graph, 789 789 concepts::Graph::EdgeMap<bool> > >(); 790 790 791 791 typedef ListGraph Graph; 792 792 typedef Graph::EdgeMap<bool> EdgeFilter; 793 typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;793 typedef FilterEdges<Graph, EdgeFilter> Adaptor; 794 794 795 795 Graph graph; … … 838 838 checkGraphEdgeMap(adaptor); 839 839 840 edge_filter[e2] = false; 840 edge_filter[e2] = false; 841 841 842 842 checkGraphNodeList(adaptor, 4); … … 886 886 } 887 887 888 void check DirGraphAdaptor() {889 checkConcept<concepts::Digraph, 890 DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();888 void checkOrienter() { 889 checkConcept<concepts::Digraph, 890 Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >(); 891 891 892 892 typedef ListGraph Graph; 893 893 typedef ListGraph::EdgeMap<bool> DirMap; 894 typedef DirGraphAdaptor<Graph> Adaptor;894 typedef Orienter<Graph> Adaptor; 895 895 896 896 Graph graph; … … 905 905 Graph::Edge e2 = graph.addEdge(n1, n3); 906 906 Graph::Edge e3 = graph.addEdge(n2, n3); 907 907 908 908 checkGraphNodeList(adaptor, 3); 909 909 checkGraphArcList(adaptor, 3); 910 910 checkGraphConArcList(adaptor, 3); 911 911 912 912 { 913 913 dir[e1] = true; 914 914 Adaptor::Node u = adaptor.source(e1); 915 915 Adaptor::Node v = adaptor.target(e1); 916 916 917 917 dir[e1] = false; 918 918 check (u == adaptor.target(e1), "Wrong dir"); … … 927 927 Adaptor::Node u = adaptor.source(e2); 928 928 Adaptor::Node v = adaptor.target(e2); 929 929 930 930 dir[e2] = false; 931 931 check (u == adaptor.target(e2), "Wrong dir"); … … 940 940 Adaptor::Node u = adaptor.source(e3); 941 941 Adaptor::Node v = adaptor.target(e3); 942 942 943 943 dir[e3] = false; 944 944 check (u == adaptor.target(e3), "Wrong dir"); … … 968 968 int main(int, const char **) { 969 969 970 checkRev DigraphAdaptor();971 checkSubDigraph Adaptor();972 check NodeSubDigraphAdaptor();973 check ArcSubDigraphAdaptor();974 checkUndir DigraphAdaptor();975 checkRes DigraphAdaptor();976 checkSplit DigraphAdaptor();977 978 checkSubGraph Adaptor();979 check NodeSubGraphAdaptor();980 check EdgeSubGraphAdaptor();981 check DirGraphAdaptor();970 checkReverseDigraph(); 971 checkSubDigraph(); 972 checkFilterNodes1(); 973 checkFilterArcs(); 974 checkUndirector(); 975 checkResidual(); 976 checkSplitNodes(); 977 978 checkSubGraph(); 979 checkFilterNodes2(); 980 checkFilterEdges(); 981 checkOrienter(); 982 982 983 983 return 0;
Note: See TracChangeset
for help on using the changeset viewer.