src/work/athos/suurballe.cc
author alpar
Sat, 17 Apr 2004 13:15:53 +0000
changeset 348 b63ea19e502e
parent 310 76c005b15354
child 921 818510fa3d99
permissions -rw-r--r--
A bool Edge Map with iterators that goes through the true or the false edges.
     1 // -*- c++ -*-
     2 //#include <iostream>
     3 //#include <vector>
     4 //#include <string>
     5 
     6 #include <list_graph.h>
     7 #include <minlengthpaths.h>
     8 
     9 using namespace hugo;
    10 
    11 
    12 int main()
    13 {
    14 
    15   
    16   typedef ListGraph::Node Node;
    17   typedef ListGraph::Edge Edge;
    18 
    19   ListGraph graph;
    20 
    21   /*
    22   //Marci példája
    23 
    24 
    25   NodeIt s=graph.addNode();
    26   NodeIt v1=graph.addNode();
    27   NodeIt v2=graph.addNode();
    28   NodeIt v3=graph.addNode();
    29   NodeIt v4=graph.addNode();
    30   NodeIt t=graph.addNode();
    31   
    32 
    33   EdgeIt s_v1=graph.addEdge(s, v1);
    34   EdgeIt s_v2=graph.addEdge(s, v2);
    35   EdgeIt v1_v2=graph.addEdge(v1, v2);
    36   EdgeIt v2_v1=graph.addEdge(v2, v1);
    37   EdgeIt v1_v3=graph.addEdge(v1, v3);
    38   EdgeIt v3_v2=graph.addEdge(v3, v2);
    39   EdgeIt v2_v4=graph.addEdge(v2, v4);
    40   EdgeIt v4_v3=graph.addEdge(v4, v3);
    41   EdgeIt v3_t=graph.addEdge(v3, t);
    42   EdgeIt v4_t=graph.addEdge(v4, t);
    43 
    44   ListGraph::EdgeMap<int> length(graph);
    45 
    46   length.set(s_v1, 16);
    47   length.set(s_v2, 13);
    48   length.set(v1_v2, 10);
    49   length.set(v2_v1, 4);
    50   length.set(v1_v3, 12);
    51   length.set(v3_v2, 9);
    52   length.set(v2_v4, 14);
    53   length.set(v4_v3, 7);
    54   length.set(v3_t, 20);
    55   length.set(v4_t, 4);
    56   */
    57 
    58 
    59   //Ahuja könyv példája
    60 
    61   Node s=graph.addNode();
    62   Node v2=graph.addNode();
    63   Node v3=graph.addNode();
    64   Node v4=graph.addNode();
    65   Node v5=graph.addNode();
    66   Node t=graph.addNode();
    67 
    68   Edge s_v2=graph.addEdge(s, v2);
    69   Edge s_v3=graph.addEdge(s, v3);
    70   Edge v2_v4=graph.addEdge(v2, v4);
    71   Edge v2_v5=graph.addEdge(v2, v5);
    72   Edge v3_v5=graph.addEdge(v3, v5);
    73   Edge v4_t=graph.addEdge(v4, t);
    74   Edge v5_t=graph.addEdge(v5, t);
    75   
    76   //Kis modositas
    77   //edge_iterator v2_s=graph.add_edge(v2, s);
    78 
    79   ListGraph::EdgeMap<int> length(graph);
    80 
    81   length.set(s_v2, 10);
    82   length.set(s_v3, 10);
    83   length.set(v2_v4, 5);
    84   length.set(v2_v5, 8);
    85   length.set(v3_v5, 5);
    86   length.set(v4_t, 8);
    87   length.set(v5_t, 8);
    88 
    89   //Kis modositas
    90   //length.put(v2_s, 100);
    91  
    92 
    93 
    94 
    95   /*Egyszerű példa
    96   NodeIt s=flow_test.add_node();
    97   NodeIt v1=flow_test.add_node();
    98   NodeIt v2=flow_test.add_node();
    99   NodeIt t=flow_test.add_node();
   100   
   101   node_property_vector<list_graph, std::string> node_name(flow_test);
   102   node_name.put(s, "s");
   103   node_name.put(v1, "v1");
   104   node_name.put(v2, "v2");
   105   node_name.put(t, "t");
   106 
   107   edge_iterator s_v1=flow_test.add_edge(s, v1);
   108   edge_iterator v1_v2=flow_test.add_edge(v1, v2);
   109   edge_iterator v2_t=flow_test.add_edge(v2, t);
   110 
   111   edge_property_vector<list_graph, int> length(flow_test); 
   112     
   113   length.put(s_v1, 16);
   114   length.put(v1_v2, 10);
   115   length.put(v2_t, 4);
   116   */
   117 
   118   std::cout << "Suurballe algorithm test..." << std::endl;
   119 
   120   
   121   int k=3;
   122   MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
   123     surb_test(graph, length);
   124   std::cout << surb_test.run(s,t,k) << std::endl;
   125 
   126 
   127   return 0;
   128 }