lemon-1.2: test/edge_set_test.cc@1b89e29c9fc7

     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 <iostream>

    20 #include <vector>

    22 #include <lemon/concepts/digraph.h>

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

    24 #include <lemon/concept_check.h>

    26 #include <lemon/list_graph.h>

    28 #include <lemon/edge_set.h>

    30 #include "graph_test.h"

    31 #include "test_tools.h"

    33 using namespace lemon;

    35 void checkSmartArcSet() {

    36   checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();

    38   typedef ListDigraph Digraph;

    39   typedef SmartArcSet<Digraph> ArcSet;

    41   Digraph digraph;

    42   Digraph::Node

    43     n1 = digraph.addNode(),

    44     n2 = digraph.addNode();

    46   Digraph::Arc ga1 = digraph.addArc(n1, n2);

    48   ArcSet arc_set(digraph);

    50   Digraph::Arc ga2 = digraph.addArc(n2, n1);

    52   checkGraphNodeList(arc_set, 2);

    53   checkGraphArcList(arc_set, 0);

    55   Digraph::Node

    56     n3 = digraph.addNode();

    57   checkGraphNodeList(arc_set, 3);

    58   checkGraphArcList(arc_set, 0);

    60   ArcSet::Arc a1 = arc_set.addArc(n1, n2);

    61   check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");

    62   checkGraphNodeList(arc_set, 3);

    63   checkGraphArcList(arc_set, 1);

    65   checkGraphOutArcList(arc_set, n1, 1);

    66   checkGraphOutArcList(arc_set, n2, 0);

    67   checkGraphOutArcList(arc_set, n3, 0);

    69   checkGraphInArcList(arc_set, n1, 0);

    70   checkGraphInArcList(arc_set, n2, 1);

    71   checkGraphInArcList(arc_set, n3, 0);

    73   checkGraphConArcList(arc_set, 1);

    75   ArcSet::Arc a2 = arc_set.addArc(n2, n1),

    76     a3 = arc_set.addArc(n2, n3),

    77     a4 = arc_set.addArc(n2, n3);

    78   checkGraphNodeList(arc_set, 3);

    79   checkGraphArcList(arc_set, 4);

    81   checkGraphOutArcList(arc_set, n1, 1);

    82   checkGraphOutArcList(arc_set, n2, 3);

    83   checkGraphOutArcList(arc_set, n3, 0);

    85   checkGraphInArcList(arc_set, n1, 1);

    86   checkGraphInArcList(arc_set, n2, 1);

    87   checkGraphInArcList(arc_set, n3, 2);

    89   checkGraphConArcList(arc_set, 4);

    91   checkNodeIds(arc_set);

    92   checkArcIds(arc_set);

    93   checkGraphNodeMap(arc_set);

    94   checkGraphArcMap(arc_set);

    96   check(arc_set.valid(), "Wrong validity");

    97   digraph.erase(n1);

    98   check(!arc_set.valid(), "Wrong validity");

    99 }

   101 void checkListArcSet() {

   102   checkConcept<concepts::Digraph, SmartArcSet<ListDigraph> >();

   104   typedef ListDigraph Digraph;

   105   typedef ListArcSet<Digraph> ArcSet;

   107   Digraph digraph;

   108   Digraph::Node

   109     n1 = digraph.addNode(),

   110     n2 = digraph.addNode();

   112   Digraph::Arc ga1 = digraph.addArc(n1, n2);

   114   ArcSet arc_set(digraph);

   116   Digraph::Arc ga2 = digraph.addArc(n2, n1);

   118   checkGraphNodeList(arc_set, 2);

   119   checkGraphArcList(arc_set, 0);

   121   Digraph::Node

   122     n3 = digraph.addNode();

   123   checkGraphNodeList(arc_set, 3);

   124   checkGraphArcList(arc_set, 0);

   126   ArcSet::Arc a1 = arc_set.addArc(n1, n2);

   127   check(arc_set.source(a1) == n1 && arc_set.target(a1) == n2, "Wrong arc");

   128   checkGraphNodeList(arc_set, 3);

   129   checkGraphArcList(arc_set, 1);

   131   checkGraphOutArcList(arc_set, n1, 1);

   132   checkGraphOutArcList(arc_set, n2, 0);

   133   checkGraphOutArcList(arc_set, n3, 0);

   135   checkGraphInArcList(arc_set, n1, 0);

   136   checkGraphInArcList(arc_set, n2, 1);

   137   checkGraphInArcList(arc_set, n3, 0);

   139   checkGraphConArcList(arc_set, 1);

   141   ArcSet::Arc a2 = arc_set.addArc(n2, n1),

   142     a3 = arc_set.addArc(n2, n3),

   143     a4 = arc_set.addArc(n2, n3);

   144   checkGraphNodeList(arc_set, 3);

   145   checkGraphArcList(arc_set, 4);

   147   checkGraphOutArcList(arc_set, n1, 1);

   148   checkGraphOutArcList(arc_set, n2, 3);

   149   checkGraphOutArcList(arc_set, n3, 0);

   151   checkGraphInArcList(arc_set, n1, 1);

   152   checkGraphInArcList(arc_set, n2, 1);

   153   checkGraphInArcList(arc_set, n3, 2);

   155   checkGraphConArcList(arc_set, 4);

   157   checkNodeIds(arc_set);

   158   checkArcIds(arc_set);

   159   checkGraphNodeMap(arc_set);

   160   checkGraphArcMap(arc_set);

   162   digraph.erase(n1);

   164   checkGraphNodeList(arc_set, 2);

   165   checkGraphArcList(arc_set, 2);

   167   checkGraphOutArcList(arc_set, n2, 2);

   168   checkGraphOutArcList(arc_set, n3, 0);

   170   checkGraphInArcList(arc_set, n2, 0);

   171   checkGraphInArcList(arc_set, n3, 2);

   173   checkNodeIds(arc_set);

   174   checkArcIds(arc_set);

   175   checkGraphNodeMap(arc_set);

   176   checkGraphArcMap(arc_set);

   178   checkGraphConArcList(arc_set, 2);

   179 }

   181 void checkSmartEdgeSet() {

   182   checkConcept<concepts::Digraph, SmartEdgeSet<ListDigraph> >();

   184   typedef ListDigraph Digraph;

   185   typedef SmartEdgeSet<Digraph> EdgeSet;

   187   Digraph digraph;

   188   Digraph::Node

   189     n1 = digraph.addNode(),

   190     n2 = digraph.addNode();

   192   Digraph::Arc ga1 = digraph.addArc(n1, n2);

   194   EdgeSet edge_set(digraph);

   196   Digraph::Arc ga2 = digraph.addArc(n2, n1);

   198   checkGraphNodeList(edge_set, 2);

   199   checkGraphArcList(edge_set, 0);

   200   checkGraphEdgeList(edge_set, 0);

   202   Digraph::Node

   203     n3 = digraph.addNode();

   204   checkGraphNodeList(edge_set, 3);

   205   checkGraphArcList(edge_set, 0);

   206   checkGraphEdgeList(edge_set, 0);

   208   EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);

   209   check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||

   210         (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");

   211   checkGraphNodeList(edge_set, 3);

   212   checkGraphArcList(edge_set, 2);

   213   checkGraphEdgeList(edge_set, 1);

   215   checkGraphOutArcList(edge_set, n1, 1);

   216   checkGraphOutArcList(edge_set, n2, 1);

   217   checkGraphOutArcList(edge_set, n3, 0);

   219   checkGraphInArcList(edge_set, n1, 1);

   220   checkGraphInArcList(edge_set, n2, 1);

   221   checkGraphInArcList(edge_set, n3, 0);

   223   checkGraphIncEdgeList(edge_set, n1, 1);

   224   checkGraphIncEdgeList(edge_set, n2, 1);

   225   checkGraphIncEdgeList(edge_set, n3, 0);

   227   checkGraphConEdgeList(edge_set, 1);

   228   checkGraphConArcList(edge_set, 2);

   230   EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),

   231     e3 = edge_set.addEdge(n2, n3),

   232     e4 = edge_set.addEdge(n2, n3);

   233   checkGraphNodeList(edge_set, 3);

   234   checkGraphEdgeList(edge_set, 4);

   236   checkGraphOutArcList(edge_set, n1, 2);

   237   checkGraphOutArcList(edge_set, n2, 4);

   238   checkGraphOutArcList(edge_set, n3, 2);

   240   checkGraphInArcList(edge_set, n1, 2);

   241   checkGraphInArcList(edge_set, n2, 4);

   242   checkGraphInArcList(edge_set, n3, 2);

   244   checkGraphIncEdgeList(edge_set, n1, 2);

   245   checkGraphIncEdgeList(edge_set, n2, 4);

   246   checkGraphIncEdgeList(edge_set, n3, 2);

   248   checkGraphConEdgeList(edge_set, 4);

   249   checkGraphConArcList(edge_set, 8);

   251   checkArcDirections(edge_set);

   253   checkNodeIds(edge_set);

   254   checkArcIds(edge_set);

   255   checkEdgeIds(edge_set);

   256   checkGraphNodeMap(edge_set);

   257   checkGraphArcMap(edge_set);

   258   checkGraphEdgeMap(edge_set);

   260   check(edge_set.valid(), "Wrong validity");

   261   digraph.erase(n1);

   262   check(!edge_set.valid(), "Wrong validity");

   263 }

   265 void checkListEdgeSet() {

   266   checkConcept<concepts::Digraph, ListEdgeSet<ListDigraph> >();

   268   typedef ListDigraph Digraph;

   269   typedef ListEdgeSet<Digraph> EdgeSet;

   271   Digraph digraph;

   272   Digraph::Node

   273     n1 = digraph.addNode(),

   274     n2 = digraph.addNode();

   276   Digraph::Arc ga1 = digraph.addArc(n1, n2);

   278   EdgeSet edge_set(digraph);

   280   Digraph::Arc ga2 = digraph.addArc(n2, n1);

   282   checkGraphNodeList(edge_set, 2);

   283   checkGraphArcList(edge_set, 0);

   284   checkGraphEdgeList(edge_set, 0);

   286   Digraph::Node

   287     n3 = digraph.addNode();

   288   checkGraphNodeList(edge_set, 3);

   289   checkGraphArcList(edge_set, 0);

   290   checkGraphEdgeList(edge_set, 0);

   292   EdgeSet::Edge e1 = edge_set.addEdge(n1, n2);

   293   check((edge_set.u(e1) == n1 && edge_set.v(e1) == n2) ||

   294         (edge_set.v(e1) == n1 && edge_set.u(e1) == n2), "Wrong edge");

   295   checkGraphNodeList(edge_set, 3);

   296   checkGraphArcList(edge_set, 2);

   297   checkGraphEdgeList(edge_set, 1);

   299   checkGraphOutArcList(edge_set, n1, 1);

   300   checkGraphOutArcList(edge_set, n2, 1);

   301   checkGraphOutArcList(edge_set, n3, 0);

   303   checkGraphInArcList(edge_set, n1, 1);

   304   checkGraphInArcList(edge_set, n2, 1);

   305   checkGraphInArcList(edge_set, n3, 0);

   307   checkGraphIncEdgeList(edge_set, n1, 1);

   308   checkGraphIncEdgeList(edge_set, n2, 1);

   309   checkGraphIncEdgeList(edge_set, n3, 0);

   311   checkGraphConEdgeList(edge_set, 1);

   312   checkGraphConArcList(edge_set, 2);

   314   EdgeSet::Edge e2 = edge_set.addEdge(n2, n1),

   315     e3 = edge_set.addEdge(n2, n3),

   316     e4 = edge_set.addEdge(n2, n3);

   317   checkGraphNodeList(edge_set, 3);

   318   checkGraphEdgeList(edge_set, 4);

   320   checkGraphOutArcList(edge_set, n1, 2);

   321   checkGraphOutArcList(edge_set, n2, 4);

   322   checkGraphOutArcList(edge_set, n3, 2);

   324   checkGraphInArcList(edge_set, n1, 2);

   325   checkGraphInArcList(edge_set, n2, 4);

   326   checkGraphInArcList(edge_set, n3, 2);

   328   checkGraphIncEdgeList(edge_set, n1, 2);

   329   checkGraphIncEdgeList(edge_set, n2, 4);

   330   checkGraphIncEdgeList(edge_set, n3, 2);

   332   checkGraphConEdgeList(edge_set, 4);

   333   checkGraphConArcList(edge_set, 8);

   335   checkArcDirections(edge_set);

   337   checkNodeIds(edge_set);

   338   checkArcIds(edge_set);

   339   checkEdgeIds(edge_set);

   340   checkGraphNodeMap(edge_set);

   341   checkGraphArcMap(edge_set);

   342   checkGraphEdgeMap(edge_set);

   344   digraph.erase(n1);

   346   checkGraphNodeList(edge_set, 2);

   347   checkGraphArcList(edge_set, 4);

   348   checkGraphEdgeList(edge_set, 2);

   350   checkGraphOutArcList(edge_set, n2, 2);

   351   checkGraphOutArcList(edge_set, n3, 2);

   353   checkGraphInArcList(edge_set, n2, 2);

   354   checkGraphInArcList(edge_set, n3, 2);

   356   checkGraphIncEdgeList(edge_set, n2, 2);

   357   checkGraphIncEdgeList(edge_set, n3, 2);

   359   checkNodeIds(edge_set);

   360   checkArcIds(edge_set);

   361   checkEdgeIds(edge_set);

   362   checkGraphNodeMap(edge_set);

   363   checkGraphArcMap(edge_set);

   364   checkGraphEdgeMap(edge_set);

   366   checkGraphConEdgeList(edge_set, 2);

   367   checkGraphConArcList(edge_set, 4);

   369 }

   372 int main() {

   374   checkSmartArcSet();

   375   checkListArcSet();

   376   checkSmartEdgeSet();

   377   checkListEdgeSet();

   379   return 0;

   380 }

author	Alpar Juttner <alpar@cs.elte.hu>
	Thu, 10 Dec 2009 17:18:25 +0100
changeset 803	1b89e29c9fc7
parent 468	68fe66e2b34a
child 877	141f9c0db4a3
child 963	761fe0846f49
permissions	-rw-r--r--