src/test/kruskal_test.cc
author alpar
Wed, 16 Mar 2005 07:50:20 +0000
changeset 1215 81b4731f8a6b
parent 959 c80ef5912903
child 1359 1581f961cfaa
permissions -rw-r--r--
- '.lgf' could be the standard 'lemon graph format' extension.
- heap_test is fixed in order that 'make discheck' work.
- heap_test now checks whether the input file exists.
alpar@906
     1
/* -*- C++ -*-
alpar@921
     2
 * src/test/kruskal_test.cc - Part of LEMON, a generic C++ optimization library
alpar@906
     3
 *
alpar@1164
     4
 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@906
     5
 * (Egervary Combinatorial Optimization Research Group, EGRES).
alpar@906
     6
 *
alpar@906
     7
 * Permission to use, modify and distribute this software is granted
alpar@906
     8
 * provided that this copyright notice appears in all copies. For
alpar@906
     9
 * precise terms see the accompanying LICENSE file.
alpar@906
    10
 *
alpar@906
    11
 * This software is provided "AS IS" with no warranty of any kind,
alpar@906
    12
 * express or implied, and with no claim as to its suitability for any
alpar@906
    13
 * purpose.
alpar@906
    14
 *
alpar@906
    15
 */
alpar@906
    16
alpar@810
    17
#include <iostream>
alpar@810
    18
#include <vector>
alpar@810
    19
alpar@810
    20
#include "test_tools.h"
alpar@921
    21
#include <lemon/maps.h>
alpar@921
    22
#include <lemon/kruskal.h>
alpar@921
    23
#include <lemon/list_graph.h>
klao@959
    24
#include <lemon/concept/maps.h>
klao@959
    25
#include <lemon/concept/graph.h>
alpar@810
    26
alpar@810
    27
alpar@810
    28
using namespace std;
alpar@921
    29
using namespace lemon;
alpar@810
    30
alpar@810
    31
void checkCompileKruskal()
alpar@810
    32
{
klao@959
    33
  concept::WriteMap<concept::StaticGraph::Edge,bool> w;
alpar@810
    34
klao@959
    35
  kruskalEdgeMap(concept::StaticGraph(),
klao@959
    36
		 concept::ReadMap<concept::StaticGraph::Edge,int>(),
alpar@810
    37
		 w);
alpar@810
    38
}
alpar@810
    39
alpar@810
    40
int main() {
alpar@810
    41
alpar@810
    42
  typedef ListGraph::Node Node;
alpar@810
    43
  typedef ListGraph::Edge Edge;
alpar@810
    44
  typedef ListGraph::NodeIt NodeIt;
alpar@810
    45
  typedef ListGraph::EdgeIt EdgeIt;
alpar@810
    46
alpar@810
    47
  ListGraph G;
alpar@810
    48
alpar@810
    49
  Node s=G.addNode();
alpar@810
    50
  Node v1=G.addNode();
alpar@810
    51
  Node v2=G.addNode();
alpar@810
    52
  Node v3=G.addNode();
alpar@810
    53
  Node v4=G.addNode();
alpar@810
    54
  Node t=G.addNode();
alpar@810
    55
  
alpar@810
    56
  Edge e1 = G.addEdge(s, v1);
alpar@810
    57
  Edge e2 = G.addEdge(s, v2);
alpar@810
    58
  Edge e3 = G.addEdge(v1, v2);
alpar@810
    59
  Edge e4 = G.addEdge(v2, v1);
alpar@810
    60
  Edge e5 = G.addEdge(v1, v3);
alpar@810
    61
  Edge e6 = G.addEdge(v3, v2);
alpar@810
    62
  Edge e7 = G.addEdge(v2, v4);
alpar@810
    63
  Edge e8 = G.addEdge(v4, v3);
alpar@810
    64
  Edge e9 = G.addEdge(v3, t);
alpar@810
    65
  Edge e10 = G.addEdge(v4, t);
alpar@810
    66
alpar@810
    67
  typedef ListGraph::EdgeMap<int> ECostMap;
alpar@810
    68
  typedef ListGraph::EdgeMap<bool> EBoolMap;
alpar@810
    69
alpar@810
    70
  ECostMap edge_cost_map(G, 2);
alpar@810
    71
  EBoolMap tree_map(G);
alpar@810
    72
  
alpar@810
    73
alpar@810
    74
  //Test with const map.
alpar@810
    75
  check(kruskalEdgeMap(G, ConstMap<ListGraph::Edge,int>(2), tree_map)==10,
alpar@810
    76
	"Total cost should be 10");
alpar@810
    77
  //Test with a edge map (filled with uniform costs).
alpar@810
    78
  check(kruskalEdgeMap(G, edge_cost_map, tree_map)==10,
alpar@810
    79
	"Total cost should be 10");
alpar@810
    80
alpar@810
    81
  edge_cost_map.set(e1, -10);
alpar@810
    82
  edge_cost_map.set(e2, -9);
alpar@810
    83
  edge_cost_map.set(e3, -8);
alpar@810
    84
  edge_cost_map.set(e4, -7);
alpar@810
    85
  edge_cost_map.set(e5, -6);
alpar@810
    86
  edge_cost_map.set(e6, -5);
alpar@810
    87
  edge_cost_map.set(e7, -4);
alpar@810
    88
  edge_cost_map.set(e8, -3);
alpar@810
    89
  edge_cost_map.set(e9, -2);
alpar@810
    90
  edge_cost_map.set(e10, -1);
alpar@810
    91
alpar@810
    92
  vector<Edge> tree_edge_vec;
alpar@810
    93
alpar@810
    94
  //Test with a edge map and inserter.
alpar@810
    95
  check(kruskalEdgeMap_IteratorOut(G, edge_cost_map,
alpar@810
    96
				   back_inserter(tree_edge_vec))
alpar@810
    97
	==-31,
alpar@810
    98
	"Total cost should be -31.");
alpar@810
    99
klao@885
   100
  tree_edge_vec.clear();
klao@885
   101
klao@885
   102
  //The above test could also be coded like this:
klao@885
   103
  check(kruskal(G,
klao@885
   104
		makeKruskalMapInput(G, edge_cost_map),
klao@885
   105
		makeKruskalSequenceOutput(back_inserter(tree_edge_vec)))
klao@885
   106
	==-31,
klao@885
   107
	"Total cost should be -31.");
klao@885
   108
alpar@810
   109
  check(tree_edge_vec.size()==5,"The tree should have 5 edges.");
alpar@810
   110
alpar@810
   111
  check(tree_edge_vec[0]==e1 &&
alpar@810
   112
	tree_edge_vec[1]==e2 &&
alpar@810
   113
	tree_edge_vec[2]==e5 &&
alpar@810
   114
	tree_edge_vec[3]==e7 &&
alpar@810
   115
	tree_edge_vec[4]==e9,
alpar@810
   116
	"Wrong tree.");
alpar@810
   117
alpar@810
   118
  return 0;
alpar@810
   119
}