test/graph_utils_test.cc
author kpeter
Sun, 05 Oct 2008 13:36:43 +0000
changeset 2619 30fb4d68b0e8
parent 2391 14a343be7a5a
permissions -rw-r--r--
Improve network simplex algorithm

- Remove "Limited Search" and "Combined" pivot rules.
- Add a new pivot rule "Altering Candidate List".
- Make the edge selection faster in every pivot rule.
- Set the default rule to "Block Search".
- Doc improvements.

The algorithm became about 15-35 percent faster on various input files.
"Block Search" pivot rule proved to be by far the fastest on all inputs.
     1 /* -*- C++ -*-
     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 <iostream>
    20 #include <vector>
    21 
    22 #include <lemon/graph_utils.h>
    23 
    24 #include <lemon/list_graph.h>
    25 #include <lemon/smart_graph.h>
    26 #include <lemon/full_graph.h>
    27 
    28 #include "test_tools.h"
    29 #include "graph_utils_test.h"
    30 
    31 
    32 using namespace lemon;
    33 
    34 template<class Graph>
    35 void checkSnapDeg() 
    36 {
    37   Graph g;
    38   typename Graph::Node n1=g.addNode();
    39   typename Graph::Node n2=g.addNode();
    40    
    41   InDegMap<Graph> ind(g);
    42  
    43   g.addEdge(n1,n2);
    44   
    45   typename Graph::Snapshot snap(g);
    46   
    47   OutDegMap<Graph> outd(g);
    48   
    49   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    50   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    51 
    52   g.addEdge(n1,n2);
    53   g.addEdge(n2,n1);
    54  
    55   check(ind[n1]==1 && ind[n2]==2, "Wrong InDegMap value.");
    56   check(outd[n1]==2 && outd[n2]==1, "Wrong OutDegMap value.");
    57 
    58   snap.restore();
    59 
    60   check(ind[n1]==0 && ind[n2]==1, "Wrong InDegMap value.");
    61   check(outd[n1]==1 && outd[n2]==0, "Wrong OutDegMap value.");
    62   
    63 }
    64 
    65 int main() {
    66   ///\file
    67   { // checking list graph
    68     checkGraphCounters<ListGraph>();
    69     checkFindEdge<ListGraph>();
    70   }
    71   { // checking smart graph
    72     checkGraphCounters<SmartGraph>();
    73     checkFindEdge<SmartGraph>();
    74   }
    75   {
    76     int num = 5;
    77     FullGraph fg(num);
    78     check(countNodes(fg) == num, "FullGraph: wrong node number.");
    79     check(countEdges(fg) == num*num, "FullGraph: wrong edge number.");
    80     for (FullGraph::NodeIt src(fg); src != INVALID; ++src) {
    81       for (FullGraph::NodeIt trg(fg); trg != INVALID; ++trg) {
    82 	ConEdgeIt<FullGraph> con(fg, src, trg);
    83 	check(con != INVALID, "There is no connecting edge.");
    84 	check(fg.source(con) == src, "Wrong source.");
    85 	check(fg.target(con) == trg, "Wrong target.");
    86 	check(++con == INVALID, "There is more connecting edge.");
    87       }
    88     }
    89     AllEdgeLookUp<FullGraph> el(fg);
    90     for (FullGraph::NodeIt src(fg); src != INVALID; ++src) {
    91       for (FullGraph::NodeIt trg(fg); trg != INVALID; ++trg) {
    92 	FullGraph::Edge con = el(src, trg);
    93 	check(con != INVALID, "There is no connecting edge.");
    94 	check(fg.source(con) == src, "Wrong source.");
    95 	check(fg.target(con) == trg, "Wrong target.");
    96 	check(el(src,trg,con) == INVALID, "There is more connecting edge.");
    97       }
    98     }
    99   }
   100 
   101   //check In/OutDegMap (and Snapshot feature)
   102 
   103   checkSnapDeg<ListGraph>();
   104   checkSnapDeg<SmartGraph>();
   105   
   106   {
   107     const int nodeNum = 10;
   108     const int edgeNum = 100;
   109     ListGraph graph;
   110     InDegMap<ListGraph> inDeg(graph);
   111     OutDegMap<ListGraph> outDeg(graph);
   112     std::vector<ListGraph::Node> nodes(nodeNum);
   113     for (int i = 0; i < nodeNum; ++i) {
   114       nodes[i] = graph.addNode();
   115     }
   116     std::vector<ListGraph::Edge> edges(edgeNum);
   117     for (int i = 0; i < edgeNum; ++i) {
   118       edges[i] = 
   119 	graph.addEdge(nodes[rnd[nodeNum]], nodes[rnd[nodeNum]]);
   120     }
   121     for (int i = 0; i < nodeNum; ++i) {
   122       check(inDeg[nodes[i]] == countInEdges(graph, nodes[i]), 
   123 	    "Wrong in degree map");
   124     }
   125     for (int i = 0; i < nodeNum; ++i) {
   126       check(outDeg[nodes[i]] == countOutEdges(graph, nodes[i]), 
   127 	    "Wrong in degree map");
   128     }
   129   }
   130 
   131   ///Everything is OK
   132   std::cout << __FILE__ ": All tests passed.\n";
   133 
   134   return 0;
   135 }