COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 946:c94ef40a22ce in lemon-0.x for src/test


Ignore:
Timestamp:
10/28/04 00:38:50 (20 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1322
Message:

The graph_factory branch (@ 1321) has been merged to trunk.

Location:
src/test
Files:
5 added
5 edited

Legend:

Unmodified
Added
Removed

  • src/test/Makefile.am

    r938 r946  
    33EXTRA_DIST = preflow_graph.dim #input file for preflow_test.cc
    44
    5 noinst_HEADERS = test_tools.h graph_test.h sym_graph_test.h
     5noinst_HEADERS = \
     6        test_tools.h \
     7        graph_test.h \
     8        sym_graph_test.h \
     9        map_test.h \
     10        graph_utils_test.h
    611
    712check_PROGRAMS = \
    … …  
    1015        dijkstra_test \
    1116        graph_test \
    12         sym_graph_test \
    13         graph_wrapper_test \
     17        graph_utils_test \
    1418        kruskal_test \
    1519        min_cost_flow_test \
     20        new_graph_test \
    1621        suurballe_test \
    1722        path_test \
    … …  
    2126        time_measure_test \
    2227        unionfind_test \
     28        graph_wrapper_test \
    2329        xy_test
    2430
    … …  
    3036dijkstra_test_SOURCES = dijkstra_test.cc
    3137graph_test_SOURCES = graph_test.cc
    32 sym_graph_test_SOURCES = sym_graph_test.cc
     38graph_utils_test_SOURCES = graph_utils_test.cc
    3339graph_wrapper_test_SOURCES = graph_wrapper_test.cc
    3440kruskal_test_SOURCES = kruskal_test.cc
    3541min_cost_flow_test_SOURCES = min_cost_flow_test.cc
     42new_graph_test_SOURCES = new_graph_test.cc
    3643suurballe_test_SOURCES = suurballe_test.cc
    3744path_test_SOURCES = path_test.cc

  • src/test/graph_test.cc

    r938 r946  
    1 /* -*- C++ -*-
    2  * src/test/graph_test.cc - Part of LEMON, a generic C++ optimization library
    3  *
    4  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    5  * (Egervary Combinatorial Optimization Research Group, EGRES).
    6  *
    7  * Permission to use, modify and distribute this software is granted
    8  * provided that this copyright notice appears in all copies. For
    9  * precise terms see the accompanying LICENSE file.
    10  *
    11  * This software is provided "AS IS" with no warranty of any kind,
    12  * express or implied, and with no claim as to its suitability for any
    13  * purpose.
    14  *
    15  */
     1// -*- c++ -*-
    162
    17 #include<iostream>
    18 #include<lemon/smart_graph.h>
    19 #include<lemon/skeletons/graph.h>
    20 #include<lemon/list_graph.h>
    21 #include<lemon/full_graph.h>
     3#include <iostream>
     4#include <vector>
    225
    23 #include"test_tools.h"
    24 #include"graph_test.h"
     6#include <lemon/skeletons/graph.h>
     7#include <lemon/list_graph.h>
     8#include <lemon/smart_graph.h>
     9#include <lemon/full_graph.h>
    2510
    26 /**
    27 \file
    28 This test makes consistency checks of list graph structures.
     11#include "test_tools.h"
     12#include "graph_test.h"
     13#include "map_test.h"
    2914
    30 G.addNode(), G.addEdge(), G.tail(), G.head()
    31 
    32 \todo Checks for empty graphs and isolated points.
    33 conversion.
    34 */
    3515
    3616using namespace lemon;
    37 
    38 template<class Graph> void bidirPetersen(Graph &G)
    39 {
    40   typedef typename Graph::Edge Edge;
    41   typedef typename Graph::EdgeIt EdgeIt;
    42  
    43   checkGraphEdgeList(G,15);
    44  
    45   std::vector<Edge> ee;
    46  
    47   for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
    48 
    49   for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
    50     G.addEdge(G.head(*p),G.tail(*p));
    51 }
    52 
    53 template<class Graph> void checkPetersen(Graph &G)
    54 {
    55   typedef typename Graph::Node Node;
    56 
    57   typedef typename Graph::EdgeIt EdgeIt;
    58   typedef typename Graph::NodeIt NodeIt;
    59 
    60   checkGraphNodeList(G,10);
    61   checkGraphEdgeList(G,30);
    62 
    63   for(NodeIt n(G);n!=INVALID;++n) {
    64     checkGraphInEdgeList(G,n,3);
    65     checkGraphOutEdgeList(G,n,3);
    66   } 
    67 }
    68 
    69 //Compile Graph
    70 template void lemon::skeleton::checkCompileStaticGraph<skeleton::StaticGraph>
    71 (skeleton::StaticGraph &);
    72 
    73 template
    74 void lemon::skeleton::checkCompileExtendableGraph<skeleton::ExtendableGraph>
    75 (skeleton::ExtendableGraph &);
    76 
    77 template
    78 void lemon::skeleton::checkCompileErasableGraph<skeleton::ErasableGraph>
    79 (skeleton::ErasableGraph &);
    80 
    81 //Compile SmartGraph
    82 template
    83 void lemon::skeleton::checkCompileExtendableGraph<SmartGraph>(SmartGraph &);
    84 template
    85 void lemon::skeleton::checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
    86 
    87 //Compile SymSmartGraph
    88 //template void hugo::checkCompileGraph<SymSmartGraph>(SymSmartGraph &);
    89 //template void hugo::checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
    90 
    91 //Compile ListGraph
    92 template
    93 void lemon::skeleton::checkCompileExtendableGraph<ListGraph>(ListGraph &);
    94 template
    95 void lemon::skeleton::checkCompileErasableGraph<ListGraph>(ListGraph &);
    96 template
    97 void lemon::skeleton::checkCompileGraphFindEdge<ListGraph>(ListGraph &);
     17using namespace lemon::skeleton;
    9818
    9919
    100 //Compile SymListGraph
    101 //template void hugo::checkCompileGraph<SymListGraph>(SymListGraph &);
    102 //template void hugo::checkCompileErasableGraph<SymListGraph>(SymListGraph &);
    103 //template void hugo::checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
     20int main() {
     21  ///\file
     22  { // checking graph components
     23    function_requires<BaseGraphComponentConcept<BaseGraphComponent> >();
    10424
    105 //Compile FullGraph
    106 template void lemon::skeleton::checkCompileStaticGraph<FullGraph>(FullGraph &);
    107 template
    108 void lemon::skeleton::checkCompileGraphFindEdge<FullGraph>(FullGraph &);
     25    function_requires<BaseIterableGraphComponentConcept<BaseIterableGraphComponent> >();
    10926
    110 //Compile EdgeSet <ListGraph>
    111 template void lemon::skeleton::checkCompileExtendableGraph<EdgeSet <ListGraph> >
    112 (EdgeSet <ListGraph> &);
    113 template void lemon::skeleton::checkCompileGraphEraseEdge<EdgeSet <ListGraph> >
    114 (EdgeSet <ListGraph> &);
    115 template void lemon::skeleton::checkCompileGraphFindEdge<EdgeSet <ListGraph> >
    116 (EdgeSet <ListGraph> &);
     27    function_requires<IDableGraphComponentConcept<IDableGraphComponent> >();
     28    function_requires<MaxIDableGraphComponentConcept<MaxIDableGraphComponent> >();
    11729
    118 //Compile EdgeSet <NodeSet>
    119 template void lemon::skeleton::checkCompileExtendableGraph<EdgeSet <NodeSet> >
    120 (EdgeSet <NodeSet> &);
    121 template void lemon::skeleton::checkCompileGraphEraseEdge<EdgeSet <NodeSet> >
    122 (EdgeSet <NodeSet> &);
    123 template void lemon::skeleton::checkCompileGraphFindEdge<EdgeSet <NodeSet> >
    124 (EdgeSet <NodeSet> &);
     30    function_requires<BaseExtendableGraphComponentConcept<BaseExtendableGraphComponent> >();
     31    function_requires<BaseErasableGraphComponentConcept<BaseErasableGraphComponent> >();
     32    function_requires<BaseClearableGraphComponentConcept<BaseClearableGraphComponent> >();
    12533
     34    function_requires<IterableGraphComponentConcept<IterableGraphComponent> >();
    12635
    127 int main()
    128 {
    129   {
    130     SmartGraph G;
    131     addPetersen(G);
    132     bidirPetersen(G);
    133     checkPetersen(G);
     36    function_requires<IdMappableGraphComponentConcept<IdMappableGraphComponent> >();
     37    function_requires<MappableGraphComponentConcept<MappableGraphComponent> >();
     38
     39    function_requires<ExtendableGraphComponentConcept<ExtendableGraphComponent> >();
     40    function_requires<ErasableGraphComponentConcept<ErasableGraphComponent> >();
     41    function_requires<ClearableGraphComponentConcept<ClearableGraphComponent> >();
    13442  }
    135   {
    136     ListGraph G;
    137     addPetersen(G);
    138     bidirPetersen(G);
    139     checkPetersen(G);
     43  { // checking skeleton graphs
     44    function_requires<StaticGraphConcept<StaticGraph> >();
     45    function_requires<ExtendableGraphConcept<ExtendableGraph> >();
     46    function_requires<ErasableGraphConcept<ErasableGraph> >();
    14047  }
    141   {
    142     //    SymSmartGraph G;
    143     //    addPetersen(G);
    144     //    checkPetersen(G);
     48  { // checking list graph
     49    function_requires<ErasableGraphConcept<ListGraph> >();
     50
     51    checkGraph<ListGraph>();
     52    checkGraphNodeMap<ListGraph>();
     53    checkGraphEdgeMap<ListGraph>();
    14554  }
    146   {
    147     //    SymListGraph G;
    148     //    addPetersen(G);
    149     //    checkPetersen(G);
     55  { // checking smart graph
     56    function_requires<ExtendableGraphConcept<SmartGraph> >();
     57
     58    checkGraph<SmartGraph>();
     59    checkGraphNodeMap<SmartGraph>();
     60    checkGraphEdgeMap<SmartGraph>();
    15061  }
    151 
    152   ///\file
    153   ///\todo map tests.
    154   ///\todo copy constr tests.
     62  { // checking full graph
     63    function_requires<StaticGraphConcept<FullGraph> >();
     64  }
    15565
    15666  std::cout << __FILE__ ": All tests passed.\n";

  • src/test/graph_test.h

    r938 r946  
    2222//! \ingroup misc
    2323//! \file
    24 //! \brief Some utility to test graph classes.
     24//! \brief Some utility and test cases to test graph classes.
    2525namespace lemon {
    2626
    2727  template<class Graph> void checkGraphNodeList(Graph &G, int nn)
    28     {
    29       typename Graph::NodeIt n(G);
    30       for(int i=0;i<nn;i++) {
    31         check(n!=INVALID,"Wrong Node list linking.");
    32         ++n;
    33       }
    34       check(n==INVALID,"Wrong Node list linking.");
     28  {
     29    typename Graph::NodeIt n(G);
     30    for(int i=0;i<nn;i++) {
     31      check(n!=INVALID,"Wrong Node list linking.");
     32      ++n;
    3533    }
     34    check(n==INVALID,"Wrong Node list linking.");
     35  }
    3636
    37   template<class Graph> void checkGraphEdgeList(Graph &G, int nn)
    38     {
    39       typedef typename Graph::EdgeIt EdgeIt;
     37  template<class Graph>
     38  void checkGraphEdgeList(Graph &G, int nn)
     39  {
     40    typedef typename Graph::EdgeIt EdgeIt;
    4041
    41       EdgeIt e(G);
    42       for(int i=0;i<nn;i++) {
    43         check(e!=INVALID,"Wrong Edge list linking.");
    44         ++e;
    45       }
    46       check(e==INVALID,"Wrong Edge list linking.");
     42    EdgeIt e(G);
     43    for(int i=0;i<nn;i++) {
     44      check(e!=INVALID,"Wrong Edge list linking.");
     45      ++e;
    4746    }
     47    check(e==INVALID,"Wrong Edge list linking.");
     48  }
    4849
    49   template<class Graph> void checkGraphOutEdgeList(Graph &G,
    50                                                    typename Graph::Node n,
    51                                                    int nn)
    52     {
    53       typename Graph::OutEdgeIt e(G,n);
    54       for(int i=0;i<nn;i++) {
    55         check(e!=INVALID,"Wrong OutEdge list linking.");
    56         check(n==G.tail(e), "Wrong OutEdge list linking.");
    57         ++e;
    58       }
    59       check(e==INVALID,"Wrong OutEdge list linking.");
     50  template<class Graph>
     51  void checkGraphOutEdgeList(Graph &G, typename Graph::Node n, int nn)
     52  {
     53    typename Graph::OutEdgeIt e(G,n);
     54    for(int i=0;i<nn;i++) {
     55      check(e!=INVALID,"Wrong OutEdge list linking.");
     56      check(n==G.tail(e), "Wrong OutEdge list linking.");
     57      ++e;
    6058    }
     59    check(e==INVALID,"Wrong OutEdge list linking.");
     60  }
    6161
    62   template<class Graph> void checkGraphInEdgeList(Graph &G,
    63                                                   typename Graph::Node n,
    64                                                   int nn)
    65     {
    66       typename Graph::InEdgeIt e(G,n);
    67       for(int i=0;i<nn;i++) {
    68         check(e!=INVALID,"Wrong InEdge list linking.");
    69         check(n==G.head(e), "Wrong InEdge list linking.");
    70         ++e;
    71       }
    72       check(e==INVALID,"Wrong InEdge list linking.");
     62  template<class Graph> void
     63  checkGraphInEdgeList(Graph &G, typename Graph::Node n, int nn)
     64  {
     65    typename Graph::InEdgeIt e(G,n);
     66    for(int i=0;i<nn;i++) {
     67      check(e!=INVALID,"Wrong InEdge list linking.");
     68      check(n==G.head(e), "Wrong InEdge list linking.");
     69      ++e;
    7370    }
     71    check(e==INVALID,"Wrong InEdge list linking.");
     72  }
     73
     74  template <class Graph>
     75  void checkGraph() {
     76    const int num = 5;
     77    Graph G;
     78    addPetersen(G, num);
     79    bidirGraph(G);
     80    checkBidirPetersen(G, num);
     81  }
    7482
    7583  ///\file

  • src/test/graph_wrapper_test.cc

    r938 r946  
    1616
    1717#include<iostream>
     18#include<lemon/concept_check.h>
     19
    1820#include<lemon/smart_graph.h>
    1921#include<lemon/skeletons/graph.h>
     22
    2023#include<lemon/list_graph.h>
    2124#include<lemon/full_graph.h>
    … …  
    3336
    3437using namespace lemon;
     38using namespace lemon::skeleton;
    3539
    3640
    3741typedef SmartGraph Graph;
    3842
    39 //Compile GraphWrapper
    40 typedef GraphWrapper<Graph> GW;
    41 template void lemon::skeleton::checkCompileStaticGraph<GW>(GW &);
    42 
    43 //Compile RevGraphWrapper
    44 typedef RevGraphWrapper<Graph> RevGW;
    45 template void lemon::skeleton::checkCompileStaticGraph<RevGW>(RevGW &);
    46 
    47 //Compile SubGraphWrapper
    48 typedef SubGraphWrapper<Graph, Graph::NodeMap<bool>,
    49                         Graph::EdgeMap<bool> > SubGW;
    50 template void lemon::skeleton::checkCompileStaticGraph<SubGW>(SubGW &);
    51 
    52 //Compile NodeSubGraphWrapper
    53 typedef NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > NodeSubGW;
    54 template void lemon::skeleton::checkCompileStaticGraph<NodeSubGW>(NodeSubGW &);
    55 
    56 //Compile EdgeSubGraphWrapper
    57 typedef EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > EdgeSubGW;
    58 template void lemon::skeleton::checkCompileStaticGraph<EdgeSubGW>(EdgeSubGW &);
    59 
    60 //Compile UndirGraphWrapper
    61 /// \bug UndirGraphWrapper cannot pass the StaticGraph test
    62 //typedef UndirGraphWrapper<Graph> UndirGW;
    63 //template void checkCompileStaticGraph<UndirGW>(UndirGW &);
    64 
    65 //Compile UndirGraph
    66 //typedef UndirGraph<Graph> UndirG;
    67 //template void checkCompileStaticGraph<UndirG>(UndirG &);
    68 
    69 //Compile SubBidirGraphWrapper
    70 typedef SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>,
    71                              Graph::EdgeMap<bool> > SubBDGW;
    72 template void lemon::skeleton::checkCompileStaticGraph<SubBDGW>(SubBDGW &);
    73 
    74 //Compile BidirGraphWrapper
    75 typedef BidirGraphWrapper<Graph> BidirGW;
    76 template void lemon::skeleton::checkCompileStaticGraph<BidirGW>(BidirGW &);
    77 
    78 //Compile BidirGraph
    79 typedef BidirGraph<Graph> BidirG;
    80 template void lemon::skeleton::checkCompileStaticGraph<BidirG>(BidirG &);
    81 
    82 //Compile ResGraphWrapper
    83 typedef ResGraphWrapper<Graph, int, Graph::EdgeMap<int>,
    84                         Graph::EdgeMap<int> > ResGW;
    85 template void lemon::skeleton::checkCompileStaticGraph<ResGW>(ResGW &);
    86 
    87 //Compile ErasingFirstGraphWrapper
    88 typedef ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > ErasingFirstGW;
    89 template
    90 void lemon::skeleton::checkCompileStaticGraph<ErasingFirstGW>(ErasingFirstGW &);
    91 
    9243
    9344int main()
    9445{
     46  {
     47    function_requires<StaticGraphConcept<GraphWrapper<Graph> > >();
     48
     49    function_requires<StaticGraphConcept<RevGraphWrapper<Graph> > >();
     50
     51    function_requires<StaticGraphConcept<SubGraphWrapper<Graph, Graph::NodeMap<bool> , Graph::EdgeMap<bool> > > >();
     52    function_requires<StaticGraphConcept<NodeSubGraphWrapper<Graph, Graph::NodeMap<bool> > > >();
     53    function_requires<StaticGraphConcept<EdgeSubGraphWrapper<Graph, Graph::EdgeMap<bool> > > >();
     54
     55    function_requires<StaticGraphConcept<SubBidirGraphWrapper<Graph, Graph::EdgeMap<bool>, Graph::EdgeMap<bool> > > > ();
     56
     57    function_requires<StaticGraphConcept<BidirGraph<Graph> > >();
     58
     59    function_requires<StaticGraphConcept<ResGraphWrapper<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > > >();
     60
     61    function_requires<StaticGraphConcept<ErasingFirstGraphWrapper<Graph, Graph::NodeMap<Graph::Edge> > > >();
     62  }
    9563  std::cout << __FILE__ ": All tests passed.\n";
    9664

  • src/test/test_tools.h

    r937 r946  
    7171
    7272template<typename Graph>
    73 PetStruct<Graph> addPetersen(Graph &G,int num=5)
     73PetStruct<Graph> addPetersen(Graph &G,int num = 5)
    7474{
    7575  PetStruct<Graph> n;
    … …  
    8282 for(int i=0;i<num;i++) {
    8383   n.chords.push_back(G.addEdge(n.outer[i],n.inner[i]));
    84    n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1)%5]));
    85    n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2)%5]));
     84   n.outcir.push_back(G.addEdge(n.outer[i],n.outer[(i+1) % num]));
     85   n.incir.push_back(G.addEdge(n.inner[i],n.inner[(i+2) % num]));
    8686  }
    8787 return n;
     88}
     89
     90/// \brief Adds to the graph the reverse pair of all edge.
     91///
     92/// Adds to the graph the reverse pair of all edge.
     93///
     94template<class Graph> void bidirGraph(Graph &G)
     95{
     96  typedef typename Graph::Edge Edge;
     97  typedef typename Graph::EdgeIt EdgeIt;
     98 
     99  std::vector<Edge> ee;
     100 
     101  for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
     102
     103  for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
     104    G.addEdge(G.head(*p),G.tail(*p));
     105}
     106
     107
     108/// \brief Checks the bidirectioned Petersen graph.
     109///
     110///  Checks the bidirectioned Petersen graph.
     111///
     112template<class Graph> void checkBidirPetersen(Graph &G, int num = 5)
     113{
     114  typedef typename Graph::Node Node;
     115
     116  typedef typename Graph::EdgeIt EdgeIt;
     117  typedef typename Graph::NodeIt NodeIt;
     118
     119  checkGraphNodeList(G, 2 * num);
     120  checkGraphEdgeList(G, 6 * num);
     121
     122  for(NodeIt n(G);n!=INVALID;++n) {
     123    checkGraphInEdgeList(G, n, 3);
     124    checkGraphOutEdgeList(G, n, 3);
     125  } 
    88126}
    89127
Note: See TracChangeset for help on using the changeset viewer.