dijkstrabox.cc
author alpar
Tue, 07 Nov 2006 21:27:28 +0000
changeset 180 911c6ba0e3c8
parent 169 c223ffdbdb5c
child 188 c1c9fcf03e94
permissions -rw-r--r--
Bugfix + polishing
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2006
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <dijkstrabox.h>
    20 #include <lemon/dijkstra.h>
    21 #include <lemon/suurballe.h>
    22 #include <lemon/path.h>
    23 
    24 enum {INPUT, OUTPUT, MAP_NUM};
    25 
    26 DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
    27 {
    28   init(t);
    29 }
    30     
    31 SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
    32 {
    33   Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
    34   num_set = new Gtk::SpinButton(*adjustment, 5,0);
    35 
    36   Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
    37 //   hbox.pack_start(*label);
    38 //   hbox.pack_start(*num_set);
    39 //   hbox.show_all_children();
    40 
    41   table.attach(*label, 0,1,2,3);
    42   table.attach(*num_set, 1,2,2,3);
    43 
    44 
    45 //   pack_start(hbox);
    46 }
    47     
    48 void DijkstraBox::run()
    49 {
    50   if(
    51      tabcbt.get_active_text()!="" &&
    52      (edgemapcbts[INPUT])->get_active_text()!="" &&
    53      (edgemapcbts[OUTPUT])->get_active_text()!="" &&
    54      source.get_active_text()!="" &&
    55      target.get_active_text()!=""
    56      )
    57     {
    58       const Graph &g=mapstorage->graph;
    59       Node from, to;
    60 
    61       get_from_to(from, to, (Graph&)g);
    62 
    63       std::ostringstream o;
    64 
    65       if(!(from==to))
    66 	{
    67 	  Graph::EdgeMap<double> * inputmap=
    68 	    (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
    69 	  Graph::EdgeMap<double> * outputmap=
    70 	    (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
    71 
    72 	  //zero out output map
    73 	  for (EdgeIt i(g); i!=INVALID; ++i)
    74 	    {
    75 	      (*outputmap)[i]=0;
    76 	    }
    77 	  
    78 	  Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
    79 	  dijkstra.run(from, to);
    80 	  
    81 	  if(dijkstra.reached(to))
    82 	    {
    83 	      Node n=to;
    84 	      int length=0;
    85 	      while (n!=INVALID && n!=from)
    86 		{
    87 		  Edge e=dijkstra.predEdge(n);
    88 		  (*outputmap)[e]=1;
    89 		  n=dijkstra.predNode(n);
    90 		  length++;
    91 		}
    92 	      o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
    93 	    }
    94 	  else
    95 	    {
    96 	      o << "Result: failed to find shortest path between ";
    97 	      o << source.get_active_text() << " and " << target.get_active_text();
    98 	    }
    99 	  resultlabel.set_text(o.str());
   100 	  
   101 	  mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
   102 	  //   mapstorage->changeActiveMap(true, E_COLOR,
   103 	  // 			      (edgemapcbts[OUTPUT])->get_active_text());
   104 	  //   mapstorage->changeActiveMap(true, E_TEXT,
   105 	  // 			      (edgemapcbts[INPUT])->get_active_text());
   106 	}
   107     }
   108 }
   109 
   110 void SuurballeBox::run()
   111 {
   112   if(
   113      tabcbt.get_active_text()!="" &&
   114      (edgemapcbts[INPUT])->get_active_text()!="" &&
   115      (edgemapcbts[OUTPUT])->get_active_text()!="" &&
   116      source.get_active_text()!="" &&
   117      target.get_active_text()!=""
   118      )
   119     {
   120       const Graph &g=mapstorage->graph;
   121       Node from, to;
   122 
   123       get_from_to(from, to, (Graph&)g);
   124 
   125       std::ostringstream o;
   126 
   127       if(!(from==to))
   128 	{
   129 	  Graph::EdgeMap<double> * inputmap=
   130 	    (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
   131 	  Graph::EdgeMap<double> * outputmap=
   132 	    (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
   133 
   134 	  //zero out output map
   135 	  for (EdgeIt i(g); i!=INVALID; ++i)
   136 	    {
   137 	      (*outputmap)[i]=0;
   138 	    }
   139 	  
   140 	  Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
   141 	  
   142 	  int found=sb.run(num_set->get_value_as_int());
   143 	  if(found)
   144 	    {
   145 	      for(int j=0;j<found;j++)
   146 		{
   147 		  Path<Graph> path(g);
   148 		  sb.getPath(path, j);
   149 		  for(int k=0;k<path.length();k++)
   150 		    {
   151 		      Path<Graph>::EdgeIt ei;
   152 		      ei=path.nthEdge(k);
   153 		      (*outputmap)[ei]=j+1;
   154 		    }
   155 		}
   156 	      o << "Result: found " << found << " paths between ";
   157 	      o << source.get_active_text() << " and " << target.get_active_text();
   158 	    }
   159 	  else
   160 	    {
   161 	      o << "Result: failed to find shortest path between ";
   162 	      o << source.get_active_text() << " and " << target.get_active_text();
   163 	    }
   164 	  resultlabel.set_text(o.str());
   165 	  
   166 	  mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
   167 	  //   mapstorage->changeActiveMap(true, E_COLOR,
   168 	  // 			      (edgemapcbts[OUTPUT])->get_active_text());
   169 	  //   mapstorage->changeActiveMap(true, E_TEXT,
   170 	  // 			      (edgemapcbts[INPUT])->get_active_text());
   171 	}
   172     }
   173 }
   174     
   175 void DijkstraBox::build_box()
   176 {
   177   //if active tab is changed, labels of graph nodes had to be loaded into comboboxes
   178   //this can be done after the maps are loaded into ComboBoxes
   179   signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
   180 
   181   addMapSelector("Cost map: ", true);
   182   addMapSelector("Edges of path here: ", true);
   183 
   184   Gtk::Label * source_label=new Gtk::Label("Source: ");
   185   Gtk::Label * target_label=new Gtk::Label("Target: ");
   186 
   187   table.attach(*source_label, 0,1,0,1);
   188   table.attach(*target_label, 0,1,1,2);
   189   table.attach(source, 1,2,0,1);
   190   table.attach(target, 1,2,1,2);
   191 
   192 
   193   pack_start(table);
   194 
   195   resultlabel.set_text("Result: algorithm is not run yet.");
   196   pack_start(resultlabel);
   197 }
   198 
   199 void SuurballeBox::build_box()
   200 {
   201 }
   202 
   203 void DijkstraBox::maplists_updated()
   204 {
   205   if(tabcbt.get_active_text()!="")
   206     {
   207       source.clear();
   208       target.clear();
   209       const Graph &g=mapstorage->graph;
   210       for (NodeIt i(g); i!=INVALID; ++i)
   211 	{
   212 	  std::ostringstream text;
   213 	  text << (*((mapstorage->nodemap_storage)["label"]))[i];
   214 	  source.prepend_text(text.str());
   215 	  target.prepend_text(text.str());
   216 	}
   217     }
   218 }
   219 
   220 void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
   221 {
   222   int assigned=0;
   223   for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
   224     {
   225       std::ostringstream text;
   226       text << (*((mapstorage->nodemap_storage)["label"]))[i];
   227       if(!(text.str().compare(source.get_active_text())))
   228 	{
   229 	  from=i;
   230 	  assigned++;
   231 	}
   232       if(!(text.str().compare(target.get_active_text())))
   233 	{
   234 	  to=i;
   235 	  assigned++;
   236 	}
   237     }
   238 }