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