src/work/athos/pf_demo.cc
author alpar
Fri, 07 May 2004 06:57:50 +0000
changeset 567 efaa79ee8d14
parent 201 b9158a014fe8
child 921 818510fa3d99
permissions -rw-r--r--
time_measure.cc was renamed to time_measure_test.cc
Add an alternative dijsktra_test.cc
athos@36
     1
#include <iostream>
athos@36
     2
#include <vector>
athos@36
     3
#include <string>
athos@36
     4
athos@331
     5
#include "list_graph.h"
athos@331
     6
//#include "marci_graph_traits.hh"
athos@77
     7
//#include "marci_property_vector.hh"
athos@36
     8
#include "preflow_push.hh"
athos@36
     9
alpar@105
    10
using namespace hugo;
athos@36
    11
athos@36
    12
athos@36
    13
int main (int, char*[])
athos@36
    14
{
athos@36
    15
athos@331
    16
  typedef ListGraph::Node Node;
athos@331
    17
  typedef ListGraph::Edge Edge;
athos@331
    18
athos@331
    19
  ListGraph graph;
athos@201
    20
athos@201
    21
  /*
athos@77
    22
  //Marci példája
athos@201
    23
athos@77
    24
athos@331
    25
  NodeIt s=graph.addNode();
athos@331
    26
  NodeIt v1=graph.addNode();
athos@331
    27
  NodeIt v2=graph.addNode();
athos@331
    28
  NodeIt v3=graph.addNode();
athos@331
    29
  NodeIt v4=graph.addNode();
athos@331
    30
  NodeIt t=graph.addNode();
athos@77
    31
  
athos@77
    32
athos@331
    33
  EdgeIt s_v1=graph.addEdge(s, v1);
athos@331
    34
  EdgeIt s_v2=graph.addEdge(s, v2);
athos@331
    35
  EdgeIt v1_v2=graph.addEdge(v1, v2);
athos@331
    36
  EdgeIt v2_v1=graph.addEdge(v2, v1);
athos@331
    37
  EdgeIt v1_v3=graph.addEdge(v1, v3);
athos@331
    38
  EdgeIt v3_v2=graph.addEdge(v3, v2);
athos@331
    39
  EdgeIt v2_v4=graph.addEdge(v2, v4);
athos@331
    40
  EdgeIt v4_v3=graph.addEdge(v4, v3);
athos@331
    41
  EdgeIt v3_t=graph.addEdge(v3, t);
athos@331
    42
  EdgeIt v4_t=graph.addEdge(v4, t);
athos@77
    43
athos@331
    44
  ListGraph::EdgeMap<int> length(graph);
athos@77
    45
athos@331
    46
  length.set(s_v1, 16);
athos@331
    47
  length.set(s_v2, 13);
athos@331
    48
  length.set(v1_v2, 10);
athos@331
    49
  length.set(v2_v1, 4);
athos@331
    50
  length.set(v1_v3, 12);
athos@331
    51
  length.set(v3_v2, 9);
athos@331
    52
  length.set(v2_v4, 14);
athos@331
    53
  length.set(v4_v3, 7);
athos@331
    54
  length.set(v3_t, 20);
athos@331
    55
  length.set(v4_t, 4);
athos@201
    56
  */
athos@77
    57
athos@77
    58
athos@201
    59
  //Ahuja könyv példája
athos@77
    60
athos@331
    61
  Node s=graph.addNode();
athos@331
    62
  Node v2=graph.addNode();
athos@331
    63
  Node v3=graph.addNode();
athos@331
    64
  Node v4=graph.addNode();
athos@331
    65
  Node v5=graph.addNode();
athos@331
    66
  Node t=graph.addNode();
athos@77
    67
athos@331
    68
  Edge s_v2=graph.addEdge(s, v2);
athos@331
    69
  Edge s_v3=graph.addEdge(s, v3);
athos@331
    70
  Edge v2_v4=graph.addEdge(v2, v4);
athos@331
    71
  Edge v2_v5=graph.addEdge(v2, v5);
athos@331
    72
  Edge v3_v5=graph.addEdge(v3, v5);
athos@331
    73
  Edge v4_t=graph.addEdge(v4, t);
athos@331
    74
  Edge v5_t=graph.addEdge(v5, t);
athos@36
    75
  
athos@36
    76
  //Kis modositas
athos@331
    77
  //edge_iterator v2_s=graph.add_edge(v2, s);
athos@36
    78
athos@331
    79
  ListGraph::EdgeMap<int> length(graph);
athos@201
    80
athos@331
    81
  length.set(s_v2, 10);
athos@331
    82
  length.set(s_v3, 10);
athos@331
    83
  length.set(v2_v4, 5);
athos@331
    84
  length.set(v2_v5, 8);
athos@331
    85
  length.set(v3_v5, 5);
athos@331
    86
  length.set(v4_t, 8);
athos@331
    87
  length.set(v5_t, 8);
athos@36
    88
athos@36
    89
  //Kis modositas
athos@331
    90
  //length.put(v2_s, 100);
athos@36
    91
athos@77
    92
athos@77
    93
athos@36
    94
  std::cout << "preflow-push algorithm test..." << std::endl;
athos@77
    95
athos@36
    96
  
athos@331
    97
  preflow_push<ListGraph, int> preflow_push_test(graph, s, t, length);
athos@36
    98
  cout << preflow_push_test.run()<<endl;
athos@36
    99
athos@36
   100
  //cap.put(v5_t, 9);
athos@36
   101
  //cout << preflow_push_test.run()<<endl;
athos@36
   102
athos@36
   103
  return 0;
athos@36
   104
}