lemon: test/graph_test.cc@ada5f74d1c9e

     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library.

     4  *

     5  * Copyright (C) 2003-2008

     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).

     8  *

     9  * Permission to use, modify and distribute this software is granted

    10  * provided that this copyright notice appears in all copies. For

    11  * precise terms see the accompanying LICENSE file.

    12  *

    13  * This software is provided "AS IS" with no warranty of any kind,

    14  * express or implied, and with no claim as to its suitability for any

    15  * purpose.

    16  *

    17  */

    19 #include <lemon/concepts/graph.h>

    20 #include <lemon/list_graph.h>

    21 #include <lemon/smart_graph.h>

    22 // #include <lemon/full_graph.h>

    23 #include <lemon/grid_graph.h>

    25 #include "test_tools.h"

    26 #include "graph_test.h"

    28 using namespace lemon;

    29 using namespace lemon::concepts;

    31 template <class Graph>

    32 void checkGraph() {

    33   TEMPLATE_GRAPH_TYPEDEFS(Graph);

    35   Graph G;

    36   checkGraphNodeList(G, 0);

    37   checkGraphEdgeList(G, 0);

    39   Node

    40     n1 = G.addNode(),

    41     n2 = G.addNode(),

    42     n3 = G.addNode();

    43   checkGraphNodeList(G, 3);

    44   checkGraphEdgeList(G, 0);

    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);

    53   checkGraphOutArcList(G, n1, 1);

    54   checkGraphOutArcList(G, n2, 1);

    55   checkGraphOutArcList(G, n3, 0);

    57   checkGraphInArcList(G, n1, 1);

    58   checkGraphInArcList(G, n2, 1);

    59   checkGraphInArcList(G, n3, 0);

    61   checkGraphIncEdgeList(G, n1, 1);

    62   checkGraphIncEdgeList(G, n2, 1);

    63   checkGraphIncEdgeList(G, n3, 0);

    65   checkGraphConArcList(G, 2);

    66   checkGraphConEdgeList(G, 1);

    68   Edge e2 = G.addEdge(n2, n1), e3 = G.addEdge(n2, n3);

    69   checkGraphNodeList(G, 3);

    70   checkGraphArcList(G, 6);

    71   checkGraphEdgeList(G, 3);

    73   checkGraphOutArcList(G, n1, 2);

    74   checkGraphOutArcList(G, n2, 3);

    75   checkGraphOutArcList(G, n3, 1);

    77   checkGraphInArcList(G, n1, 2);

    78   checkGraphInArcList(G, n2, 3);

    79   checkGraphInArcList(G, n3, 1);

    81   checkGraphIncEdgeList(G, n1, 2);

    82   checkGraphIncEdgeList(G, n2, 3);

    83   checkGraphIncEdgeList(G, n3, 1);

    85   checkGraphConArcList(G, 6);

    86   checkGraphConEdgeList(G, 3);

    88   checkArcDirections(G);

    90   checkNodeIds(G);

    91   checkArcIds(G);

    92   checkEdgeIds(G);

    93   checkGraphNodeMap(G);

    94   checkGraphArcMap(G);

    95   checkGraphEdgeMap(G);

    96 }

    98 void checkConcepts() {

    99   { // Checking graph components

   100     checkConcept<BaseGraphComponent, BaseGraphComponent >();

   102     checkConcept<IDableGraphComponent<>,

   103       IDableGraphComponent<> >();

   105     checkConcept<IterableGraphComponent<>,

   106       IterableGraphComponent<> >();

   108     checkConcept<MappableGraphComponent<>,

   109       MappableGraphComponent<> >();

   110   }

   111   { // Checking skeleton graph

   112     checkConcept<Graph, Graph>();

   113   }

   114   { // Checking ListGraph

   115     checkConcept<Graph, ListGraph>();

   116     checkConcept<AlterableGraphComponent<>, ListGraph>();

   117     checkConcept<ExtendableGraphComponent<>, ListGraph>();

   118     checkConcept<ClearableGraphComponent<>, ListGraph>();

   119     checkConcept<ErasableGraphComponent<>, ListGraph>();

   120   }

   121   { // Checking SmartGraph

   122     checkConcept<Graph, SmartGraph>();

   123     checkConcept<AlterableGraphComponent<>, SmartGraph>();

   124     checkConcept<ExtendableGraphComponent<>, SmartGraph>();

   125     checkConcept<ClearableGraphComponent<>, SmartGraph>();

   126   }

   127 //  { // Checking FullGraph

   128 //    checkConcept<Graph, FullGraph>();

   129 //  }

   130   { // Checking GridGraph

   131     checkConcept<Graph, GridGraph>();

   132   }

   133 }

   135 template <typename Graph>

   136 void checkGraphValidity() {

   137   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   138   Graph g;

   140   Node

   141     n1 = g.addNode(),

   142     n2 = g.addNode(),

   143     n3 = g.addNode();

   145   Edge

   146     e1 = g.addEdge(n1, n2),

   147     e2 = g.addEdge(n2, n3);

   149   check(g.valid(n1), "Wrong validity check");

   150   check(g.valid(e1), "Wrong validity check");

   151   check(g.valid(g.direct(e1, true)), "Wrong validity check");

   153   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

   154   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

   155   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

   156 }

   158 template <typename Graph>

   159 void checkGraphValidityErase() {

   160   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   161   Graph g;

   163   Node

   164     n1 = g.addNode(),

   165     n2 = g.addNode(),

   166     n3 = g.addNode();

   168   Edge

   169     e1 = g.addEdge(n1, n2),

   170     e2 = g.addEdge(n2, n3);

   172   check(g.valid(n1), "Wrong validity check");

   173   check(g.valid(e1), "Wrong validity check");

   174   check(g.valid(g.direct(e1, true)), "Wrong validity check");

   176   g.erase(n1);

   178   check(!g.valid(n1), "Wrong validity check");

   179   check(g.valid(n2), "Wrong validity check");

   180   check(g.valid(n3), "Wrong validity check");

   181   check(!g.valid(e1), "Wrong validity check");

   182   check(g.valid(e2), "Wrong validity check");

   184   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");

   185   check(!g.valid(g.edgeFromId(-1)), "Wrong validity check");

   186   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");

   187 }

   189 void checkGridGraph(const GridGraph& g, int w, int h) {

   190   check(g.width() == w, "Wrong width");

   191   check(g.height() == h, "Wrong height");

   193   for (int i = 0; i < w; ++i) {

   194     for (int j = 0; j < h; ++j) {

   195       check(g.col(g(i, j)) == i, "Wrong col");

   196       check(g.row(g(i, j)) == j, "Wrong row");

   197     }

   198   }

   200   for (int i = 0; i < w; ++i) {

   201     for (int j = 0; j < h - 1; ++j) {

   202       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");

   203       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");

   204     }

   205     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");

   206   }

   208   for (int i = 0; i < w; ++i) {

   209     for (int j = 1; j < h; ++j) {

   210       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");

   211       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");

   212     }

   213     check(g.up(g(i, 0)) == INVALID, "Wrong up");

   214   }

   216   for (int j = 0; j < h; ++j) {

   217     for (int i = 0; i < w - 1; ++i) {

   218       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");

   219       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");

   220     }

   221     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");

   222   }

   224   for (int j = 0; j < h; ++j) {

   225     for (int i = 1; i < w; ++i) {

   226       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");

   227       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");

   228     }

   229     check(g.left(g(0, j)) == INVALID, "Wrong left");

   230   }

   232   checkGraphNodeList(g, w*h);

   233   checkGraphArcList(g, 2*(2*w*h-w-h));

   234   checkGraphEdgeList(g, 2*w*h-w-h);

   236   checkGraphOutArcList(g, g(0,0), 2);

   237   checkGraphOutArcList(g, g(0,1), 3);

   238   checkGraphOutArcList(g, g(w-2,h-2), 4);

   240   checkGraphInArcList(g, g(0,0), 2);

   241   checkGraphInArcList(g, g(0,1), 3);

   242   checkGraphInArcList(g, g(w-2,h-2), 4);

   244   checkGraphIncEdgeList(g, g(0,0), 2);

   245   checkGraphIncEdgeList(g, g(0,1), 3);

   246   checkGraphIncEdgeList(g, g(w-2,h-2), 4);

   248   checkGraphConArcList(g, 2*(2*w*h-w-h));

   249   checkGraphConEdgeList(g, 2*w*h-w-h);

   251   checkArcDirections(g);

   253   checkNodeIds(g);

   254   checkArcIds(g);

   255   checkEdgeIds(g);

   256   checkGraphNodeMap(g);

   257   checkGraphArcMap(g);

   258   checkGraphEdgeMap(g);

   259 }

   261 void checkGraphs() {

   262   { // Checking ListGraph

   263     checkGraph<ListGraph>();

   264     checkGraphValidityErase<ListGraph>();

   265   }

   266   { // Checking SmartGraph

   267     checkGraph<SmartGraph>();

   268     checkGraphValidity<SmartGraph>();

   269   }

   270 //   { // Checking FullGraph

   271 //     FullGraph g(5);

   272 //     checkGraphNodeList(g, 5);

   273 //     checkGraphEdgeList(g, 10);

   274 //   }

   275   { // Checking GridGraph

   276     GridGraph g(5, 6);

   277     checkGridGraph(g, 5, 6);

   278   }

   279 }

   281 int main() {

   282   checkConcepts();

   283   checkGraphs();

   284   return 0;

   285 }

author	Peter Kovacs <kpeter@inf.elte.hu>
	Tue, 02 Sep 2008 22:32:04 +0200
changeset 346	ada5f74d1c9e
parent 228	b6732e0d38c5
child 347	160bf92c7cdc
permissions	-rw-r--r--