lemon-1.1: test/graph_test.cc@560e4b6d020d

     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 //    checkGraphIterators<FullGraph>();

   130 //  }

   131   { // Checking GridGraph

   132     checkConcept<Graph, GridGraph>();

   133   }

   134 }

   136 template <typename Graph>

   137 void checkGraphValidity() {

   138   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   139   Graph g;

   141   Node

   142     n1 = g.addNode(),

   143     n2 = g.addNode(),

   144     n3 = g.addNode();

   146   Edge

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

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

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

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

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

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

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

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

   157 }

   159 template <typename Graph>

   160 void checkGraphValidityErase() {

   161   TEMPLATE_GRAPH_TYPEDEFS(Graph);

   162   Graph g;

   164   Node

   165     n1 = g.addNode(),

   166     n2 = g.addNode(),

   167     n3 = g.addNode();

   169   Edge

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

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

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

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

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

   177   g.erase(n1);

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

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

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

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

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

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

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

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

   188 }

   190 void checkGridGraph(int width, int height) {

   191   typedef GridGraph Graph;

   192   GRAPH_TYPEDEFS(Graph);

   193   Graph G(width, height);

   195   check(G.width() == width, "Wrong column number");

   196   check(G.height() == height, "Wrong row number");

   198   for (int i = 0; i < width; ++i) {

   199     for (int j = 0; j < height; ++j) {

   200       check(G.col(G(i, j)) == i, "Wrong column");

   201       check(G.row(G(i, j)) == j, "Wrong row");

   202       check(G.pos(G(i, j)).x == i, "Wrong column");

   203       check(G.pos(G(i, j)).y == j, "Wrong row");

   204     }

   205   }

   207   for (int j = 0; j < height; ++j) {

   208     for (int i = 0; i < width - 1; ++i) {

   209       check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");

   210       check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");

   211     }

   212     check(G.right(G(width - 1, j)) == INVALID, "Wrong right");

   213   }

   215   for (int j = 0; j < height; ++j) {

   216     for (int i = 1; i < width; ++i) {

   217       check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");

   218       check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");

   219     }

   220     check(G.left(G(0, j)) == INVALID, "Wrong left");

   221   }

   223   for (int i = 0; i < width; ++i) {

   224     for (int j = 0; j < height - 1; ++j) {

   225       check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");

   226       check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");

   227     }

   228     check(G.up(G(i, height - 1)) == INVALID, "Wrong up");

   229   }

   231   for (int i = 0; i < width; ++i) {

   232     for (int j = 1; j < height; ++j) {

   233       check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");

   234       check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");

   235     }

   236     check(G.down(G(i, 0)) == INVALID, "Wrong down");

   237   }

   239   checkGraphNodeList(G, width * height);

   240   checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);

   241   checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));

   243   for (NodeIt n(G); n != INVALID; ++n) {

   244     int nb = 4;

   245     if (G.col(n) == 0) --nb;

   246     if (G.col(n) == width - 1) --nb;

   247     if (G.row(n) == 0) --nb;

   248     if (G.row(n) == height - 1) --nb;

   250     checkGraphOutArcList(G, n, nb);

   251     checkGraphInArcList(G, n, nb);

   252     checkGraphIncEdgeList(G, n, nb);

   253   }

   255   checkArcDirections(G);

   257   checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));

   258   checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);

   260   checkNodeIds(G);

   261   checkArcIds(G);

   262   checkEdgeIds(G);

   263   checkGraphNodeMap(G);

   264   checkGraphArcMap(G);

   265   checkGraphEdgeMap(G);

   267 }

   269 void checkGraphs() {

   270   { // Checking ListGraph

   271     checkGraph<ListGraph>();

   272     checkGraphValidityErase<ListGraph>();

   273   }

   274   { // Checking SmartGraph

   275     checkGraph<SmartGraph>();

   276     checkGraphValidity<SmartGraph>();

   277   }

   278 //   { // Checking FullGraph

   279 //     FullGraph g(5);

   280 //     checkGraphNodeList(g, 5);

   281 //     checkGraphEdgeList(g, 10);

   282 //   }

   283   { // Checking GridGraph

   284     checkGridGraph(5, 8);

   285     checkGridGraph(8, 5);

   286     checkGridGraph(5, 5);

   287     checkGridGraph(0, 0);

   288     checkGridGraph(1, 1);

   289   }

   290 }

   292 int main() {

   293   checkConcepts();

   294   checkGraphs();

   295   return 0;

   296 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Wed, 22 Oct 2008 22:14:00 +0100
changeset 337	560e4b6d020d
parent 335	160bf92c7cdc
child 356	99f1bdf8f7db
permissions	-rw-r--r--