COIN-OR::LEMON - Graph Library

Changeset 49:f00a4f7e2149 in lemon-0.x for src/work/marci_graph_demo.cc


Ignore:
Timestamp:
01/30/04 15:55:10 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@64
Message:

marci_graph_demo in new concept

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_graph_demo.cc

    r19 r49  
    33#include <string>
    44
    5 #include <marci_list_graph.hh>
    6 #include <marci_property_vector.hh>
    7 #include <marci_bfs.hh>
    8 #include <marci_max_flow.hh>
     5#include <list_graph.hh>
     6#include <bfs_iterator.hh>
     7#include <edmonds_karp.hh>
    98
    109using namespace marci;
     
    1211int main (int, char*[])
    1312{
    14   typedef list_graph::node_iterator node_iterator;
    15   typedef list_graph::edge_iterator edge_iterator;
    16   typedef list_graph::each_node_iterator each_node_iterator;
    17   typedef list_graph::each_edge_iterator each_edge_iterator;
    18   typedef list_graph::out_edge_iterator out_edge_iterator;
    19   typedef list_graph::in_edge_iterator in_edge_iterator;
    20   typedef list_graph::sym_edge_iterator sym_edge_iterator;
    21   list_graph G;
    22   std::vector<node_iterator> vector_of_node_iterators;
    23   for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
     13  typedef ListGraph::NodeIt NodeIt;
     14  typedef ListGraph::EdgeIt EdgeIt;
     15  typedef ListGraph::EachNodeIt EachNodeIt;
     16  typedef ListGraph::EachEdgeIt EachEdgeIt;
     17  typedef ListGraph::OutEdgeIt OutEdgeIt;
     18  typedef ListGraph::InEdgeIt InEdgeIt;
     19  typedef ListGraph::SymEdgeIt SymEdgeIt;
     20  ListGraph G;
     21  std::vector<NodeIt> vector_of_NodeIts;
     22  for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
    2423  for(int i=0; i!=8; ++i)
    25     for(int j=0; j!=8; ++j) {
    26       if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);
    27     } 
     24    for(int j=0; j!=8; ++j)
     25      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
    2826
    2927  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;
    30   std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
    31 
    32   for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     28  std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
     29
     30  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
    3331    std::cout << "node " << G.id(i) << std::endl;
    34     std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
    35     for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
     32    std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
     33    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
    3634      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
    3735    }
     
    3937
    4038    std::cout<< " ";
    41     for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
    42       std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
    43     std::cout<<std::endl;
    44 
    45     std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
    46     for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
     39    for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
     40      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
     41    std::cout<<std::endl;
     42
     43    std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
     44    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
    4745      std::cout << j << " "; }
    4846    std::cout << std::endl;
    4947
    5048    std::cout<< " ";
    51     for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
    52       std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
    53     std::cout<<std::endl;
    54 
    55     std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
    56     for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
     49    for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
     50      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
     51    std::cout<<std::endl;
     52
     53    std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
     54    for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
    5755      std::cout << j << " "; }
    5856    std::cout<<std::endl;
    5957
    6058    std::cout<< " ";
    61     for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
    62       std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
     59    for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
     60      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    6361    std::cout<<std::endl;
    6462  }
    6563
    6664  std::cout << "all edges: ";
    67   for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
     65  for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
    6866    std::cout << i << " ";
    6967  }
     
    7169
    7270  std::cout << "node property array test" << std::endl;
    73   node_property_vector<list_graph, int> my_property_vector(G);
    74   each_node_iterator v;
    75   G.get_first(v);
    76   my_property_vector.put(v, 42);
    77   my_property_vector.put(++G.first_node(), 314);
    78   my_property_vector.put(++++G.first_node(), 1956);
    79   my_property_vector.put(vector_of_node_iterators[3], 1989);
    80   my_property_vector.put(vector_of_node_iterators[4], 2003);
    81   my_property_vector.put(vector_of_node_iterators[7], 1978);
     71  ListGraph::NodeMap<int> my_property_vector(G);
     72  EachNodeIt v;
     73  G.getFirst(v);
     74  my_property_vector.set(v, 42);
     75  my_property_vector.set(++G.first<EachNodeIt>(), 314);
     76  my_property_vector.set(++++G.first<EachNodeIt>(), 1956);
     77  my_property_vector.set(vector_of_NodeIts[3], 1989);
     78  my_property_vector.set(vector_of_NodeIts[4], 2003);
     79  my_property_vector.set(vector_of_NodeIts[7], 1978);
    8280  std::cout << "some node property values..." << std::endl;
    83   for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     81  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
    8482    std::cout << my_property_vector.get(i) << std::endl;
    8583  }
    8684  int _i=1;
    8785  int _ii=1;
    88   edge_property_vector<list_graph, int> my_edge_property(G);
    89   for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
    90     my_edge_property.put(i, _i);
     86  ListGraph::EdgeMap<int> my_edge_property(G);
     87  for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
     88    my_edge_property.set(i, _i);
    9189    _i*=_ii; ++_ii;
    9290  }
    9391
    9492  std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
    95   for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
     93  for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
    9694    std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
    9795  }
    9896  std::cout << std::endl;
    9997
    100   //std::cout << "the same for inedges of the nodes..." << std::endl;
    101   //k=0;
    102   //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
    103   //  for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
    104   //    std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
    105   //  }
    106   //  std::cout << std::endl;
    107   //}
    108 
    10998  std::cout << "bfs from the first node" << std::endl;
    110   bfs<list_graph> bfs_test(G, G.first_node());
     99  bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
    111100  bfs_test.run();
    112101  std::cout << "reached: ";
    113   for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     102  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
    114103    std::cout << bfs_test.reached.get(i) << " ";
    115104  }
    116105  std::cout<<std::endl;
    117106  std::cout << "dist: ";
    118   for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
     107  for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
    119108    std::cout << bfs_test.dist.get(i) << " ";
    120109  }
     
    123112
    124113  std::cout << "augmenting path flow algorithm test..." << std::endl;
    125   list_graph flow_test;
    126 
    127   node_iterator s=flow_test.add_node();
    128   node_iterator v1=flow_test.add_node();
    129   node_iterator v2=flow_test.add_node();
    130   node_iterator v3=flow_test.add_node();
    131   node_iterator v4=flow_test.add_node();
    132   node_iterator t=flow_test.add_node();
     114  ListGraph flowG;
     115
     116  NodeIt s=flowG.addNode();
     117  NodeIt v1=flowG.addNode();
     118  NodeIt v2=flowG.addNode();
     119  NodeIt v3=flowG.addNode();
     120  NodeIt v4=flowG.addNode();
     121  NodeIt t=flowG.addNode();
    133122 
    134   node_property_vector<list_graph, std::string> node_name(flow_test);
    135   node_name.put(s, "s");
    136   node_name.put(v1, "v1");
    137   node_name.put(v2, "v2");
    138   node_name.put(v3, "v3");
    139   node_name.put(v4, "v4");
    140   node_name.put(t, "t");
    141 
    142   edge_iterator s_v1=flow_test.add_edge(s, v1);
    143   edge_iterator s_v2=flow_test.add_edge(s, v2);
    144   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
    145   edge_iterator v2_v1=flow_test.add_edge(v2, v1);
    146   edge_iterator v1_v3=flow_test.add_edge(v1, v3);
    147   edge_iterator v3_v2=flow_test.add_edge(v3, v2);
    148   edge_iterator v2_v4=flow_test.add_edge(v2, v4);
    149   edge_iterator v4_v3=flow_test.add_edge(v4, v3);
    150   edge_iterator v3_t=flow_test.add_edge(v3, t);
    151   edge_iterator v4_t=flow_test.add_edge(v4, t);
    152 
    153   edge_property_vector<list_graph, int> cap(flow_test);
    154 
    155   cap.put(s_v1, 16);
    156   cap.put(s_v2, 13);
    157   cap.put(v1_v2, 10);
    158   cap.put(v2_v1, 4);
    159   cap.put(v1_v3, 12);
    160   cap.put(v3_v2, 9);
    161   cap.put(v2_v4, 14);
    162   cap.put(v4_v3, 7);
    163   cap.put(v3_t, 20);
    164   cap.put(v4_t, 4);
    165 
    166   std::cout << "on directed graph graph" << std::endl; //<< flow_test;
     123  ListGraph::NodeMap<std::string> node_name(flowG);
     124  node_name.set(s, "s");
     125  node_name.set(v1, "v1");
     126  node_name.set(v2, "v2");
     127  node_name.set(v3, "v3");
     128  node_name.set(v4, "v4");
     129  node_name.set(t, "t");
     130
     131  EdgeIt s_v1=flowG.addEdge(s, v1);
     132  EdgeIt s_v2=flowG.addEdge(s, v2);
     133  EdgeIt v1_v2=flowG.addEdge(v1, v2);
     134  EdgeIt v2_v1=flowG.addEdge(v2, v1);
     135  EdgeIt v1_v3=flowG.addEdge(v1, v3);
     136  EdgeIt v3_v2=flowG.addEdge(v3, v2);
     137  EdgeIt v2_v4=flowG.addEdge(v2, v4);
     138  EdgeIt v4_v3=flowG.addEdge(v4, v3);
     139  EdgeIt v3_t=flowG.addEdge(v3, t);
     140  EdgeIt v4_t=flowG.addEdge(v4, t);
     141
     142  ListGraph::EdgeMap<int> cap(flowG);
     143
     144  cap.set(s_v1, 16);
     145  cap.set(s_v2, 13);
     146  cap.set(v1_v2, 10);
     147  cap.set(v2_v1, 4);
     148  cap.set(v1_v3, 12);
     149  cap.set(v3_v2, 9);
     150  cap.set(v2_v4, 14);
     151  cap.set(v4_v3, 7);
     152  cap.set(v3_t, 20);
     153  cap.set(v4_t, 4);
     154
     155  std::cout << "on directed graph graph" << std::endl; //<< flowG;
    167156  std::cout << "names and capacity values" << std::endl;
    168   for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
     157  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
    169158    std::cout << node_name.get(i) << ": ";
    170159    std::cout << "out edges: ";
    171     for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
    172       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
     160    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     161      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    173162    std::cout << "in edges: ";
    174     for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
    175       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
     163    for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     164      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    176165    std::cout << std::endl;
    177166  }
    178167
     168  //flowG.setTail(v3_t, v2);
     169  //flowG.setHead(v3_t, s);
     170
     171  for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     172    std::cout << node_name.get(i) << ": ";
     173    std::cout << "out edges: ";
     174    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     175      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     176    std::cout << "in edges: ";
     177    for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     178      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     179    std::cout << std::endl;
     180  }
    179181 
    180   //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
    181   //  std::cout << i << " ";
    182   //}
     182
     183  /*
     184  while (flowG.first<EachEdgeIt>().valid()) {
     185    flowG.deleteEdge(flowG.first<EachEdgeIt>());
     186    for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     187      std::cout << node_name.get(i) << ": ";
     188      std::cout << "out edges: ";
     189      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     190        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     191      std::cout << "in edges: ";
     192      for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     193        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     194      std::cout << std::endl;
     195    }
     196  }
    183197 
    184   max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);
     198  while (flowG.first<EachNodeIt>().valid()) {
     199    flowG.deleteNode(flowG.first<EachNodeIt>());
     200    for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     201      std::cout << node_name.get(i) << ": ";
     202      std::cout << "out edges: ";
     203      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     204        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     205      std::cout << "in edges: ";
     206      for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     207        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
     208      std::cout << std::endl;
     209    }
     210  }
     211  */
     212
     213  //ListGraph::EdgeMap<int> flow(flowG, 0);
     214  //ResGraph<ListGraph, int> res_graph(flowG, cap, flow);
     215  max_flow_type<ListGraph, int> max_flow_test(flowG, s, t, cap);
    185216  max_flow_test.run();
    186217
Note: See TracChangeset for help on using the changeset viewer.