src/work/athos/dijkstra_demo.cc
changeset 762 511200bdb71f
child 921 818510fa3d99
equal deleted inserted replaced
-1:000000000000 0:c93919050f41
       
     1 #include <iostream>
       
     2 #include <string>
       
     3 
       
     4 #include "list_graph.hh"
       
     5 //#include "marci_property_vector.hh"
       
     6 #include <dijkstra_at.h>
       
     7 
       
     8 using namespace hugo;
       
     9 
       
    10 
       
    11 int main (int, char*[])
       
    12 {
       
    13 
       
    14   
       
    15   typedef ListGraph::NodeIt NodeIt;
       
    16   typedef ListGraph::EdgeIt EdgeIt;
       
    17   /*
       
    18   typedef ListGraph::EachNodeIt EachNodeIt;
       
    19   typedef ListGraph::EachEdgeIt EachEdgeIt;
       
    20   typedef ListGraph::OutEdgeIt OutEdgeIt;
       
    21   typedef ListGraph::InEdgeIt InEdgeIt;
       
    22   typedef ListGraph::SymEdgeIt SymEdgeIt;
       
    23   */
       
    24   ListGraph flowG;
       
    25 
       
    26   /*
       
    27   //Marci példája
       
    28 
       
    29 
       
    30   NodeIt s=flowG.addNode();
       
    31   NodeIt v1=flowG.addNode();
       
    32   NodeIt v2=flowG.addNode();
       
    33   NodeIt v3=flowG.addNode();
       
    34   NodeIt v4=flowG.addNode();
       
    35   NodeIt t=flowG.addNode();
       
    36   
       
    37 
       
    38   EdgeIt s_v1=flowG.addEdge(s, v1);
       
    39   EdgeIt s_v2=flowG.addEdge(s, v2);
       
    40   EdgeIt v1_v2=flowG.addEdge(v1, v2);
       
    41   EdgeIt v2_v1=flowG.addEdge(v2, v1);
       
    42   EdgeIt v1_v3=flowG.addEdge(v1, v3);
       
    43   EdgeIt v3_v2=flowG.addEdge(v3, v2);
       
    44   EdgeIt v2_v4=flowG.addEdge(v2, v4);
       
    45   EdgeIt v4_v3=flowG.addEdge(v4, v3);
       
    46   EdgeIt v3_t=flowG.addEdge(v3, t);
       
    47   EdgeIt v4_t=flowG.addEdge(v4, t);
       
    48 
       
    49   ListGraph::EdgeMap<int> cap(flowG);
       
    50 
       
    51   cap.set(s_v1, 16);
       
    52   cap.set(s_v2, 13);
       
    53   cap.set(v1_v2, 10);
       
    54   cap.set(v2_v1, 4);
       
    55   cap.set(v1_v3, 12);
       
    56   cap.set(v3_v2, 9);
       
    57   cap.set(v2_v4, 14);
       
    58   cap.set(v4_v3, 7);
       
    59   cap.set(v3_t, 20);
       
    60   cap.set(v4_t, 4);
       
    61   */
       
    62 
       
    63 
       
    64   //Ahuja könyv példája
       
    65 
       
    66   NodeIt s=flowG.addNode();
       
    67   NodeIt v2=flowG.addNode();
       
    68   NodeIt v3=flowG.addNode();
       
    69   NodeIt v4=flowG.addNode();
       
    70   NodeIt v5=flowG.addNode();
       
    71   NodeIt t=flowG.addNode();
       
    72 
       
    73   EdgeIt s_v2=flowG.addEdge(s, v2);
       
    74   EdgeIt s_v3=flowG.addEdge(s, v3);
       
    75   EdgeIt v2_v4=flowG.addEdge(v2, v4);
       
    76   EdgeIt v2_v5=flowG.addEdge(v2, v5);
       
    77   EdgeIt v3_v5=flowG.addEdge(v3, v5);
       
    78   EdgeIt v4_t=flowG.addEdge(v4, t);
       
    79   EdgeIt v5_t=flowG.addEdge(v5, t);
       
    80   
       
    81   //Kis modositas
       
    82   //edge_iterator v2_s=flowG.add_edge(v2, s);
       
    83 
       
    84   ListGraph::EdgeMap<int> cap(flowG);
       
    85 
       
    86   cap.set(s_v2, 10);
       
    87   cap.set(s_v3, 10);
       
    88   cap.set(v2_v4, 5);
       
    89   cap.set(v2_v5, 8);
       
    90   cap.set(v3_v5, 5);
       
    91   cap.set(v4_t, 8);
       
    92   cap.set(v5_t, 8);
       
    93 
       
    94   //Kis modositas
       
    95   //cap.put(v2_s, 100);
       
    96  
       
    97 
       
    98 
       
    99 
       
   100   /*Egyszerű példa
       
   101   NodeIt s=flow_test.add_node();
       
   102   NodeIt v1=flow_test.add_node();
       
   103   NodeIt v2=flow_test.add_node();
       
   104   NodeIt t=flow_test.add_node();
       
   105   
       
   106   node_property_vector<list_graph, std::string> node_name(flow_test);
       
   107   node_name.put(s, "s");
       
   108   node_name.put(v1, "v1");
       
   109   node_name.put(v2, "v2");
       
   110   node_name.put(t, "t");
       
   111 
       
   112   edge_iterator s_v1=flow_test.add_edge(s, v1);
       
   113   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
       
   114   edge_iterator v2_t=flow_test.add_edge(v2, t);
       
   115 
       
   116   edge_property_vector<list_graph, int> cap(flow_test); 
       
   117     
       
   118   cap.put(s_v1, 16);
       
   119   cap.put(v1_v2, 10);
       
   120   cap.put(v2_t, 4);
       
   121   */
       
   122 
       
   123   std::cout << "preflow-push algorithm test..." << std::endl;
       
   124 
       
   125   /*
       
   126   std::cout << "on directed graph graph" << std::endl; //<< flow_test;
       
   127   std::cout << "names and capacity values" << std::endl; 
       
   128   for(EachNodeIt i=flow_test.first_node(); i.valid(); ++i) { 
       
   129     std::cout << node_name.get(i) << ": ";
       
   130     std::cout << "out edges: ";
       
   131     for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) 
       
   132       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
       
   133     std::cout << "in edges: ";
       
   134     for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) 
       
   135       std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
       
   136     std::cout << std::endl;
       
   137   }
       
   138   */
       
   139   
       
   140   //for(each_NodeIt i=flow_test.first_node(); i.valid(); ++i) { 
       
   141   //  std::cout << i << " ";
       
   142   //}
       
   143   
       
   144   dijkstra_at<ListGraph, int> dijkstra_test(flowG, s, cap);
       
   145   //cout << preflow_push_test.run()<<endl;
       
   146 
       
   147   //cap.put(v5_t, 9);
       
   148   //cout << preflow_push_test.run()<<endl;
       
   149 
       
   150   return 0;
       
   151 }
       
   152 
       
   153 
       
   154 
       
   155 
       
   156 
       
   157 
       
   158 
       
   159 
       
   160