test/kruskal_test.cc
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 209 765619b7cbb2
child 581 aa1804409f29
permissions -rw-r--r--
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@209
     1
/* -*- mode: C++; indent-tabs-mode: nil; -*-
alpar@103
     2
 *
alpar@209
     3
 * This file is a part of LEMON, a generic C++ optimization library.
alpar@103
     4
 *
alpar@440
     5
 * Copyright (C) 2003-2009
alpar@103
     6
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@103
     7
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@103
     8
 *
alpar@103
     9
 * Permission to use, modify and distribute this software is granted
alpar@103
    10
 * provided that this copyright notice appears in all copies. For
alpar@103
    11
 * precise terms see the accompanying LICENSE file.
alpar@103
    12
 *
alpar@103
    13
 * This software is provided "AS IS" with no warranty of any kind,
alpar@103
    14
 * express or implied, and with no claim as to its suitability for any
alpar@103
    15
 * purpose.
alpar@103
    16
 *
alpar@103
    17
 */
alpar@103
    18
alpar@103
    19
#include <iostream>
alpar@103
    20
#include <vector>
alpar@103
    21
alpar@103
    22
#include "test_tools.h"
alpar@103
    23
#include <lemon/maps.h>
alpar@103
    24
#include <lemon/kruskal.h>
alpar@103
    25
#include <lemon/list_graph.h>
alpar@103
    26
alpar@103
    27
#include <lemon/concepts/maps.h>
alpar@103
    28
#include <lemon/concepts/digraph.h>
alpar@103
    29
#include <lemon/concepts/graph.h>
alpar@103
    30
alpar@103
    31
using namespace std;
alpar@103
    32
using namespace lemon;
alpar@103
    33
alpar@103
    34
void checkCompileKruskal()
alpar@103
    35
{
alpar@103
    36
  concepts::WriteMap<concepts::Digraph::Arc,bool> w;
alpar@103
    37
  concepts::WriteMap<concepts::Graph::Edge,bool> uw;
alpar@103
    38
alpar@103
    39
  concepts::ReadMap<concepts::Digraph::Arc,int> r;
alpar@103
    40
  concepts::ReadMap<concepts::Graph::Edge,int> ur;
alpar@103
    41
alpar@103
    42
  concepts::Digraph g;
alpar@103
    43
  concepts::Graph ug;
alpar@103
    44
alpar@103
    45
  kruskal(g, r, w);
alpar@103
    46
  kruskal(ug, ur, uw);
alpar@103
    47
alpar@103
    48
  std::vector<std::pair<concepts::Digraph::Arc, int> > rs;
alpar@103
    49
  std::vector<std::pair<concepts::Graph::Edge, int> > urs;
alpar@103
    50
alpar@103
    51
  kruskal(g, rs, w);
alpar@103
    52
  kruskal(ug, urs, uw);
alpar@103
    53
alpar@103
    54
  std::vector<concepts::Digraph::Arc> ws;
alpar@103
    55
  std::vector<concepts::Graph::Edge> uws;
alpar@103
    56
alpar@103
    57
  kruskal(g, r, ws.begin());
alpar@103
    58
  kruskal(ug, ur, uws.begin());
alpar@103
    59
}
alpar@103
    60
alpar@103
    61
int main() {
alpar@103
    62
alpar@103
    63
  typedef ListGraph::Node Node;
alpar@103
    64
  typedef ListGraph::Edge Edge;
alpar@103
    65
  typedef ListGraph::NodeIt NodeIt;
alpar@103
    66
  typedef ListGraph::ArcIt ArcIt;
alpar@103
    67
alpar@103
    68
  ListGraph G;
alpar@103
    69
alpar@103
    70
  Node s=G.addNode();
alpar@103
    71
  Node v1=G.addNode();
alpar@103
    72
  Node v2=G.addNode();
alpar@103
    73
  Node v3=G.addNode();
alpar@103
    74
  Node v4=G.addNode();
alpar@103
    75
  Node t=G.addNode();
alpar@209
    76
alpar@103
    77
  Edge e1 = G.addEdge(s, v1);
alpar@103
    78
  Edge e2 = G.addEdge(s, v2);
alpar@103
    79
  Edge e3 = G.addEdge(v1, v2);
alpar@103
    80
  Edge e4 = G.addEdge(v2, v1);
alpar@103
    81
  Edge e5 = G.addEdge(v1, v3);
alpar@103
    82
  Edge e6 = G.addEdge(v3, v2);
alpar@103
    83
  Edge e7 = G.addEdge(v2, v4);
alpar@103
    84
  Edge e8 = G.addEdge(v4, v3);
alpar@103
    85
  Edge e9 = G.addEdge(v3, t);
alpar@103
    86
  Edge e10 = G.addEdge(v4, t);
alpar@103
    87
alpar@103
    88
  typedef ListGraph::EdgeMap<int> ECostMap;
alpar@103
    89
  typedef ListGraph::EdgeMap<bool> EBoolMap;
alpar@103
    90
alpar@103
    91
  ECostMap edge_cost_map(G, 2);
alpar@103
    92
  EBoolMap tree_map(G);
alpar@209
    93
alpar@103
    94
alpar@103
    95
  //Test with const map.
alpar@103
    96
  check(kruskal(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
alpar@209
    97
        "Total cost should be 10");
kpeter@171
    98
  //Test with an edge map (filled with uniform costs).
alpar@103
    99
  check(kruskal(G, edge_cost_map, tree_map)==10,
alpar@209
   100
        "Total cost should be 10");
alpar@103
   101
alpar@103
   102
  edge_cost_map.set(e1, -10);
alpar@103
   103
  edge_cost_map.set(e2, -9);
alpar@103
   104
  edge_cost_map.set(e3, -8);
alpar@103
   105
  edge_cost_map.set(e4, -7);
alpar@103
   106
  edge_cost_map.set(e5, -6);
alpar@103
   107
  edge_cost_map.set(e6, -5);
alpar@103
   108
  edge_cost_map.set(e7, -4);
alpar@103
   109
  edge_cost_map.set(e8, -3);
alpar@103
   110
  edge_cost_map.set(e9, -2);
alpar@103
   111
  edge_cost_map.set(e10, -1);
alpar@103
   112
alpar@103
   113
  vector<Edge> tree_edge_vec(5);
alpar@103
   114
alpar@103
   115
  //Test with a edge map and inserter.
alpar@103
   116
  check(kruskal(G, edge_cost_map,
alpar@209
   117
                 tree_edge_vec.begin())
alpar@209
   118
        ==-31,
alpar@209
   119
        "Total cost should be -31.");
alpar@209
   120
alpar@103
   121
  tree_edge_vec.clear();
alpar@103
   122
alpar@103
   123
  check(kruskal(G, edge_cost_map,
alpar@209
   124
                back_inserter(tree_edge_vec))
alpar@209
   125
        ==-31,
alpar@209
   126
        "Total cost should be -31.");
alpar@209
   127
alpar@103
   128
//   tree_edge_vec.clear();
alpar@209
   129
alpar@103
   130
//   //The above test could also be coded like this:
alpar@103
   131
//   check(kruskal(G,
alpar@209
   132
//                 makeKruskalMapInput(G, edge_cost_map),
alpar@209
   133
//                 makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
alpar@209
   134
//         ==-31,
alpar@209
   135
//         "Total cost should be -31.");
alpar@103
   136
alpar@103
   137
  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
alpar@103
   138
alpar@103
   139
  check(tree_edge_vec[0]==e1 &&
alpar@209
   140
        tree_edge_vec[1]==e2 &&
alpar@209
   141
        tree_edge_vec[2]==e5 &&
alpar@209
   142
        tree_edge_vec[3]==e7 &&
alpar@209
   143
        tree_edge_vec[4]==e9,
alpar@209
   144
        "Wrong tree.");
alpar@103
   145
alpar@103
   146
  return 0;
alpar@103
   147
}