COIN-OR::LEMON - Graph Library

Changeset 160:f1a7005e9dff in lemon-0.x for src


Ignore:
Timestamp:
03/09/04 16:53:19 (21 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@226
Message:

* empty log message *

Location:
src/work/jacint
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/dijkstra.cc

    r159 r160  
    11#include <iostream>
    2 #include <vector>
    3 #include <string>
     2#include <fstream>
    43
    54#include <list_graph.hh>
     5#include <dimacs.hh>
    66#include <dijkstra.h>
     7#include <time_measure.h>
    78
    89using namespace hugo;
    910
    10 int main (int, char*[])
    11 {
     11int main(int, char **) {
    1212  typedef ListGraph::NodeIt NodeIt;
    13   typedef ListGraph::EdgeIt EdgeIt;
    14   typedef ListGraph::EachNodeIt EachNodeIt;
    1513  typedef ListGraph::EachEdgeIt EachEdgeIt;
    16   typedef ListGraph::OutEdgeIt OutEdgeIt;
    17   typedef ListGraph::InEdgeIt InEdgeIt;
     14
     15  ListGraph G;
     16  NodeIt s, t;
     17  ListGraph::EdgeMap<int> cap(G);
     18  readDimacsMaxFlow(std::cin, G, s, t, cap);
     19
     20  std::cout << "dijkstra demo ..." << std::endl;
    1821 
    19   ListGraph flow_test;
     22  double pre_time=currTime();
     23    Dijkstra<ListGraph, int> dijkstra_test(G, s, cap);
     24  double post_time=currTime();
     25   
     26  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
    2027 
    21   /*    //Ahuja könyv példája, maxflowvalue=13
    22   NodeIt s=flow_test.addNode();
    23   NodeIt v1=flow_test.addNode();
    24   NodeIt v2=flow_test.addNode();
    25   NodeIt v3=flow_test.addNode();
    26   NodeIt v4=flow_test.addNode();
    27   NodeIt v5=flow_test.addNode();
    28   NodeIt t=flow_test.addNode();
    29  
    30   ListGraph::NodeMap<std::string> Node_name(flow_test);
    31   Node_name.set(s, "s");
    32   Node_name.set(v1, "v1");
    33   Node_name.set(v2, "v2");
    34   Node_name.set(v3, "v3");
    35   Node_name.set(v4, "v4");
    36   Node_name.set(v5, "v5");
    37   Node_name.set(t, "t");
     28  EachEdgeIt e;
    3829
    39   EdgeIt s_v1=flow_test.addEdge(s, v1);
    40   EdgeIt s_v2=flow_test.addEdge(s, v2);
    41   EdgeIt s_v3=flow_test.addEdge(s, v3);
    42   EdgeIt v2_v4=flow_test.addEdge(v2, v4);
    43   EdgeIt v2_v5=flow_test.addEdge(v2, v5);
    44   EdgeIt v3_v5=flow_test.addEdge(v3, v5);
    45   EdgeIt v4_t=flow_test.addEdge(v4, t);
    46   EdgeIt v5_t=flow_test.addEdge(v5, t);
    47   EdgeIt v2_s=flow_test.addEdge(v2, s);
    48  
    49    ListGraph::EdgeMap<int> cap(flow_test); 
    50   cap.set(s_v1, 0);
    51   cap.set(s_v2, 10);
    52   cap.set(s_v3, 10);
    53   cap.set(v2_v4, 5);
    54   cap.set(v2_v5, 8);
    55   cap.set(v3_v5, 5);
    56   cap.set(v4_t, 8);
    57   cap.set(v5_t, 8);
    58   cap.set(v2_s, 0);
    59   */
    60 
    61  
    62   //Marci példája, maxflowvalue=23
    63     NodeIt s=flow_test.addNode();
    64   NodeIt v1=flow_test.addNode();
    65   NodeIt v2=flow_test.addNode();
    66   NodeIt v3=flow_test.addNode();
    67   NodeIt v4=flow_test.addNode();
    68   NodeIt t=flow_test.addNode();
    69   NodeIt z=flow_test.addNode();
    70 
    71  
    72    ListGraph::NodeMap<std::string> Node_name(flow_test);
    73   Node_name.set(s, "s");
    74   Node_name.set(v1, "v1");
    75   Node_name.set(v2, "v2");
    76   Node_name.set(v3, "v3");
    77   Node_name.set(v4, "v4");
    78   Node_name.set(t, "t");
    79   Node_name.set(z, "z");
    80 
    81   EdgeIt s_v1=flow_test.addEdge(s, v1);
    82   EdgeIt s_v2=flow_test.addEdge(s, v2);
    83   EdgeIt v1_v2=flow_test.addEdge(v1, v2);
    84   EdgeIt v2_v1=flow_test.addEdge(v2, v1);
    85   EdgeIt v1_v3=flow_test.addEdge(v1, v3);
    86   EdgeIt v3_v2=flow_test.addEdge(v3, v2);
    87   EdgeIt v2_v4=flow_test.addEdge(v2, v4);
    88   EdgeIt v4_v3=flow_test.addEdge(v4, v3);
    89   EdgeIt v3_t=flow_test.addEdge(v3, t);
    90   EdgeIt v4_t=flow_test.addEdge(v4, t);
    91   EdgeIt v3_v3=flow_test.addEdge(v3, v3);
    92   EdgeIt s_z=flow_test.addEdge(s, z);
    93   //  EdgeIt v2_s=flow_test.addEdge(v2, s);
    94  
    95 
    96 
    97    ListGraph::EdgeMap<int> cap(flow_test); 
    98   cap.set(s_v1, 16);
    99   cap.set(s_v2, 13);
    100   cap.set(v1_v2, 10);
    101   cap.set(v2_v1, 4);
    102   cap.set(v1_v3, 12);
    103   cap.set(v3_v2, 9);
    104   cap.set(v2_v4, 14);
    105   cap.set(v4_v3, 7);
    106   cap.set(v3_t, 20);
    107   cap.set(v4_t, 4);
    108   cap.set(v3_v3, 4);
    109   cap.set(s_z, 4);
    110   //  cap.set(v2_s, 0);
    111 
    112 
    113 
    114   //pelda 3, maxflowvalue=4
    115   /*      NodeIt s=flow_test.addNode();
    116   NodeIt v1=flow_test.addNode();
    117   NodeIt v2=flow_test.addNode();
    118   NodeIt t=flow_test.addNode();
    119   NodeIt w=flow_test.addNode();
    120  
    121   NodeMap<ListGraph, std::string> Node_name(flow_test);
    122   Node_name.set(s, "s");
    123   Node_name.set(v1, "v1");
    124   Node_name.set(v2, "v2");
    125   Node_name.set(t, "t");
    126   Node_name.set(w, "w");
    127 
    128   EdgeIt s_v1=flow_test.addEdge(s, v1);
    129   EdgeIt v1_v2=flow_test.addEdge(v1, v2);
    130   EdgeIt v2_t=flow_test.addEdge(v2, t);
    131   EdgeIt v1_v1=flow_test.addEdge(v1, v1);
    132   EdgeIt s_w=flow_test.addEdge(s, w);
    133 
    134 
    135   EdgeMap<ListGraph, int> cap(flow_test);
    136    
    137   cap.set(s_v1, 16);
    138   cap.set(v1_v2, 10);
    139   cap.set(v2_t, 4);
    140   cap.set(v1_v1, 3);
    141   cap.set(s_w, 5);
    142   */
    143  
    144 
    145 
    146   /*
    147   std::cout << "Testing reverse_bfs..." << std::endl;
    148  
    149   reverse_bfs<ListGraph> bfs_test(flow_test, t);
    150 
    151   bfs_test.run();
    152 
    153   for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
    154     std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
    155     }
    156 
    157   */
    158 
    159 
    160   /*
    161   std::cout << "Testing preflow_push_hl..." << std::endl;
    162  
    163   preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
    164 
    165   preflow_push_test.run();
    166 
    167   std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
    168 
    169   std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
    170 
    171    ListGraph::EdgeMap<int> flow=preflow_push_test.allflow(); 
    172   for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
    173     std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
    174     }
    175 
    176   std::cout << "A minimum cut: " <<std::endl; 
    177    ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
    178 
    179   for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
    180       if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
    181     }
    182  
    183   std::cout<<"\n\n"<<std::endl;
    184 
    185 
    186 
    187 
    188   std::cout << "Testing preflow_push_max_flow..." << std::endl;
    189  
    190   preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
    191 
    192   max_flow_test.run();
    193 
    194   std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
    195 
    196   std::cout << "A minimum cut: " <<std::endl; 
    197    ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
    198 
    199   for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
    200     if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
     30  for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
     31    NodeIt u=G.tail(e);
     32    NodeIt v=G.head(e);
     33    assert ( dijkstra_test.dist(v) - dijkstra_test.dist(u) <= cap.get(e) );
    20134  }
    202  
    203   std::cout << std::endl <<std::endl;
    204   */
    205 
    206  
    207     std::cout << "Testing dijkstra..." << std::endl;
    208  
    209     NodeIt root=s;
    210 
    211     Dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
    212 
    213     dijkstra_test.run();
    214 
    215     EachNodeIt w;
    216 
    217     for ( flow_test.getFirst(w); flow_test.valid(w) ; flow_test.next(w) ) {
    218       if (dijkstra_test.reach(w)) {
    219       std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
    220       if (dijkstra_test.pred(w).valid()) {
    221       std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;
    222       } else {
    223        std::cout <<", this is the root."<<std::endl; }
    224      
    225       } else {
    226         std::cout << w << " is not reachable from " << root <<std::endl;
    227       }
    228     }
    229 
    230 
    23135
    23236  return 0;
    23337}
    234 
    235 
    236 
    237 
    238 
    239 
    240 
    241 
    242 
  • src/work/jacint/dijkstra.h

    r159 r160  
    8282          OutEdgeIt e;
    8383          for( G.getFirst(e,v); G.valid(e); G.next(e)) {
    84             NodeIt w=G.head(e);
     84            NodeIt w=G.bNode(e);
    8585           
    8686            if ( !scanned.get(w) ) {
Note: See TracChangeset for help on using the changeset viewer.