test/digraph_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 03 Aug 2008 13:34:57 +0200
changeset 244 c30731a37f91
parent 171 02f4d5d9bfd7
child 228 b6732e0d38c5
permissions -rw-r--r--
Many improvements in bfs.h, dfs.h and dijkstra.h
- Add run() function to Bfs and run(s,t) function to DfsVisit.
- Add debug checking to addSource() function of Dfs and DfsVisit.
- Add a few missing named parameters (according to \todo notes).
- Small fixes in the code (e.g. missing derivations).
- Many doc improvements.
- Remove \todo and \warning comments which are no longer valid.
- Remove \author commands (see ticket #39).
- Fixes in the the doc (e.g. wrong references).
- Hide the doc of most of the private and protected members.
- Use public typedefs instead of template parameters in public functions.
- Use better parameter names for some functions.
- Other small changes to make the doc more uniform.
     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  */
    18 
    19 #include <lemon/concepts/digraph.h>
    20 #include <lemon/list_graph.h>
    21 #include <lemon/smart_graph.h>
    22 //#include <lemon/full_graph.h>
    23 //#include <lemon/hypercube_graph.h>
    24 
    25 #include "test_tools.h"
    26 #include "graph_test.h"
    27 #include "graph_maps_test.h"
    28 
    29 using namespace lemon;
    30 using namespace lemon::concepts;
    31 
    32 void check_concepts() {
    33   { // Checking digraph components
    34     checkConcept<BaseDigraphComponent, BaseDigraphComponent >();
    35 
    36     checkConcept<IDableDigraphComponent<>,
    37       IDableDigraphComponent<> >();
    38 
    39     checkConcept<IterableDigraphComponent<>,
    40       IterableDigraphComponent<> >();
    41 
    42     checkConcept<MappableDigraphComponent<>,
    43       MappableDigraphComponent<> >();
    44   }
    45   { // Checking skeleton digraph
    46     checkConcept<Digraph, Digraph>();
    47   }
    48   { // Checking ListDigraph
    49     checkConcept<Digraph, ListDigraph>();
    50     checkConcept<AlterableDigraphComponent<>, ListDigraph>();
    51     checkConcept<ExtendableDigraphComponent<>, ListDigraph>();
    52     checkConcept<ClearableDigraphComponent<>, ListDigraph>();
    53     checkConcept<ErasableDigraphComponent<>, ListDigraph>();
    54     checkDigraphIterators<ListDigraph>();
    55   }
    56   { // Checking SmartDigraph
    57     checkConcept<Digraph, SmartDigraph>();
    58     checkConcept<AlterableDigraphComponent<>, SmartDigraph>();
    59     checkConcept<ExtendableDigraphComponent<>, SmartDigraph>();
    60     checkConcept<ClearableDigraphComponent<>, SmartDigraph>();
    61     checkDigraphIterators<SmartDigraph>();
    62   }
    63 //  { // Checking FullDigraph
    64 //    checkConcept<Digraph, FullDigraph>();
    65 //    checkDigraphIterators<FullDigraph>();
    66 //  }
    67 //  { // Checking HyperCubeDigraph
    68 //    checkConcept<Digraph, HyperCubeDigraph>();
    69 //    checkDigraphIterators<HyperCubeDigraph>();
    70 //  }
    71 }
    72 
    73 template <typename Digraph>
    74 void check_graph_validity() {
    75   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    76   Digraph g;
    77 
    78   Node
    79     n1 = g.addNode(),
    80     n2 = g.addNode(),
    81     n3 = g.addNode();
    82 
    83   Arc
    84     e1 = g.addArc(n1, n2),
    85     e2 = g.addArc(n2, n3);
    86 
    87   check(g.valid(n1), "Wrong validity check");
    88   check(g.valid(e1), "Wrong validity check");
    89 
    90   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
    91   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
    92 }
    93 
    94 template <typename Digraph>
    95 void check_graph_validity_erase() {
    96   TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    97   Digraph g;
    98 
    99   Node
   100     n1 = g.addNode(),
   101     n2 = g.addNode(),
   102     n3 = g.addNode();
   103 
   104   Arc
   105     e1 = g.addArc(n1, n2),
   106     e2 = g.addArc(n2, n3);
   107 
   108   check(g.valid(n1), "Wrong validity check");
   109   check(g.valid(e1), "Wrong validity check");
   110 
   111   g.erase(n1);
   112 
   113   check(!g.valid(n1), "Wrong validity check");
   114   check(g.valid(n2), "Wrong validity check");
   115   check(g.valid(n3), "Wrong validity check");
   116   check(!g.valid(e1), "Wrong validity check");
   117   check(g.valid(e2), "Wrong validity check");
   118 
   119   check(!g.valid(g.nodeFromId(-1)), "Wrong validity check");
   120   check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
   121 }
   122 
   123 void check_digraphs() {
   124   { // Checking ListDigraph
   125     checkDigraph<ListDigraph>();
   126     checkGraphNodeMap<ListDigraph>();
   127     checkGraphArcMap<ListDigraph>();
   128 
   129     check_graph_validity_erase<ListDigraph>();
   130   }
   131   { // Checking SmartDigraph
   132     checkDigraph<SmartDigraph>();
   133     checkGraphNodeMap<SmartDigraph>();
   134     checkGraphArcMap<SmartDigraph>();
   135 
   136     check_graph_validity<SmartDigraph>();
   137   }
   138 }
   139 
   140 int main() {
   141   check_concepts();
   142   check_digraphs();
   143   return 0;
   144 }