COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 1019:4c89e925cfe2 in lemon-main for test


Ignore:
Timestamp:
11/14/10 20:06:23 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

SmartBpGraph? implementation (#69)

Location:
test
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • test/bpgraph_test.cc

    r1018 r1019  
    1919#include <lemon/concepts/bpgraph.h>
    2020//#include <lemon/list_graph.h>
    21 //#include <lemon/smart_graph.h>
     21#include <lemon/smart_graph.h>
    2222//#include <lemon/full_graph.h>
    23 //#include <lemon/grid_graph.h>
    24 //#include <lemon/hypercube_graph.h>
    2523
    2624#include "test_tools.h"
    … …  
    2927using namespace lemon;
    3028using namespace lemon::concepts;
     29
     30template <class BpGraph>
     31void checkBpGraphBuild() {
     32  TEMPLATE_BPGRAPH_TYPEDEFS(BpGraph);
     33
     34  BpGraph G;
     35  checkGraphNodeList(G, 0);
     36  checkGraphRedNodeList(G, 0);
     37  checkGraphBlueNodeList(G, 0);
     38  checkGraphEdgeList(G, 0);
     39  checkGraphArcList(G, 0);
     40
     41  G.reserveNode(3);
     42  G.reserveEdge(3);
     43
     44  Node
     45    rn1 = G.addRedNode();
     46  checkGraphNodeList(G, 1);
     47  checkGraphRedNodeList(G, 1);
     48  checkGraphBlueNodeList(G, 0);
     49  checkGraphEdgeList(G, 0);
     50  checkGraphArcList(G, 0);
     51
     52  Node
     53    bn1 = G.addBlueNode(),
     54    bn2 = G.addBlueNode();
     55  checkGraphNodeList(G, 3);
     56  checkGraphRedNodeList(G, 1);
     57  checkGraphBlueNodeList(G, 2);
     58  checkGraphEdgeList(G, 0);
     59  checkGraphArcList(G, 0);
     60
     61  Edge e1 = G.addEdge(rn1, bn2);
     62  check(G.redNode(e1) == rn1 && G.blueNode(e1) == bn2, "Wrong edge");
     63  check(G.u(e1) == rn1 && G.v(e1) == bn2, "Wrong edge");
     64
     65  checkGraphNodeList(G, 3);
     66  checkGraphRedNodeList(G, 1);
     67  checkGraphBlueNodeList(G, 2);
     68  checkGraphEdgeList(G, 1);
     69  checkGraphArcList(G, 2);
     70
     71  checkGraphIncEdgeArcLists(G, rn1, 1);
     72  checkGraphIncEdgeArcLists(G, bn1, 0);
     73  checkGraphIncEdgeArcLists(G, bn2, 1);
     74
     75  checkGraphConEdgeList(G, 1);
     76  checkGraphConArcList(G, 2);
     77
     78  Edge
     79    e2 = G.addEdge(rn1, bn1),
     80    e3 = G.addEdge(rn1, bn2);
     81
     82  checkGraphNodeList(G, 3);
     83  checkGraphRedNodeList(G, 1);
     84  checkGraphBlueNodeList(G, 2);
     85  checkGraphEdgeList(G, 3);
     86  checkGraphArcList(G, 6);
     87
     88  checkGraphIncEdgeArcLists(G, rn1, 3);
     89  checkGraphIncEdgeArcLists(G, bn1, 1);
     90  checkGraphIncEdgeArcLists(G, bn2, 2);
     91
     92  checkGraphConEdgeList(G, 3);
     93  checkGraphConArcList(G, 6);
     94
     95  checkArcDirections(G);
     96
     97  checkNodeIds(G);
     98  checkRedNodeIds(G);
     99  checkBlueNodeIds(G);
     100  checkArcIds(G);
     101  checkEdgeIds(G);
     102
     103  checkGraphNodeMap(G);
     104  checkGraphRedMap(G);
     105  checkGraphBlueMap(G);
     106  checkGraphArcMap(G);
     107  checkGraphEdgeMap(G);
     108}
     109
     110template <class Graph>
     111void checkBpGraphSnapshot() {
     112  TEMPLATE_BPGRAPH_TYPEDEFS(Graph);
     113
     114  Graph G;
     115  Node
     116    n1 = G.addRedNode(),
     117    n2 = G.addBlueNode(),
     118    n3 = G.addBlueNode();
     119  Edge
     120    e1 = G.addEdge(n1, n2),
     121    e2 = G.addEdge(n1, n3);
     122
     123  checkGraphNodeList(G, 3);
     124  checkGraphRedNodeList(G, 1);
     125  checkGraphBlueNodeList(G, 2);
     126  checkGraphEdgeList(G, 2);
     127  checkGraphArcList(G, 4);
     128
     129  typename Graph::Snapshot snapshot(G);
     130
     131  Node n4 = G.addRedNode();
     132  G.addEdge(n4, n2);
     133  G.addEdge(n4, n3);
     134
     135  checkGraphNodeList(G, 4);
     136  checkGraphRedNodeList(G, 2);
     137  checkGraphBlueNodeList(G, 2);
     138  checkGraphEdgeList(G, 4);
     139  checkGraphArcList(G, 8);
     140
     141  snapshot.restore();
     142
     143  checkGraphNodeList(G, 3);
     144  checkGraphRedNodeList(G, 1);
     145  checkGraphBlueNodeList(G, 2);
     146  checkGraphEdgeList(G, 2);
     147  checkGraphArcList(G, 4);
     148
     149  checkGraphIncEdgeArcLists(G, n1, 2);
     150  checkGraphIncEdgeArcLists(G, n2, 1);
     151  checkGraphIncEdgeArcLists(G, n3, 1);
     152
     153  checkGraphConEdgeList(G, 2);
     154  checkGraphConArcList(G, 4);
     155
     156  checkNodeIds(G);
     157  checkRedNodeIds(G);
     158  checkBlueNodeIds(G);
     159  checkArcIds(G);
     160  checkEdgeIds(G);
     161
     162  checkGraphNodeMap(G);
     163  checkGraphRedMap(G);
     164  checkGraphBlueMap(G);
     165  checkGraphArcMap(G);
     166  checkGraphEdgeMap(G);
     167
     168  G.addRedNode();
     169  snapshot.save(G);
     170
     171  G.addEdge(G.addRedNode(), G.addBlueNode());
     172
     173  snapshot.restore();
     174  snapshot.save(G);
     175
     176  checkGraphNodeList(G, 4);
     177  checkGraphRedNodeList(G, 2);
     178  checkGraphBlueNodeList(G, 2);
     179  checkGraphEdgeList(G, 2);
     180  checkGraphArcList(G, 4);
     181
     182  G.addEdge(G.addRedNode(), G.addBlueNode());
     183
     184  snapshot.restore();
     185
     186  checkGraphNodeList(G, 4);
     187  checkGraphRedNodeList(G, 2);
     188  checkGraphBlueNodeList(G, 2);
     189  checkGraphEdgeList(G, 2);
     190  checkGraphArcList(G, 4);
     191}
     192
     193template <typename Graph>
     194void checkBpGraphValidity() {
     195  TEMPLATE_GRAPH_TYPEDEFS(Graph);
     196  Graph g;
     197
     198  Node
     199    n1 = g.addRedNode(),
     200    n2 = g.addBlueNode(),
     201    n3 = g.addBlueNode();
     202
     203  Edge
     204    e1 = g.addEdge(n1, n2),
     205    e2 = g.addEdge(n1, n3);
     206
     207  check(g.valid(n1), "Wrong validity check");
     208  check(g.valid(e1), "Wrong validity check");
     209  check(g.valid(g.direct(e1, true)), "Wrong validity check");
     210
     211  check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
     212  check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");
     213  check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
     214}
    31215
    32216void checkConcepts() {
    … …  
    52236      ErasableBpGraphComponent<> >();
    53237
    54     checkConcept<ClearableGraphComponent<>,
    55       ClearableGraphComponent<> >();
     238    checkConcept<ClearableBpGraphComponent<>,
     239      ClearableBpGraphComponent<> >();
    56240
    57241  }
    … …  
    59243    checkConcept<BpGraph, BpGraph>();
    60244  }
     245  { // Checking SmartBpGraph
     246    checkConcept<BpGraph, SmartBpGraph>();
     247    checkConcept<AlterableBpGraphComponent<>, SmartBpGraph>();
     248    checkConcept<ExtendableBpGraphComponent<>, SmartBpGraph>();
     249    checkConcept<ClearableBpGraphComponent<>, SmartBpGraph>();
     250  }
    61251}
    62252
    63253void checkGraphs() {
     254  { // Checking SmartGraph
     255    checkBpGraphBuild<SmartBpGraph>();
     256    checkBpGraphSnapshot<SmartBpGraph>();
     257    checkBpGraphValidity<SmartBpGraph>();
     258  }
    64259}
    65260

  • test/graph_test.h

    r440 r1019  
    4242
    4343  template<class Graph>
     44  void checkGraphRedNodeList(const Graph &G, int cnt)
     45  {
     46    typename Graph::RedIt n(G);
     47    for(int i=0;i<cnt;i++) {
     48      check(n!=INVALID,"Wrong red Node list linking.");
     49      ++n;
     50    }
     51    check(n==INVALID,"Wrong red Node list linking.");
     52    check(countRedNodes(G)==cnt,"Wrong red Node number.");
     53  }
     54
     55  template<class Graph>
     56  void checkGraphBlueNodeList(const Graph &G, int cnt)
     57  {
     58    typename Graph::BlueIt n(G);
     59    for(int i=0;i<cnt;i++) {
     60      check(n!=INVALID,"Wrong blue Node list linking.");
     61      ++n;
     62    }
     63    check(n==INVALID,"Wrong blue Node list linking.");
     64    check(countBlueNodes(G)==cnt,"Wrong blue Node number.");
     65  }
     66
     67  template<class Graph>
    4468  void checkGraphArcList(const Graph &G, int cnt)
    4569  {
    … …  
    167191  template <typename Graph>
    168192  void checkNodeIds(const Graph& G) {
     193    typedef typename Graph::Node Node;
    169194    std::set<int> values;
    170195    for (typename Graph::NodeIt n(G); n != INVALID; ++n) {
    … …  
    174199      values.insert(G.id(n));
    175200    }
     201    check(G.maxId(Node()) <= G.maxNodeId(), "Wrong maximum id");
     202  }
     203
     204  template <typename Graph>
     205  void checkRedNodeIds(const Graph& G) {
     206    typedef typename Graph::RedNode RedNode;
     207    std::set<int> values;
     208    for (typename Graph::RedIt n(G); n != INVALID; ++n) {
     209      check(G.red(n), "Wrong partition");
     210      check(G.redId(n) == G.id(RedNode(n)), "Wrong id");
     211      check(values.find(G.redId(n)) == values.end(), "Wrong id");
     212      check(G.redId(n) <= G.maxRedId(), "Wrong maximum id");
     213      values.insert(G.id(n));
     214    }
     215    check(G.maxId(RedNode()) == G.maxRedId(), "Wrong maximum id");
     216  }
     217
     218  template <typename Graph>
     219  void checkBlueNodeIds(const Graph& G) {
     220    typedef typename Graph::BlueNode BlueNode;
     221    std::set<int> values;
     222    for (typename Graph::BlueIt n(G); n != INVALID; ++n) {
     223      check(G.blue(n), "Wrong partition");
     224      check(G.blueId(n) == G.id(BlueNode(n)), "Wrong id");
     225      check(values.find(G.blueId(n)) == values.end(), "Wrong id");
     226      check(G.blueId(n) <= G.maxBlueId(), "Wrong maximum id");
     227      values.insert(G.id(n));
     228    }
     229    check(G.maxId(BlueNode()) == G.maxBlueId(), "Wrong maximum id");
    176230  }
    177231
    178232  template <typename Graph>
    179233  void checkArcIds(const Graph& G) {
     234    typedef typename Graph::Arc Arc;
    180235    std::set<int> values;
    181236    for (typename Graph::ArcIt a(G); a != INVALID; ++a) {
    … …  
    185240      values.insert(G.id(a));
    186241    }
     242    check(G.maxId(Arc()) <= G.maxArcId(), "Wrong maximum id");
    187243  }
    188244
    189245  template <typename Graph>
    190246  void checkEdgeIds(const Graph& G) {
     247    typedef typename Graph::Edge Edge;
    191248    std::set<int> values;
    192249    for (typename Graph::EdgeIt e(G); e != INVALID; ++e) {
    … …  
    196253      values.insert(G.id(e));
    197254    }
     255    check(G.maxId(Edge()) <= G.maxEdgeId(), "Wrong maximum id");
    198256  }
    199257
    … …  
    229287
    230288  template <typename Graph>
     289  void checkGraphRedMap(const Graph& G) {
     290    typedef typename Graph::Node Node;
     291    typedef typename Graph::RedIt RedIt;
     292
     293    typedef typename Graph::template RedMap<int> IntRedMap;
     294    IntRedMap map(G, 42);
     295    for (RedIt it(G); it != INVALID; ++it) {
     296      check(map[it] == 42, "Wrong map constructor.");
     297    }
     298    int s = 0;
     299    for (RedIt it(G); it != INVALID; ++it) {
     300      map[it] = 0;
     301      check(map[it] == 0, "Wrong operator[].");
     302      map.set(it, s);
     303      check(map[it] == s, "Wrong set.");
     304      ++s;
     305    }
     306    s = s * (s - 1) / 2;
     307    for (RedIt it(G); it != INVALID; ++it) {
     308      s -= map[it];
     309    }
     310    check(s == 0, "Wrong sum.");
     311
     312    // map = constMap<Node>(12);
     313    // for (NodeIt it(G); it != INVALID; ++it) {
     314    //   check(map[it] == 12, "Wrong operator[].");
     315    // }
     316  }
     317
     318  template <typename Graph>
     319  void checkGraphBlueMap(const Graph& G) {
     320    typedef typename Graph::Node Node;
     321    typedef typename Graph::BlueIt BlueIt;
     322
     323    typedef typename Graph::template BlueMap<int> IntBlueMap;
     324    IntBlueMap map(G, 42);
     325    for (BlueIt it(G); it != INVALID; ++it) {
     326      check(map[it] == 42, "Wrong map constructor.");
     327    }
     328    int s = 0;
     329    for (BlueIt it(G); it != INVALID; ++it) {
     330      map[it] = 0;
     331      check(map[it] == 0, "Wrong operator[].");
     332      map.set(it, s);
     333      check(map[it] == s, "Wrong set.");
     334      ++s;
     335    }
     336    s = s * (s - 1) / 2;
     337    for (BlueIt it(G); it != INVALID; ++it) {
     338      s -= map[it];
     339    }
     340    check(s == 0, "Wrong sum.");
     341
     342    // map = constMap<Node>(12);
     343    // for (NodeIt it(G); it != INVALID; ++it) {
     344    //   check(map[it] == 12, "Wrong operator[].");
     345    // }
     346  }
     347
     348  template <typename Graph>
    231349  void checkGraphArcMap(const Graph& G) {
    232350    typedef typename Graph::Arc Arc;
Note: See TracChangeset for help on using the changeset viewer.