test/kruskal_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Fri, 17 Apr 2009 18:04:36 +0200
changeset 609 e6927fe719e6
parent 209 765619b7cbb2
child 581 aa1804409f29
permissions -rw-r--r--
Support >= and <= constraints in NetworkSimplex (#219, #234)

By default the same inequality constraints are supported as by
Circulation (the GEQ form), but the LEQ form can also be selected
using the problemType() function.

The documentation of the min. cost flow module is reworked and
extended with important notes and explanations about the different
variants of the problem and about the dual solution and optimality
conditions.
     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-2009
     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 "test_tools.h"
    23 #include <lemon/maps.h>
    24 #include <lemon/kruskal.h>
    25 #include <lemon/list_graph.h>
    26 
    27 #include <lemon/concepts/maps.h>
    28 #include <lemon/concepts/digraph.h>
    29 #include <lemon/concepts/graph.h>
    30 
    31 using namespace std;
    32 using namespace lemon;
    33 
    34 void checkCompileKruskal()
    35 {
    36   concepts::WriteMap<concepts::Digraph::Arc,bool> w;
    37   concepts::WriteMap<concepts::Graph::Edge,bool> uw;
    38 
    39   concepts::ReadMap<concepts::Digraph::Arc,int> r;
    40   concepts::ReadMap<concepts::Graph::Edge,int> ur;
    41 
    42   concepts::Digraph g;
    43   concepts::Graph ug;
    44 
    45   kruskal(g, r, w);
    46   kruskal(ug, ur, uw);
    47 
    48   std::vector<std::pair<concepts::Digraph::Arc, int> > rs;
    49   std::vector<std::pair<concepts::Graph::Edge, int> > urs;
    50 
    51   kruskal(g, rs, w);
    52   kruskal(ug, urs, uw);
    53 
    54   std::vector<concepts::Digraph::Arc> ws;
    55   std::vector<concepts::Graph::Edge> uws;
    56 
    57   kruskal(g, r, ws.begin());
    58   kruskal(ug, ur, uws.begin());
    59 }
    60 
    61 int main() {
    62 
    63   typedef ListGraph::Node Node;
    64   typedef ListGraph::Edge Edge;
    65   typedef ListGraph::NodeIt NodeIt;
    66   typedef ListGraph::ArcIt ArcIt;
    67 
    68   ListGraph G;
    69 
    70   Node s=G.addNode();
    71   Node v1=G.addNode();
    72   Node v2=G.addNode();
    73   Node v3=G.addNode();
    74   Node v4=G.addNode();
    75   Node t=G.addNode();
    76 
    77   Edge e1 = G.addEdge(s, v1);
    78   Edge e2 = G.addEdge(s, v2);
    79   Edge e3 = G.addEdge(v1, v2);
    80   Edge e4 = G.addEdge(v2, v1);
    81   Edge e5 = G.addEdge(v1, v3);
    82   Edge e6 = G.addEdge(v3, v2);
    83   Edge e7 = G.addEdge(v2, v4);
    84   Edge e8 = G.addEdge(v4, v3);
    85   Edge e9 = G.addEdge(v3, t);
    86   Edge e10 = G.addEdge(v4, t);
    87 
    88   typedef ListGraph::EdgeMap<int> ECostMap;
    89   typedef ListGraph::EdgeMap<bool> EBoolMap;
    90 
    91   ECostMap edge_cost_map(G, 2);
    92   EBoolMap tree_map(G);
    93 
    94 
    95   //Test with const map.
    96   check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
    97         "Total cost should be 10");
    98   //Test with an edge map (filled with uniform costs).
    99   check(kruskal(G, edge_cost_map, tree_map)==10,
   100         "Total cost should be 10");
   101 
   102   edge_cost_map.set(e1, -10);
   103   edge_cost_map.set(e2, -9);
   104   edge_cost_map.set(e3, -8);
   105   edge_cost_map.set(e4, -7);
   106   edge_cost_map.set(e5, -6);
   107   edge_cost_map.set(e6, -5);
   108   edge_cost_map.set(e7, -4);
   109   edge_cost_map.set(e8, -3);
   110   edge_cost_map.set(e9, -2);
   111   edge_cost_map.set(e10, -1);
   112 
   113   vector<Edge> tree_edge_vec(5);
   114 
   115   //Test with a edge map and inserter.
   116   check(kruskal(G, edge_cost_map,
   117                  tree_edge_vec.begin())
   118         ==-31,
   119         "Total cost should be -31.");
   120 
   121   tree_edge_vec.clear();
   122 
   123   check(kruskal(G, edge_cost_map,
   124                 back_inserter(tree_edge_vec))
   125         ==-31,
   126         "Total cost should be -31.");
   127 
   128 //   tree_edge_vec.clear();
   129 
   130 //   //The above test could also be coded like this:
   131 //   check(kruskal(G,
   132 //                 makeKruskalMapInput(G, edge_cost_map),
   133 //                 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
   134 //         ==-31,
   135 //         "Total cost should be -31.");
   136 
   137   check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
   138 
   139   check(tree_edge_vec[0]==e1 &&
   140         tree_edge_vec[1]==e2 &&
   141         tree_edge_vec[2]==e5 &&
   142         tree_edge_vec[3]==e7 &&
   143         tree_edge_vec[4]==e9,
   144         "Wrong tree.");
   145 
   146   return 0;
   147 }