COIN-OR::LEMON - Graph Library

Changeset 243:a85fd87460e3 in lemon-0.x for src/work/marci_graph_demo.cc


Ignore:
Timestamp:
03/25/04 10:42:59 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@342
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci_graph_demo.cc

    r168 r243  
    33#include <string>
    44
    5 #include <list_graph.hh>
    6 #include <bfs_iterator.hh>
    7 #include <edmonds_karp.hh>
     5#include <list_graph.h>
     6#include <bfs_iterator.h>
     7#include <edmonds_karp.h>
    88
    99using namespace hugo;
     
    1111int main (int, char*[])
    1212{
     13  typedef ListGraph::Node Node;
     14  typedef ListGraph::Edge Edge;
    1315  typedef ListGraph::NodeIt NodeIt;
    1416  typedef ListGraph::EdgeIt EdgeIt;
    15   typedef ListGraph::EachNodeIt EachNodeIt;
    16   typedef ListGraph::EachEdgeIt EachEdgeIt;
    1717  typedef ListGraph::OutEdgeIt OutEdgeIt;
    1818  typedef ListGraph::InEdgeIt InEdgeIt;
    1919  typedef ListGraph::SymEdgeIt SymEdgeIt;
    2020  ListGraph G;
    21   std::vector<NodeIt> vector_of_NodeIts;
    22   for(int i=0; i!=8; ++i) vector_of_NodeIts.push_back(G.addNode());
     21  std::vector<Node> vector_of_Nodes;
     22  for(int i=0; i!=8; ++i) vector_of_Nodes.push_back(G.addNode());
    2323  for(int i=0; i!=8; ++i)
    2424    for(int j=0; j!=8; ++j)
    25       if ((i<j)&&(i+j)%3) G.addEdge(vector_of_NodeIts[i], vector_of_NodeIts[j]);
     25      if ((i<j)&&(i+j)%3) G.addEdge(vector_of_Nodes[i], vector_of_Nodes[j]);
    2626
    2727  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;
    28   std::cout << "number of nodes: " << count(G.first<EachNodeIt>()) << std::endl;
    29 
    30   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     28  std::cout << "number of nodes: " << count(G.first<NodeIt>()) << std::endl;
     29
     30  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    3131    std::cout << "node " << G.id(i) << std::endl;
    3232    std::cout << " outdegree (OutEdgeIt): " << count(G.first<OutEdgeIt>(i)) << " ";
    33     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
     33    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
    3434      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
    3535    }
     
    3737
    3838    std::cout<< " ";
    39     for(OutEdgeIt j=G.first<OutEdgeIt>(i); j.valid(); ++j) {
     39    for(OutEdgeIt j=G.first<OutEdgeIt>(i); G.valid(j); G.next(j)) {
    4040      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    4141    std::cout<<std::endl;
    4242
    4343    std::cout << " indegree: (InEdgeIt) " << count(G.first<InEdgeIt>(i)) << " ";
    44     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
     44    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
    4545      std::cout << j << " "; }
    4646    std::cout << std::endl;
    4747
    4848    std::cout<< " ";
    49     for(InEdgeIt j=G.first<InEdgeIt>(i); j.valid(); ++j) {
     49    for(InEdgeIt j=G.first<InEdgeIt>(i); G.valid(j); G.next(j)) {
    5050      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    5151    std::cout<<std::endl;
    5252
    5353    std::cout << " degree: (SymEdgeIt) " << count(G.first<SymEdgeIt>(i)) << " ";
    54     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
     54    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
    5555      std::cout << j << " "; }
    5656    std::cout<<std::endl;
    5757
    5858    std::cout<< " ";
    59     for(SymEdgeIt j=G.first<SymEdgeIt>(i); j.valid(); ++j) {
     59    for(SymEdgeIt j=G.first<SymEdgeIt>(i); G.valid(j); G.next(j)) {
    6060      std::cout << G.aNode(j) << "->" << G.bNode(j) << " "; }
    6161    std::cout<<std::endl;
     
    6363
    6464  std::cout << "all edges: ";
    65   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
     65  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
    6666    std::cout << i << " ";
    6767  }
     
    7070  std::cout << "node property array test" << std::endl;
    7171  ListGraph::NodeMap<int> my_property_vector(G);
    72   EachNodeIt v;
    73   G.getFirst(v);
     72  NodeIt v;
     73  G.first(v);
    7474  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);
     75  my_property_vector.set(G.next(G.first<NodeIt>()), 314);
     76  my_property_vector.set(G.next(G.next(G.first<NodeIt>())), 1956);
     77  my_property_vector.set(vector_of_Nodes[3], 1989);
     78  my_property_vector.set(vector_of_Nodes[4], 2003);
     79  my_property_vector.set(vector_of_Nodes[7], 1978);
    8080  std::cout << "some node property values..." << std::endl;
    81   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     81  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    8282    std::cout << my_property_vector.get(i) << std::endl;
    8383  }
     
    8585  int _ii=1;
    8686  ListGraph::EdgeMap<int> my_edge_property(G);
    87   for(EachEdgeIt i=G.first<EachEdgeIt>(); i.valid(); ++i) {
     87  for(EdgeIt i=G.first<EdgeIt>(); G.valid(i); G.next(i)) {
    8888    my_edge_property.set(i, _i);
    8989    _i*=_ii; ++_ii;
     
    9191
    9292  std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
    93   for(EachEdgeIt j=G.first<EachEdgeIt>(); j.valid(); ++j) {
     93  for(EdgeIt j=G.first<EdgeIt>(); G.valid(j); G.next(j)) {
    9494    std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
    9595  }
     
    9797/*
    9898  std::cout << "bfs from the first node" << std::endl;
    99   bfs<ListGraph> bfs_test(G, G.first<EachNodeIt>());
     99  bfs<ListGraph> bfs_test(G, G.first<NodeIt>());
    100100  bfs_test.run();
    101101  std::cout << "reached: ";
    102   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     102  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    103103    std::cout << bfs_test.reached.get(i) << " ";
    104104  }
    105105  std::cout<<std::endl;
    106106  std::cout << "dist: ";
    107   for(EachNodeIt i=G.first<EachNodeIt>(); i.valid(); ++i) {
     107  for(NodeIt i=G.first<NodeIt>(); G.valid(i); G.next(i)) {
    108108    std::cout << bfs_test.dist.get(i) << " ";
    109109  }
     
    114114  ListGraph flowG;
    115115
    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();
     116  Node s=flowG.addNode();
     117  Node v1=flowG.addNode();
     118  Node v2=flowG.addNode();
     119  Node v3=flowG.addNode();
     120  Node v4=flowG.addNode();
     121  Node t=flowG.addNode();
    122122 
    123123  ListGraph::NodeMap<std::string> node_name(flowG);
     
    129129  node_name.set(t, "t");
    130130
    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);
     131  Edge s_v1=flowG.addEdge(s, v1);
     132  Edge s_v2=flowG.addEdge(s, v2);
     133  Edge v1_v2=flowG.addEdge(v1, v2);
     134  Edge v2_v1=flowG.addEdge(v2, v1);
     135  Edge v1_v3=flowG.addEdge(v1, v3);
     136  Edge v3_v2=flowG.addEdge(v3, v2);
     137  Edge v2_v4=flowG.addEdge(v2, v4);
     138  Edge v4_v3=flowG.addEdge(v4, v3);
     139  Edge v3_t=flowG.addEdge(v3, t);
     140  Edge v4_t=flowG.addEdge(v4, t);
    141141
    142142  ListGraph::EdgeMap<int> cap(flowG);
     
    155155  std::cout << "on directed graph graph" << std::endl; //<< flowG;
    156156  std::cout << "names and capacity values" << std::endl;
    157   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     157  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    158158    std::cout << node_name.get(i) << ": ";
    159159    std::cout << "out edges: ";
    160     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     160    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    161161      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    162162    std::cout << "in edges: ";
    163     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     163    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    164164      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    165165    std::cout << std::endl;
     
    175175  //flowG.setHead(v3_t, s);
    176176/*
    177   for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     177  for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    178178    std::cout << node_name.get(i) << ": ";
    179179    std::cout << "out edges: ";
    180     for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     180    for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    181181      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    182182    std::cout << "in edges: ";
    183     for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     183    for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    184184      std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    185185    std::cout << std::endl;
    186186  }
    187187 
    188   for(EachEdgeIt e=flowG.first<EachEdgeIt>(); e.valid(); ++e) {
     188  for(EdgeIt e=flowG.first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    189189    std::cout << node_name.get(flowG.tail(e)) << "-"<< cap.get(e) << "->" << node_name.get(flowG.head(e)) << " ";
    190190  }
    191191*/
    192192  /*
    193   while (flowG.first<EachEdgeIt>().valid()) {
    194     flowG.deleteEdge(flowG.first<EachEdgeIt>());
    195     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     193  while (flowG.valid(flowG.first<EdgeIt>())) {
     194    flowG.deleteEdge(flowG.first<EdgeIt>());
     195    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    196196      std::cout << node_name.get(i) << ": ";
    197197      std::cout << "out edges: ";
    198       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     198      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    199199        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    200200      std::cout << "in edges: ";
    201       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     201      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    202202        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    203203      std::cout << std::endl;
     
    205205  }
    206206 
    207   while (flowG.first<EachNodeIt>().valid()) {
    208     flowG.deleteNode(flowG.first<EachNodeIt>());
    209     for(EachNodeIt i=flowG.first<EachNodeIt>(); i.valid(); ++i) {
     207  while (flowG.valid(flowG.first<NodeIt>())) {
     208    flowG.deleteNode(flowG.first<NodeIt>());
     209    for(NodeIt i=flowG.first<NodeIt>(); flowG.valid(i); flowG.next(i)) {
    210210      std::cout << node_name.get(i) << ": ";
    211211      std::cout << "out edges: ";
    212       for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); j.valid(); ++j)
     212      for(OutEdgeIt j=flowG.first<OutEdgeIt>(i); flowG.valid(j); flowG.next(j))
    213213        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    214214      std::cout << "in edges: ";
    215       for(InEdgeIt j=flowG.first<InEdgeIt>(i); j.valid(); ++j)
     215      for(InEdgeIt j=flowG.first<InEdgeIt>(i); flowG.valid(j); flowG.next(j))
    216216        std::cout << node_name.get(flowG.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flowG.head(j)) << " ";
    217217      std::cout << std::endl;
     
    228228    /*
    229229    max_flow_test.augmentOnBlockingFlow<ListGraph>();
    230     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     230    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    231231      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    232232    }
    233233    std::cout<<std::endl;
    234234    max_flow_test.augmentOnBlockingFlow<ListGraph>();
    235     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     235    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    236236      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    237237    }
     
    241241    //std::cout << "maximum flow: "<< std::endl;
    242242    while (max_flow_test.augmentOnShortestPath()) {
    243       for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     243      for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    244244        std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    245245      }
     
    250250/*
    251251  {
    252     std::list<NodeIt> S;
     252    std::list<Node> S;
    253253    S.push_back(s); S.push_back(v3);
    254     std::list<NodeIt> T;
     254    std::list<Node> T;
    255255    T.push_back(t);
    256256
     
    260260   
    261261    std::cout << "maximum flow: "<< std::endl;
    262     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     262    for(EdgeIt e=flowG.template first<EdgeIt>(); flowG.valid(e); flowG.next(e)) {
    263263      std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    264264    }
Note: See TracChangeset for help on using the changeset viewer.