COIN-OR::LEMON - Graph Library

Changeset 165:2cd447b0bd3a in glemon-0.x for dijkstrabox.cc


Ignore:
Timestamp:
10/13/06 17:31:58 (14 years ago)
Author:
Hegyi Péter
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/glemon/trunk@2990
Message:

Suurballe algorithm is implemented in glemon.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • dijkstrabox.cc

    r163 r165  
    11#include <dijkstrabox.h>
     2#include <lemon/dijkstra.h>
     3#include <lemon/suurballe.h>
     4#include <lemon/path.h>
    25
    36enum {INPUT, OUTPUT, MAP_NUM};
     
    69{
    710  init(t);
     11}
     12   
     13SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
     14{
     15  Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
     16  num_set = new Gtk::SpinButton(*adjustment, 5,0);
     17
     18  Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
     19//   hbox.pack_start(*label);
     20//   hbox.pack_start(*num_set);
     21//   hbox.show_all_children();
     22
     23  table.attach(*label, 0,1,2,3);
     24  table.attach(*num_set, 1,2,2,3);
     25
     26
     27//   pack_start(hbox);
    828}
    929   
     
    1939    {
    2040      const Graph &g=mapstorage->graph;
    21 
    22       Graph::EdgeMap<double> * inputmap=
    23         (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
    24       Graph::EdgeMap<double> * outputmap=
    25         (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
    26 
    2741      Node from, to;
    28       int assigned=0;
     42
     43      get_from_to(from, to, (Graph&)g);
     44
    2945      std::ostringstream o;
    3046
    31       //zero out output map
    32       for (EdgeIt i(g); i!=INVALID; ++i)
    33         {
    34           (*outputmap)[i]=0;
    35         }
    36 
    37       for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
    38         {
    39           std::ostringstream text;
    40           text << (*((mapstorage->nodemap_storage)["label"]))[i];
    41           if(!(text.str().compare(source.get_active_text())))
    42             {
    43               from=i;
    44               assigned++;
    45             }
    46           if(!(text.str().compare(target.get_active_text())))
    47             {
    48               to=i;
    49               assigned++;
    50             }
    51         }
    5247      if(!(from==to))
    5348        {
     49          Graph::EdgeMap<double> * inputmap=
     50            (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
     51          Graph::EdgeMap<double> * outputmap=
     52            (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
     53
     54          //zero out output map
     55          for (EdgeIt i(g); i!=INVALID; ++i)
     56            {
     57              (*outputmap)[i]=0;
     58            }
     59         
    5460          Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
    5561          dijkstra.run(from, to);
    56 
     62         
    5763          if(dijkstra.reached(to))
    5864            {
     
    7480            }
    7581          resultlabel.set_text(o.str());
    76 
     82         
    7783          mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
    78         }
    79       //   mapstorage->changeActiveMap(true, E_COLOR,
    80       //                              (edgemapcbts[OUTPUT])->get_active_text());
    81       //   mapstorage->changeActiveMap(true, E_TEXT,
    82       //                              (edgemapcbts[INPUT])->get_active_text());
     84          //   mapstorage->changeActiveMap(true, E_COLOR,
     85          //                          (edgemapcbts[OUTPUT])->get_active_text());
     86          //   mapstorage->changeActiveMap(true, E_TEXT,
     87          //                          (edgemapcbts[INPUT])->get_active_text());
     88        }
     89    }
     90}
     91
     92void SuurballeBox::run()
     93{
     94  if(
     95     tabcbt.get_active_text()!="" &&
     96     (edgemapcbts[INPUT])->get_active_text()!="" &&
     97     (edgemapcbts[OUTPUT])->get_active_text()!="" &&
     98     source.get_active_text()!="" &&
     99     target.get_active_text()!=""
     100     )
     101    {
     102      const Graph &g=mapstorage->graph;
     103      Node from, to;
     104
     105      get_from_to(from, to, (Graph&)g);
     106
     107      std::ostringstream o;
     108
     109      if(!(from==to))
     110        {
     111          Graph::EdgeMap<double> * inputmap=
     112            (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
     113          Graph::EdgeMap<double> * outputmap=
     114            (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
     115
     116          //zero out output map
     117          for (EdgeIt i(g); i!=INVALID; ++i)
     118            {
     119              (*outputmap)[i]=0;
     120            }
     121         
     122          Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
     123         
     124          int found=sb.run(num_set->get_value_as_int());
     125          if(found)
     126            {
     127              for(int j=0;j<found;j++)
     128                {
     129                  DirPath<Graph> path(g);
     130                  sb.getPath(path, j);
     131                  for(int k=0;k<path.length();k++)
     132                    {
     133                      DirPath<Graph>::EdgeIt ei;
     134                      path.nth(ei,k);
     135                      (*outputmap)[ei]=j+1;
     136                    }
     137                }
     138              o << "Result: found " << found << " paths between ";
     139              o << source.get_active_text() << " and " << target.get_active_text();
     140            }
     141          else
     142            {
     143              o << "Result: failed to find shortest path between ";
     144              o << source.get_active_text() << " and " << target.get_active_text();
     145            }
     146          resultlabel.set_text(o.str());
     147         
     148          mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
     149          //   mapstorage->changeActiveMap(true, E_COLOR,
     150          //                          (edgemapcbts[OUTPUT])->get_active_text());
     151          //   mapstorage->changeActiveMap(true, E_TEXT,
     152          //                          (edgemapcbts[INPUT])->get_active_text());
     153        }
    83154    }
    84155}
     
    108179}
    109180
     181void SuurballeBox::build_box()
     182{
     183}
     184
    110185void DijkstraBox::maplists_updated()
    111186{
     
    124199    }
    125200}
     201
     202void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
     203{
     204  int assigned=0;
     205  for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
     206    {
     207      std::ostringstream text;
     208      text << (*((mapstorage->nodemap_storage)["label"]))[i];
     209      if(!(text.str().compare(source.get_active_text())))
     210        {
     211          from=i;
     212          assigned++;
     213        }
     214      if(!(text.str().compare(target.get_active_text())))
     215        {
     216          to=i;
     217          assigned++;
     218        }
     219    }
     220}
Note: See TracChangeset for help on using the changeset viewer.