lemon-main: test/edge_set_test.cc@c6aa2cc1af04

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

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

    47   ::lemon::ignore_unused_variable_warning(ga1);

    49   ArcSet arc_set(digraph);

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

    52   ::lemon::ignore_unused_variable_warning(ga2);

    54   checkGraphNodeList(arc_set, 2);

    55   checkGraphArcList(arc_set, 0);

    57   Digraph::Node

    58     n3 = digraph.addNode();

    59   checkGraphNodeList(arc_set, 3);

    60   checkGraphArcList(arc_set, 0);

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

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

    64   checkGraphNodeList(arc_set, 3);

    65   checkGraphArcList(arc_set, 1);

    67   checkGraphOutArcList(arc_set, n1, 1);

    68   checkGraphOutArcList(arc_set, n2, 0);

    69   checkGraphOutArcList(arc_set, n3, 0);

    71   checkGraphInArcList(arc_set, n1, 0);

    72   checkGraphInArcList(arc_set, n2, 1);

    73   checkGraphInArcList(arc_set, n3, 0);

    75   checkGraphConArcList(arc_set, 1);

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

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

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

    80   ::lemon::ignore_unused_variable_warning(a2,a3,a4);

    82   checkGraphNodeList(arc_set, 3);

    83   checkGraphArcList(arc_set, 4);

    85   checkGraphOutArcList(arc_set, n1, 1);

    86   checkGraphOutArcList(arc_set, n2, 3);

    87   checkGraphOutArcList(arc_set, n3, 0);

    89   checkGraphInArcList(arc_set, n1, 1);

    90   checkGraphInArcList(arc_set, n2, 1);

    91   checkGraphInArcList(arc_set, n3, 2);

    93   checkGraphConArcList(arc_set, 4);

    95   checkNodeIds(arc_set);

    96   checkArcIds(arc_set);

    97   checkGraphNodeMap(arc_set);

    98   checkGraphArcMap(arc_set);

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

   101   digraph.erase(n1);

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

   103 }

   105 void checkListArcSet() {

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

   108   typedef ListDigraph Digraph;

   109   typedef ListArcSet<Digraph> ArcSet;

   111   Digraph digraph;

   112   Digraph::Node

   113     n1 = digraph.addNode(),

   114     n2 = digraph.addNode();

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

   117   ::lemon::ignore_unused_variable_warning(ga1);

   119   ArcSet arc_set(digraph);

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

   122   ::lemon::ignore_unused_variable_warning(ga2);

   124   checkGraphNodeList(arc_set, 2);

   125   checkGraphArcList(arc_set, 0);

   127   Digraph::Node

   128     n3 = digraph.addNode();

   129   checkGraphNodeList(arc_set, 3);

   130   checkGraphArcList(arc_set, 0);

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

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

   134   checkGraphNodeList(arc_set, 3);

   135   checkGraphArcList(arc_set, 1);

   137   checkGraphOutArcList(arc_set, n1, 1);

   138   checkGraphOutArcList(arc_set, n2, 0);

   139   checkGraphOutArcList(arc_set, n3, 0);

   141   checkGraphInArcList(arc_set, n1, 0);

   142   checkGraphInArcList(arc_set, n2, 1);

   143   checkGraphInArcList(arc_set, n3, 0);

   145   checkGraphConArcList(arc_set, 1);

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

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

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

   150   ::lemon::ignore_unused_variable_warning(a2,a3,a4);

   152   checkGraphNodeList(arc_set, 3);

   153   checkGraphArcList(arc_set, 4);

   155   checkGraphOutArcList(arc_set, n1, 1);

   156   checkGraphOutArcList(arc_set, n2, 3);

   157   checkGraphOutArcList(arc_set, n3, 0);

   159   checkGraphInArcList(arc_set, n1, 1);

   160   checkGraphInArcList(arc_set, n2, 1);

   161   checkGraphInArcList(arc_set, n3, 2);

   163   checkGraphConArcList(arc_set, 4);

   165   checkNodeIds(arc_set);

   166   checkArcIds(arc_set);

   167   checkGraphNodeMap(arc_set);

   168   checkGraphArcMap(arc_set);

   170   digraph.erase(n1);

   172   checkGraphNodeList(arc_set, 2);

   173   checkGraphArcList(arc_set, 2);

   175   checkGraphOutArcList(arc_set, n2, 2);

   176   checkGraphOutArcList(arc_set, n3, 0);

   178   checkGraphInArcList(arc_set, n2, 0);

   179   checkGraphInArcList(arc_set, n3, 2);

   181   checkNodeIds(arc_set);

   182   checkArcIds(arc_set);

   183   checkGraphNodeMap(arc_set);

   184   checkGraphArcMap(arc_set);

   186   checkGraphConArcList(arc_set, 2);

   187 }

   189 void checkSmartEdgeSet() {

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

   192   typedef ListDigraph Digraph;

   193   typedef SmartEdgeSet<Digraph> EdgeSet;

   195   Digraph digraph;

   196   Digraph::Node

   197     n1 = digraph.addNode(),

   198     n2 = digraph.addNode();

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

   201   ::lemon::ignore_unused_variable_warning(ga1);

   203   EdgeSet edge_set(digraph);

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

   206   ::lemon::ignore_unused_variable_warning(ga2);

   208   checkGraphNodeList(edge_set, 2);

   209   checkGraphArcList(edge_set, 0);

   210   checkGraphEdgeList(edge_set, 0);

   212   Digraph::Node

   213     n3 = digraph.addNode();

   214   checkGraphNodeList(edge_set, 3);

   215   checkGraphArcList(edge_set, 0);

   216   checkGraphEdgeList(edge_set, 0);

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

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

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

   221   checkGraphNodeList(edge_set, 3);

   222   checkGraphArcList(edge_set, 2);

   223   checkGraphEdgeList(edge_set, 1);

   225   checkGraphOutArcList(edge_set, n1, 1);

   226   checkGraphOutArcList(edge_set, n2, 1);

   227   checkGraphOutArcList(edge_set, n3, 0);

   229   checkGraphInArcList(edge_set, n1, 1);

   230   checkGraphInArcList(edge_set, n2, 1);

   231   checkGraphInArcList(edge_set, n3, 0);

   233   checkGraphIncEdgeList(edge_set, n1, 1);

   234   checkGraphIncEdgeList(edge_set, n2, 1);

   235   checkGraphIncEdgeList(edge_set, n3, 0);

   237   checkGraphConEdgeList(edge_set, 1);

   238   checkGraphConArcList(edge_set, 2);

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

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

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

   243   ::lemon::ignore_unused_variable_warning(e2,e3,e4);

   245   checkGraphNodeList(edge_set, 3);

   246   checkGraphEdgeList(edge_set, 4);

   248   checkGraphOutArcList(edge_set, n1, 2);

   249   checkGraphOutArcList(edge_set, n2, 4);

   250   checkGraphOutArcList(edge_set, n3, 2);

   252   checkGraphInArcList(edge_set, n1, 2);

   253   checkGraphInArcList(edge_set, n2, 4);

   254   checkGraphInArcList(edge_set, n3, 2);

   256   checkGraphIncEdgeList(edge_set, n1, 2);

   257   checkGraphIncEdgeList(edge_set, n2, 4);

   258   checkGraphIncEdgeList(edge_set, n3, 2);

   260   checkGraphConEdgeList(edge_set, 4);

   261   checkGraphConArcList(edge_set, 8);

   263   checkArcDirections(edge_set);

   265   checkNodeIds(edge_set);

   266   checkArcIds(edge_set);

   267   checkEdgeIds(edge_set);

   268   checkGraphNodeMap(edge_set);

   269   checkGraphArcMap(edge_set);

   270   checkGraphEdgeMap(edge_set);

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

   273   digraph.erase(n1);

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

   275 }

   277 void checkListEdgeSet() {

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

   280   typedef ListDigraph Digraph;

   281   typedef ListEdgeSet<Digraph> EdgeSet;

   283   Digraph digraph;

   284   Digraph::Node

   285     n1 = digraph.addNode(),

   286     n2 = digraph.addNode();

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

   289   ::lemon::ignore_unused_variable_warning(ga1);

   291   EdgeSet edge_set(digraph);

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

   294   ::lemon::ignore_unused_variable_warning(ga2);

   296   checkGraphNodeList(edge_set, 2);

   297   checkGraphArcList(edge_set, 0);

   298   checkGraphEdgeList(edge_set, 0);

   300   Digraph::Node

   301     n3 = digraph.addNode();

   302   checkGraphNodeList(edge_set, 3);

   303   checkGraphArcList(edge_set, 0);

   304   checkGraphEdgeList(edge_set, 0);

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

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

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

   309   checkGraphNodeList(edge_set, 3);

   310   checkGraphArcList(edge_set, 2);

   311   checkGraphEdgeList(edge_set, 1);

   313   checkGraphOutArcList(edge_set, n1, 1);

   314   checkGraphOutArcList(edge_set, n2, 1);

   315   checkGraphOutArcList(edge_set, n3, 0);

   317   checkGraphInArcList(edge_set, n1, 1);

   318   checkGraphInArcList(edge_set, n2, 1);

   319   checkGraphInArcList(edge_set, n3, 0);

   321   checkGraphIncEdgeList(edge_set, n1, 1);

   322   checkGraphIncEdgeList(edge_set, n2, 1);

   323   checkGraphIncEdgeList(edge_set, n3, 0);

   325   checkGraphConEdgeList(edge_set, 1);

   326   checkGraphConArcList(edge_set, 2);

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

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

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

   331   ::lemon::ignore_unused_variable_warning(e2,e3,e4);

   333   checkGraphNodeList(edge_set, 3);

   334   checkGraphEdgeList(edge_set, 4);

   336   checkGraphOutArcList(edge_set, n1, 2);

   337   checkGraphOutArcList(edge_set, n2, 4);

   338   checkGraphOutArcList(edge_set, n3, 2);

   340   checkGraphInArcList(edge_set, n1, 2);

   341   checkGraphInArcList(edge_set, n2, 4);

   342   checkGraphInArcList(edge_set, n3, 2);

   344   checkGraphIncEdgeList(edge_set, n1, 2);

   345   checkGraphIncEdgeList(edge_set, n2, 4);

   346   checkGraphIncEdgeList(edge_set, n3, 2);

   348   checkGraphConEdgeList(edge_set, 4);

   349   checkGraphConArcList(edge_set, 8);

   351   checkArcDirections(edge_set);

   353   checkNodeIds(edge_set);

   354   checkArcIds(edge_set);

   355   checkEdgeIds(edge_set);

   356   checkGraphNodeMap(edge_set);

   357   checkGraphArcMap(edge_set);

   358   checkGraphEdgeMap(edge_set);

   360   digraph.erase(n1);

   362   checkGraphNodeList(edge_set, 2);

   363   checkGraphArcList(edge_set, 4);

   364   checkGraphEdgeList(edge_set, 2);

   366   checkGraphOutArcList(edge_set, n2, 2);

   367   checkGraphOutArcList(edge_set, n3, 2);

   369   checkGraphInArcList(edge_set, n2, 2);

   370   checkGraphInArcList(edge_set, n3, 2);

   372   checkGraphIncEdgeList(edge_set, n2, 2);

   373   checkGraphIncEdgeList(edge_set, n3, 2);

   375   checkNodeIds(edge_set);

   376   checkArcIds(edge_set);

   377   checkEdgeIds(edge_set);

   378   checkGraphNodeMap(edge_set);

   379   checkGraphArcMap(edge_set);

   380   checkGraphEdgeMap(edge_set);

   382   checkGraphConEdgeList(edge_set, 2);

   383   checkGraphConArcList(edge_set, 4);

   385 }

   388 int main() {

   390   checkSmartArcSet();

   391   checkListArcSet();

   392   checkSmartEdgeSet();

   393   checkListEdgeSet();

   395   return 0;

   396 }

author	Balazs Dezso <deba@google.com>
	Fri, 22 Jan 2021 10:55:32 +0100
changeset 1208	c6aa2cc1af04
parent 1084	8b2d4e5d96e4
permissions	-rw-r--r--