src/work/marci_graph_demo.cc
author marci
Wed, 31 Mar 2004 16:38:38 +0000
changeset 270 e4811faaaa75
parent 168 27fbd1559fb7
permissions -rw-r--r--
Ment-e a dereferalasok sporolasaval elobbre a vilag?
marci@9
     1
#include <iostream>
marci@9
     2
#include <vector>
marci@9
     3
#include <string>
marci@9
     4
marci@243
     5
#include <list_graph.h>
marci@243
     6
#include <bfs_iterator.h>
marci@243
     7
#include <edmonds_karp.h>
marci@9
     8
alpar@107
     9
using namespace hugo;
marci@9
    10
marci@9
    11
int main (int, char*[])
marci@9
    12
{
marci@243
    13
  typedef ListGraph::Node Node;
marci@243
    14
  typedef ListGraph::Edge Edge;
marci@49
    15
  typedef ListGraph::NodeIt NodeIt;
marci@49
    16
  typedef ListGraph::EdgeIt EdgeIt;
marci@49
    17
  typedef ListGraph::OutEdgeIt OutEdgeIt;
marci@49
    18
  typedef ListGraph::InEdgeIt InEdgeIt;
marci@49
    19
  typedef ListGraph::SymEdgeIt SymEdgeIt;
marci@49
    20
  ListGraph G;
marci@243
    21
  std::vector<Node> vector_of_Nodes;
marci@243
    22
  for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
marci@9
    23
  for(int i=0; i!=8; ++i)
marci@49
    24
    for(int j=0; j!=8; ++j) 
marci@243
    25
      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
marci@9
    26
marci@9
    27
  std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
marci@243
    28
  std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
marci@9
    29
marci@243
    30
  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
marci@9
    31
    std::cout << "node " << G.id(i) << std::endl;
marci@49
    32
    std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " "; 
marci@243
    33
    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
marci@9
    34
      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
marci@9
    35
    }
marci@9
    36
    std::cout << std::endl; 
marci@12
    37
marci@12
    38
    std::cout<< " ";
marci@243
    39
    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) { 
marci@49
    40
      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
marci@12
    41
    std::cout<<std::endl;
marci@12
    42
marci@49
    43
    std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
marci@243
    44
    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 
marci@9
    45
      std::cout << j << " "; } 
marci@9
    46
    std::cout << std::endl;
marci@12
    47
marci@12
    48
    std::cout<< " ";
marci@243
    49
    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) { 
marci@49
    50
      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
marci@12
    51
    std::cout<<std::endl;
marci@12
    52
marci@49
    53
    std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
marci@243
    54
    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 
marci@9
    55
      std::cout << j << " "; } 
marci@9
    56
    std::cout<<std::endl;
marci@12
    57
marci@12
    58
    std::cout<< " ";
marci@243
    59
    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) { 
marci@49
    60
      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; } 
marci@12
    61
    std::cout<<std::endl;
marci@9
    62
  }
marci@9
    63
marci@9
    64
  std::cout << "all edges: ";
marci@243
    65
  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
marci@9
    66
    std::cout << i << " ";
marci@9
    67
  }
marci@9
    68
  std::cout << std::endl;
marci@9
    69
marci@9
    70
  std::cout << "node property array test" << std::endl;
marci@49
    71
  ListGraph::NodeMap<int> my_property_vector(G);
marci@243
    72
  NodeIt v;
marci@243
    73
  G.first(v);
marci@49
    74
  my_property_vector.set(v, 42);
marci@243
    75
  my_property_vector.set(G.next(G.first<NodeIt>()), 314);
marci@243
    76
  my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
marci@243
    77
  my_property_vector.set(vector_of_Nodes[3], 1989);
marci@243
    78
  my_property_vector.set(vector_of_Nodes[4], 2003);
marci@243
    79
  my_property_vector.set(vector_of_Nodes[7], 1978);
marci@9
    80
  std::cout << "some node property values..." << std::endl;
marci@243
    81
  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
marci@9
    82
    std::cout << my_property_vector.get(i) << std::endl;
marci@9
    83
  }
marci@9
    84
  int _i=1;
marci@9
    85
  int _ii=1;
marci@49
    86
  ListGraph::EdgeMap<int> my_edge_property(G);
marci@243
    87
  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
marci@49
    88
    my_edge_property.set(i, _i);
marci@9
    89
    _i*=_ii; ++_ii;
marci@9
    90
  }
marci@9
    91
marci@9
    92
  std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
marci@243
    93
  for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
marci@9
    94
    std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
marci@9
    95
  }
marci@9
    96
  std::cout << std::endl;
marci@75
    97
/*
marci@9
    98
  std::cout << "bfs from the first node" << std::endl;
marci@243
    99
  bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
marci@9
   100
  bfs_test.run();
marci@9
   101
  std::cout << "reached: ";
marci@243
   102
  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
marci@9
   103
    std::cout << bfs_test.reached.get(i) << " ";
marci@9
   104
  }
marci@9
   105
  std::cout<<std::endl;
marci@9
   106
  std::cout << "dist: ";
marci@243
   107
  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
marci@9
   108
    std::cout << bfs_test.dist.get(i) << " ";
marci@9
   109
  }
marci@9
   110
  std::cout<<std::endl;
marci@75
   111
*/
marci@9
   112
marci@9
   113
  std::cout << "augmenting path flow algorithm test..." << std::endl;
marci@49
   114
  ListGraph flowG;
marci@9
   115
marci@243
   116
  Node s=flowG.addNode();
marci@243
   117
  Node v1=flowG.addNode();
marci@243
   118
  Node v2=flowG.addNode();
marci@243
   119
  Node v3=flowG.addNode();
marci@243
   120
  Node v4=flowG.addNode();
marci@243
   121
  Node t=flowG.addNode();
marci@9
   122
  
marci@49
   123
  ListGraph::NodeMap<std::string> node_name(flowG);
marci@49
   124
  node_name.set(s, "s");
marci@49
   125
  node_name.set(v1, "v1");
marci@49
   126
  node_name.set(v2, "v2");
marci@49
   127
  node_name.set(v3, "v3");
marci@49
   128
  node_name.set(v4, "v4");
marci@49
   129
  node_name.set(t, "t");
marci@9
   130
marci@243
   131
  Edge s_v1=flowG.addEdge(s, v1);
marci@243
   132
  Edge s_v2=flowG.addEdge(s, v2);
marci@243
   133
  Edge v1_v2=flowG.addEdge(v1, v2);
marci@243
   134
  Edge v2_v1=flowG.addEdge(v2, v1);
marci@243
   135
  Edge v1_v3=flowG.addEdge(v1, v3);
marci@243
   136
  Edge v3_v2=flowG.addEdge(v3, v2);
marci@243
   137
  Edge v2_v4=flowG.addEdge(v2, v4);
marci@243
   138
  Edge v4_v3=flowG.addEdge(v4, v3);
marci@243
   139
  Edge v3_t=flowG.addEdge(v3, t);
marci@243
   140
  Edge v4_t=flowG.addEdge(v4, t);
marci@9
   141
marci@49
   142
  ListGraph::EdgeMap<int> cap(flowG);
marci@9
   143
marci@49
   144
  cap.set(s_v1, 16);
marci@49
   145
  cap.set(s_v2, 13);
marci@49
   146
  cap.set(v1_v2, 10);
marci@49
   147
  cap.set(v2_v1, 4);
marci@49
   148
  cap.set(v1_v3, 12);
marci@49
   149
  cap.set(v3_v2, 9);
marci@49
   150
  cap.set(v2_v4, 14);
marci@49
   151
  cap.set(v4_v3, 7);
marci@49
   152
  cap.set(v3_t, 20);
marci@49
   153
  cap.set(v4_t, 4);
marci@9
   154
marci@49
   155
  std::cout << "on directed graph graph" << std::endl; //<< flowG;
marci@9
   156
  std::cout << "names and capacity values" << std::endl; 
marci@243
   157
  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
marci@9
   158
    std::cout << node_name.get(i) << ": ";
marci@9
   159
    std::cout << "out edges: ";
marci@243
   160
    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   161
      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@9
   162
    std::cout << "in edges: ";
marci@243
   163
    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   164
      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@9
   165
    std::cout << std::endl;
marci@9
   166
  }
marci@9
   167
marci@60
   168
  //flowG.deleteEdge(s_v1);
marci@60
   169
  //flowG.deleteEdge(s_v2);
marci@60
   170
  //flowG.deleteEdge(v1_v2);
marci@60
   171
  //flowG.deleteEdge(v1_v3);
marci@60
   172
  
marci@60
   173
marci@49
   174
  //flowG.setTail(v3_t, v2);
marci@49
   175
  //flowG.setHead(v3_t, s);
marci@75
   176
/*
marci@243
   177
  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
marci@49
   178
    std::cout << node_name.get(i) << ": ";
marci@49
   179
    std::cout << "out edges: ";
marci@243
   180
    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   181
      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49
   182
    std::cout << "in edges: ";
marci@243
   183
    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   184
      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49
   185
    std::cout << std::endl;
marci@49
   186
  }
marci@9
   187
  
marci@243
   188
  for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
marci@60
   189
    std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
marci@60
   190
  }
marci@75
   191
*/
marci@49
   192
  /*
marci@243
   193
  while (flowG.valid(flowG.first<EdgeIt>())) {
marci@243
   194
    flowG.deleteEdge(flowG.first<EdgeIt>());
marci@243
   195
    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
marci@49
   196
      std::cout << node_name.get(i) << ": ";
marci@49
   197
      std::cout << "out edges: ";
marci@243
   198
      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   199
	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49
   200
      std::cout << "in edges: ";
marci@243
   201
      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   202
	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49
   203
      std::cout << std::endl;
marci@49
   204
    }
marci@49
   205
  }
marci@9
   206
  
marci@243
   207
  while (flowG.valid(flowG.first<NodeIt>())) {
marci@243
   208
    flowG.deleteNode(flowG.first<NodeIt>());
marci@243
   209
    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) { 
marci@49
   210
      std::cout << node_name.get(i) << ": ";
marci@49
   211
      std::cout << "out edges: ";
marci@243
   212
      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   213
	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49
   214
      std::cout << "in edges: ";
marci@243
   215
      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j)) 
marci@49
   216
	std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
marci@49
   217
      std::cout << std::endl;
marci@49
   218
    }
marci@49
   219
  }
marci@49
   220
  */
marci@49
   221
marci@75
   222
  //std::cout << std::endl;
marci@60
   223
marci@9
   224
marci@75
   225
  {
marci@75
   226
    ListGraph::EdgeMap<int> flow(flowG, 0);
marci@75
   227
    MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, s, t, flow, cap);
marci@133
   228
    /*
marci@133
   229
    max_flow_test.augmentOnBlockingFlow<ListGraph>();
marci@243
   230
    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
marci@133
   231
      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
marci@133
   232
    }
marci@133
   233
    std::cout<<std::endl;
marci@133
   234
    max_flow_test.augmentOnBlockingFlow<ListGraph>();
marci@243
   235
    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
marci@133
   236
      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
marci@133
   237
    }
marci@133
   238
    std::cout<<std::endl;*/
marci@168
   239
    //max_flow_test.run();
marci@75
   240
    
marci@168
   241
    //std::cout << "maximum flow: "<< std::endl;
marci@168
   242
    while (max_flow_test.augmentOnShortestPath()) {
marci@243
   243
      for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
marci@168
   244
	std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
marci@168
   245
      }
marci@168
   246
      std::cout<<std::endl;
marci@75
   247
    }
marci@75
   248
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@60
   249
  }
marci@155
   250
/*
marci@75
   251
  {
marci@243
   252
    std::list<Node> S;
marci@75
   253
    S.push_back(s); S.push_back(v3);
marci@243
   254
    std::list<Node> T;
marci@75
   255
    T.push_back(t);
marci@75
   256
marci@75
   257
    ListGraph::EdgeMap<int> flow(flowG, 0);
marci@75
   258
    MaxFlow2<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(flowG, S, T, flow, cap);
marci@75
   259
    max_flow_test.run();
marci@75
   260
    
marci@75
   261
    std::cout << "maximum flow: "<< std::endl;
marci@243
   262
    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) { 
marci@75
   263
      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
marci@75
   264
    }
marci@75
   265
    std::cout<<std::endl;
marci@75
   266
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@75
   267
  }
marci@155
   268
*/
marci@9
   269
  return 0;
marci@9
   270
}