dijkstrabox.cc
author hegyi
Wed, 25 Oct 2006 13:21:24 +0000
changeset 172 fc1e478697d3
parent 165 2cd447b0bd3a
child 174 95872af46fc4
permissions -rw-r--r--
Currently visualized map can be saved and loaded from file.
     1 #include <dijkstrabox.h>
     2 #include <lemon/dijkstra.h>
     3 #include <lemon/suurballe.h>
     4 #include <lemon/path.h>
     5 
     6 enum {INPUT, OUTPUT, MAP_NUM};
     7 
     8 DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
     9 {
    10   init(t);
    11 }
    12     
    13 SuurballeBox::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);
    28 }
    29     
    30 void DijkstraBox::run()
    31 {
    32   if(
    33      tabcbt.get_active_text()!="" &&
    34      (edgemapcbts[INPUT])->get_active_text()!="" &&
    35      (edgemapcbts[OUTPUT])->get_active_text()!="" &&
    36      source.get_active_text()!="" &&
    37      target.get_active_text()!=""
    38      )
    39     {
    40       const Graph &g=mapstorage->graph;
    41       Node from, to;
    42 
    43       get_from_to(from, to, (Graph&)g);
    44 
    45       std::ostringstream o;
    46 
    47       if(!(from==to))
    48 	{
    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 	  
    60 	  Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
    61 	  dijkstra.run(from, to);
    62 	  
    63 	  if(dijkstra.reached(to))
    64 	    {
    65 	      Node n=to;
    66 	      int length=0;
    67 	      while (n!=INVALID && n!=from)
    68 		{
    69 		  Edge e=dijkstra.predEdge(n);
    70 		  (*outputmap)[e]=1;
    71 		  n=dijkstra.predNode(n);
    72 		  length++;
    73 		}
    74 	      o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
    75 	    }
    76 	  else
    77 	    {
    78 	      o << "Result: failed to find shortest path between ";
    79 	      o << source.get_active_text() << " and " << target.get_active_text();
    80 	    }
    81 	  resultlabel.set_text(o.str());
    82 	  
    83 	  mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->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 
    92 void 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 		  Path<Graph> path(g);
   130 		  sb.getPath(path, j);
   131 		  for(int k=0;k<path.length();k++)
   132 		    {
   133 		      Path<Graph>::EdgeIt ei;
   134 		      ei=path.nthEdge(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 	}
   154     }
   155 }
   156     
   157 void DijkstraBox::build_box()
   158 {
   159   //if active tab is changed, labels of graph nodes had to be loaded into comboboxes
   160   //this can be done after the maps are loaded into ComboBoxes
   161   signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
   162 
   163   addMapSelector("Cost map: ", true);
   164   addMapSelector("Edges of path here: ", true);
   165 
   166   Gtk::Label * source_label=new Gtk::Label("Source: ");
   167   Gtk::Label * target_label=new Gtk::Label("Target: ");
   168 
   169   table.attach(*source_label, 0,1,0,1);
   170   table.attach(*target_label, 0,1,1,2);
   171   table.attach(source, 1,2,0,1);
   172   table.attach(target, 1,2,1,2);
   173 
   174 
   175   pack_start(table);
   176 
   177   resultlabel.set_text("Result: algorithm is not run yet.");
   178   pack_start(resultlabel);
   179 }
   180 
   181 void SuurballeBox::build_box()
   182 {
   183 }
   184 
   185 void DijkstraBox::maplists_updated()
   186 {
   187   if(tabcbt.get_active_text()!="")
   188     {
   189       source.clear();
   190       target.clear();
   191       const Graph &g=mapstorage->graph;
   192       for (NodeIt i(g); i!=INVALID; ++i)
   193 	{
   194 	  std::ostringstream text;
   195 	  text << (*((mapstorage->nodemap_storage)["label"]))[i];
   196 	  source.prepend_text(text.str());
   197 	  target.prepend_text(text.str());
   198 	}
   199     }
   200 }
   201 
   202 void 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 }