COIN-OR::LEMON - Graph Library

Changeset 416:76287c8caa26 in lemon-1.2 for test


Ignore:
Timestamp:
11/30/08 19:18:32 (11 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

Reorganication of graph adaptors and doc improvements (#67)

  • Moving to one file, lemon/adaptors.h
  • Renamings
  • Doc cleanings
File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/graph_adaptor_test.cc

    r415 r416  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    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.
    44 *
    55 * Copyright (C) 2003-2008
     
    2626#include<lemon/concepts/graph.h>
    2727
    28 #include<lemon/digraph_adaptor.h>
    29 #include<lemon/graph_adaptor.h>
     28#include<lemon/adaptors.h>
    3029
    3130#include <limits>
     
    3837using namespace lemon;
    3938
    40 void checkRevDigraphAdaptor() {
    41   checkConcept<concepts::Digraph, RevDigraphAdaptor<concepts::Digraph> >();
     39void checkReverseDigraph() {
     40  checkConcept<concepts::Digraph, ReverseDigraph<concepts::Digraph> >();
    4241
    4342  typedef ListDigraph Digraph;
    44   typedef RevDigraphAdaptor<Digraph> Adaptor;
     43  typedef ReverseDigraph<Digraph> Adaptor;
    4544
    4645  Digraph digraph;
     
    5453  Digraph::Arc a2 = digraph.addArc(n1, n3);
    5554  Digraph::Arc a3 = digraph.addArc(n2, n3);
    56  
     55
    5756  checkGraphNodeList(adaptor, 3);
    5857  checkGraphArcList(adaptor, 3);
     
    7978}
    8079
    81 void checkSubDigraphAdaptor() {
    82   checkConcept<concepts::Digraph, 
    83     SubDigraphAdaptor<concepts::Digraph,
     80void checkSubDigraph() {
     81  checkConcept<concepts::Digraph,
     82    SubDigraph<concepts::Digraph,
    8483    concepts::Digraph::NodeMap<bool>,
    8584    concepts::Digraph::ArcMap<bool> > >();
     
    8887  typedef Digraph::NodeMap<bool> NodeFilter;
    8988  typedef Digraph::ArcMap<bool> ArcFilter;
    90   typedef SubDigraphAdaptor<Digraph, NodeFilter, ArcFilter> Adaptor;
     89  typedef SubDigraph<Digraph, NodeFilter, ArcFilter> Adaptor;
    9190
    9291  Digraph digraph;
     
    124123  checkGraphArcMap(adaptor);
    125124
    126   arc_filter[a2] = false; 
     125  arc_filter[a2] = false;
    127126
    128127  checkGraphNodeList(adaptor, 3);
     
    144143  checkGraphArcMap(adaptor);
    145144
    146   node_filter[n1] = false; 
     145  node_filter[n1] = false;
    147146
    148147  checkGraphNodeList(adaptor, 2);
     
    176175}
    177176
    178 void checkNodeSubDigraphAdaptor() {
    179   checkConcept<concepts::Digraph, 
    180     NodeSubDigraphAdaptor<concepts::Digraph,
     177void checkFilterNodes1() {
     178  checkConcept<concepts::Digraph,
     179    FilterNodes<concepts::Digraph,
    181180      concepts::Digraph::NodeMap<bool> > >();
    182181
    183182  typedef ListDigraph Digraph;
    184183  typedef Digraph::NodeMap<bool> NodeFilter;
    185   typedef NodeSubDigraphAdaptor<Digraph, NodeFilter> Adaptor;
     184  typedef FilterNodes<Digraph, NodeFilter> Adaptor;
    186185
    187186  Digraph digraph;
     
    217216  checkGraphArcMap(adaptor);
    218217
    219   node_filter[n1] = false; 
     218  node_filter[n1] = false;
    220219
    221220  checkGraphNodeList(adaptor, 2);
     
    248247}
    249248
    250 void checkArcSubDigraphAdaptor() {
    251   checkConcept<concepts::Digraph, 
    252     ArcSubDigraphAdaptor<concepts::Digraph,
     249void checkFilterArcs() {
     250  checkConcept<concepts::Digraph,
     251    FilterArcs<concepts::Digraph,
    253252    concepts::Digraph::ArcMap<bool> > >();
    254253
    255254  typedef ListDigraph Digraph;
    256255  typedef Digraph::ArcMap<bool> ArcFilter;
    257   typedef ArcSubDigraphAdaptor<Digraph, ArcFilter> Adaptor;
     256  typedef FilterArcs<Digraph, ArcFilter> Adaptor;
    258257
    259258  Digraph digraph;
     
    289288  checkGraphArcMap(adaptor);
    290289
    291   arc_filter[a2] = false; 
     290  arc_filter[a2] = false;
    292291
    293292  checkGraphNodeList(adaptor, 3);
     
    322321}
    323322
    324 void checkUndirDigraphAdaptor() {
    325   checkConcept<concepts::Graph, UndirDigraphAdaptor<concepts::Digraph> >();
     323void checkUndirector() {
     324  checkConcept<concepts::Graph, Undirector<concepts::Digraph> >();
    326325
    327326  typedef ListDigraph Digraph;
    328   typedef UndirDigraphAdaptor<Digraph> Adaptor;
     327  typedef Undirector<Digraph> Adaptor;
    329328
    330329  Digraph digraph;
     
    338337  Digraph::Arc a2 = digraph.addArc(n1, n3);
    339338  Digraph::Arc a3 = digraph.addArc(n2, n3);
    340  
     339
    341340  checkGraphNodeList(adaptor, 3);
    342341  checkGraphArcList(adaptor, 6);
     
    372371}
    373372
    374 void checkResDigraphAdaptor() {
    375   checkConcept<concepts::Digraph, 
    376     ResDigraphAdaptor<concepts::Digraph,
    377     concepts::Digraph::ArcMap<int>, 
     373void checkResidual() {
     374  checkConcept<concepts::Digraph,
     375    Residual<concepts::Digraph,
     376    concepts::Digraph::ArcMap<int>,
    378377    concepts::Digraph::ArcMap<int> > >();
    379378
    380379  typedef ListDigraph Digraph;
    381380  typedef Digraph::ArcMap<int> IntArcMap;
    382   typedef ResDigraphAdaptor<Digraph, IntArcMap> Adaptor;
     381  typedef Residual<Digraph, IntArcMap> Adaptor;
    383382
    384383  Digraph digraph;
     
    408407    flow[a] = 0;
    409408  }
    410  
     409
    411410  checkGraphNodeList(adaptor, 4);
    412411  checkGraphArcList(adaptor, 6);
     
    426425    flow[a] = capacity[a] / 2;
    427426  }
    428  
     427
    429428  checkGraphNodeList(adaptor, 4);
    430429  checkGraphArcList(adaptor, 12);
     
    450449    flow[a] = capacity[a];
    451450  }
    452  
     451
    453452  checkGraphNodeList(adaptor, 4);
    454453  checkGraphArcList(adaptor, 6);
     
    471470  int flow_value = 0;
    472471  while (true) {
    473    
     472
    474473    Bfs<Adaptor> bfs(adaptor);
    475474    bfs.run(n1, n4);
    476    
     475
    477476    if (!bfs.reached(n4)) break;
    478477
    479478    Path<Adaptor> p = bfs.path(n4);
    480    
     479
    481480    int min = std::numeric_limits<int>::max();
    482481    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);
    484484    }
    485485
     
    494494}
    495495
    496 void checkSplitDigraphAdaptor() {
    497   checkConcept<concepts::Digraph, SplitDigraphAdaptor<concepts::Digraph> >();
     496void checkSplitNodes() {
     497  checkConcept<concepts::Digraph, SplitNodes<concepts::Digraph> >();
    498498
    499499  typedef ListDigraph Digraph;
    500   typedef SplitDigraphAdaptor<Digraph> Adaptor;
     500  typedef SplitNodes<Digraph> Adaptor;
    501501
    502502  Digraph digraph;
     
    510510  Digraph::Arc a2 = digraph.addArc(n1, n3);
    511511  Digraph::Arc a3 = digraph.addArc(n2, n3);
    512  
     512
    513513  checkGraphNodeList(adaptor, 6);
    514514  checkGraphArcList(adaptor, 6);
     
    531531  checkNodeIds(adaptor);
    532532  checkArcIds(adaptor);
    533  
     533
    534534  checkGraphNodeMap(adaptor);
    535535  checkGraphArcMap(adaptor);
     
    538538    if (adaptor.origArc(a)) {
    539539      Digraph::Arc oa = a;
    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");
     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");
    544544    } else {
    545545      Digraph::Node on = a;
     
    550550}
    551551
    552 void checkSubGraphAdaptor() {
    553   checkConcept<concepts::Graph, 
    554     SubGraphAdaptor<concepts::Graph,
     552void checkSubGraph() {
     553  checkConcept<concepts::Graph,
     554    SubGraph<concepts::Graph,
    555555    concepts::Graph::NodeMap<bool>,
    556556    concepts::Graph::EdgeMap<bool> > >();
     
    559559  typedef Graph::NodeMap<bool> NodeFilter;
    560560  typedef Graph::EdgeMap<bool> EdgeFilter;
    561   typedef SubGraphAdaptor<Graph, NodeFilter, EdgeFilter> Adaptor;
     561  typedef SubGraph<Graph, NodeFilter, EdgeFilter> Adaptor;
    562562
    563563  Graph graph;
     
    608608  checkGraphEdgeMap(adaptor);
    609609
    610   edge_filter[e2] = false; 
     610  edge_filter[e2] = false;
    611611
    612612  checkGraphNodeList(adaptor, 4);
     
    639639  checkGraphEdgeMap(adaptor);
    640640
    641   node_filter[n1] = false; 
     641  node_filter[n1] = false;
    642642
    643643  checkGraphNodeList(adaptor, 3);
     
    685685}
    686686
    687 void checkNodeSubGraphAdaptor() {
    688   checkConcept<concepts::Graph, 
    689     NodeSubGraphAdaptor<concepts::Graph,
     687void checkFilterNodes2() {
     688  checkConcept<concepts::Graph,
     689    FilterNodes<concepts::Graph,
    690690      concepts::Graph::NodeMap<bool> > >();
    691691
    692692  typedef ListGraph Graph;
    693693  typedef Graph::NodeMap<bool> NodeFilter;
    694   typedef NodeSubGraphAdaptor<Graph, NodeFilter> Adaptor;
     694  typedef FilterNodes<Graph, NodeFilter> Adaptor;
    695695
    696696  Graph graph;
     
    739739  checkGraphEdgeMap(adaptor);
    740740
    741   node_filter[n1] = false; 
     741  node_filter[n1] = false;
    742742
    743743  checkGraphNodeList(adaptor, 3);
     
    784784}
    785785
    786 void checkEdgeSubGraphAdaptor() {
    787   checkConcept<concepts::Graph, 
    788     EdgeSubGraphAdaptor<concepts::Graph,
     786void checkFilterEdges() {
     787  checkConcept<concepts::Graph,
     788    FilterEdges<concepts::Graph,
    789789    concepts::Graph::EdgeMap<bool> > >();
    790790
    791791  typedef ListGraph Graph;
    792792  typedef Graph::EdgeMap<bool> EdgeFilter;
    793   typedef EdgeSubGraphAdaptor<Graph, EdgeFilter> Adaptor;
     793  typedef FilterEdges<Graph, EdgeFilter> Adaptor;
    794794
    795795  Graph graph;
     
    838838  checkGraphEdgeMap(adaptor);
    839839
    840   edge_filter[e2] = false; 
     840  edge_filter[e2] = false;
    841841
    842842  checkGraphNodeList(adaptor, 4);
     
    886886}
    887887
    888 void checkDirGraphAdaptor() {
    889   checkConcept<concepts::Digraph, 
    890     DirGraphAdaptor<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
     888void checkOrienter() {
     889  checkConcept<concepts::Digraph,
     890    Orienter<concepts::Graph, concepts::Graph::EdgeMap<bool> > >();
    891891
    892892  typedef ListGraph Graph;
    893893  typedef ListGraph::EdgeMap<bool> DirMap;
    894   typedef DirGraphAdaptor<Graph> Adaptor;
     894  typedef Orienter<Graph> Adaptor;
    895895
    896896  Graph graph;
     
    905905  Graph::Edge e2 = graph.addEdge(n1, n3);
    906906  Graph::Edge e3 = graph.addEdge(n2, n3);
    907  
     907
    908908  checkGraphNodeList(adaptor, 3);
    909909  checkGraphArcList(adaptor, 3);
    910910  checkGraphConArcList(adaptor, 3);
    911  
     911
    912912  {
    913913    dir[e1] = true;
    914914    Adaptor::Node u = adaptor.source(e1);
    915915    Adaptor::Node v = adaptor.target(e1);
    916    
     916
    917917    dir[e1] = false;
    918918    check (u == adaptor.target(e1), "Wrong dir");
     
    927927    Adaptor::Node u = adaptor.source(e2);
    928928    Adaptor::Node v = adaptor.target(e2);
    929    
     929
    930930    dir[e2] = false;
    931931    check (u == adaptor.target(e2), "Wrong dir");
     
    940940    Adaptor::Node u = adaptor.source(e3);
    941941    Adaptor::Node v = adaptor.target(e3);
    942    
     942
    943943    dir[e3] = false;
    944944    check (u == adaptor.target(e3), "Wrong dir");
     
    968968int main(int, const char **) {
    969969
    970   checkRevDigraphAdaptor();
    971   checkSubDigraphAdaptor();
    972   checkNodeSubDigraphAdaptor();
    973   checkArcSubDigraphAdaptor();
    974   checkUndirDigraphAdaptor();
    975   checkResDigraphAdaptor();
    976   checkSplitDigraphAdaptor();
    977 
    978   checkSubGraphAdaptor();
    979   checkNodeSubGraphAdaptor();
    980   checkEdgeSubGraphAdaptor();
    981   checkDirGraphAdaptor();
     970  checkReverseDigraph();
     971  checkSubDigraph();
     972  checkFilterNodes1();
     973  checkFilterArcs();
     974  checkUndirector();
     975  checkResidual();
     976  checkSplitNodes();
     977
     978  checkSubGraph();
     979  checkFilterNodes2();
     980  checkFilterEdges();
     981  checkOrienter();
    982982
    983983  return 0;
Note: See TracChangeset for help on using the changeset viewer.