src/work/athos/suurballe.cc
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 310 76c005b15354
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
     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 }