hegyi@1: /* -*- C++ -*-
hegyi@1:  *
hegyi@1:  * This file is a part of LEMON, a generic C++ optimization library
hegyi@1:  *
hegyi@1:  * Copyright (C) 2003-2006
hegyi@1:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
hegyi@1:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
hegyi@1:  *
hegyi@1:  * Permission to use, modify and distribute this software is granted
hegyi@1:  * provided that this copyright notice appears in all copies. For
hegyi@1:  * precise terms see the accompanying LICENSE file.
hegyi@1:  *
hegyi@1:  * This software is provided "AS IS" with no warranty of any kind,
hegyi@1:  * express or implied, and with no claim as to its suitability for any
hegyi@1:  * purpose.
hegyi@1:  *
hegyi@1:  */
hegyi@1: 
hegyi@1: #include <mapstorage.h>
hegyi@1: #include <mapselector.h>
hegyi@1: #include <algobox.h>
hegyi@1: #include <dijkstrabox.h>
hegyi@1: 
hegyi@1: #include <lemon/dijkstra.h>
hegyi@1: 
hegyi@1: //No Suurballe in Lemon 1.0
hegyi@1: //#include <lemon/suurballe.h>
hegyi@1: #include <lemon/path.h>
hegyi@1: 
hegyi@1: enum {INPUT, OUTPUT, MAP_NUM};
hegyi@1: 
hegyi@1: DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
hegyi@1: {
hegyi@1:   init(t);
hegyi@1: }
hegyi@1:     
hegyi@1: SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
hegyi@1: {
hegyi@1:   Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
hegyi@1:   num_set = new Gtk::SpinButton(*adjustment, 5,0);
hegyi@1: 
hegyi@1:   Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
hegyi@1: //   hbox.pack_start(*label);
hegyi@1: //   hbox.pack_start(*num_set);
hegyi@1: //   hbox.show_all_children();
hegyi@1: 
hegyi@1:   table.attach(*label, 0,1,2,3);
hegyi@1:   table.attach(*num_set, 1,2,2,3);
hegyi@1: 
hegyi@1: 
hegyi@1: //   pack_start(hbox);
hegyi@1: }
hegyi@1:     
hegyi@1: void DijkstraBox::run()
hegyi@1: {
hegyi@1:   if(
hegyi@1:       tabcbt.get_active_text()!="" &&
hegyi@1:       (arcmapcbts[INPUT])->get_active_text()!="" &&
hegyi@1:       (arcmapcbts[OUTPUT])->get_active_text()!="" &&
hegyi@1:       source.get_active_text()!="" &&
hegyi@1:       target.get_active_text()!=""
hegyi@1:     )
hegyi@1:   {
hegyi@1:     const Digraph &g=mapstorage->digraph;
hegyi@1:     Node from, to;
hegyi@1: 
hegyi@1:     get_from_to(from, to, (Digraph&)g);
hegyi@1: 
hegyi@1:     std::ostringstream o;
hegyi@1: 
hegyi@1:     if(!(from==to))
hegyi@1:     {
hegyi@1:       std::string inputmapName = arcmapcbts[INPUT]->get_active_text();
hegyi@1:       std::string outputmapName = arcmapcbts[OUTPUT]->get_active_text();
hegyi@1: 
hegyi@1:       MapStorage::NumericArcMap& inputmap = mapstorage->getNumericArcMap(inputmapName);
hegyi@1:       MapStorage::NumericArcMap& outputmap = mapstorage->getNumericArcMap(outputmapName);
hegyi@1: 
hegyi@1:       //zero out output map
hegyi@1:       for (ArcIt i(g); i!=INVALID; ++i)
hegyi@1:       {
hegyi@1:         outputmap[i]=0;
hegyi@1:       }
hegyi@1: 
hegyi@1:       Dijkstra<Digraph, MapStorage::NumericArcMap > dijkstra(g, inputmap);
hegyi@1:       dijkstra.run(from, to);
hegyi@1: 
hegyi@1:       if(dijkstra.reached(to))
hegyi@1:       {
hegyi@1:         Node n=to;
hegyi@1:         int length=0;
hegyi@1:         while (n!=INVALID && n!=from)
hegyi@1:         {
hegyi@1:           Arc e=dijkstra.predArc(n);
hegyi@1:           outputmap[e]=1;
hegyi@1:           n=dijkstra.predNode(n);
hegyi@1:           length++;
hegyi@1:         }
hegyi@1:         o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
hegyi@1:       }
hegyi@1:       else
hegyi@1:       {
hegyi@1:         o << "Result: failed to find shortest path between ";
hegyi@1:         o << source.get_active_text() << " and " << target.get_active_text();
hegyi@1:       }
hegyi@1:       resultlabel.set_text(o.str());
hegyi@1: 
hegyi@1:       mapstorage->mapChanged(true, (arcmapcbts[OUTPUT])->get_active_text());
hegyi@1:       //   mapstorage->changeActiveMap(true, E_COLOR,
hegyi@1:       // 			      (arcmapcbts[OUTPUT])->get_active_text());
hegyi@1:       //   mapstorage->changeActiveMap(true, E_TEXT,
hegyi@1:       // 			      (arcmapcbts[INPUT])->get_active_text());
hegyi@1:     }
hegyi@1:   }
hegyi@1: }
hegyi@1: 
hegyi@1: void SuurballeBox::run()
hegyi@1: {
hegyi@1:   if(
hegyi@1:      tabcbt.get_active_text()!="" &&
hegyi@1:      (arcmapcbts[INPUT])->get_active_text()!="" &&
hegyi@1:      (arcmapcbts[OUTPUT])->get_active_text()!="" &&
hegyi@1:      source.get_active_text()!="" &&
hegyi@1:      target.get_active_text()!=""
hegyi@1:      )
hegyi@1:     {
hegyi@1:       const Digraph &g=mapstorage->digraph;
hegyi@1:       Node from, to;
hegyi@1: 
hegyi@1:       get_from_to(from, to, (Digraph&)g);
hegyi@1: 
hegyi@1:       std::ostringstream o;
hegyi@1: 
hegyi@1:       if(!(from==to))
hegyi@1: 	{
hegyi@1:           MapStorage::NumericArcMap& inputmap=
hegyi@1: 	    mapstorage->getNumericArcMap(arcmapcbts[INPUT]->get_active_text());
hegyi@1:           MapStorage::NumericArcMap& outputmap=
hegyi@1: 	    mapstorage->getNumericArcMap(arcmapcbts[OUTPUT]->get_active_text());
hegyi@1: 
hegyi@1: 	  //zero out output map
hegyi@1: 	  for (ArcIt i(g); i!=INVALID; ++i)
hegyi@1: 	    {
hegyi@1: 	      outputmap[i]=0;
hegyi@1: 	    }
hegyi@1: 	  
hegyi@1: 	  //No Suurballe in Lemon 1.0
hegyi@1: 	  //Suurballe<Digraph, MapStorage::NumericArcMap > sb((Digraph&)g, inputmap, from, to);
hegyi@1: 	  
hegyi@1: 	  int found=0;
hegyi@1: 	  //No Suurballe in Lemon 1.0
hegyi@1: 	  //found=sb.run(num_set->get_value_as_int());
hegyi@1: 	  if(found)
hegyi@1: 	    {
hegyi@1: 	      for(int j=0;j<found;j++)
hegyi@1: 		{
hegyi@1: 		  Path<Digraph> path;
hegyi@1: 		  //No Suurballe in Lemon 1.0
hegyi@1: 		  //path=sb.path(j);
hegyi@1: 		  for(int k=0;k<path.length();k++)
hegyi@1: 		    {
hegyi@1: 		      outputmap[path.nth(k)]=j+1;
hegyi@1: 		    }
hegyi@1: 		}
hegyi@1: 	      o << "Result: found " << found << " paths between ";
hegyi@1: 	      o << source.get_active_text() << " and " << target.get_active_text();
hegyi@1: 	    }
hegyi@1: 	  else
hegyi@1: 	    {
hegyi@1: 	      o << "Result: failed to find shortest path between ";
hegyi@1: 	      o << source.get_active_text() << " and " << target.get_active_text();
hegyi@1: 	    }
hegyi@1: 	  resultlabel.set_text(o.str());
hegyi@1: 	  
hegyi@1: 	  mapstorage->mapChanged(true, (arcmapcbts[OUTPUT])->get_active_text());
hegyi@1: 	  //   mapstorage->changeActiveMap(true, E_COLOR,
hegyi@1: 	  // 			      (arcmapcbts[OUTPUT])->get_active_text());
hegyi@1: 	  //   mapstorage->changeActiveMap(true, E_TEXT,
hegyi@1: 	  // 			      (arcmapcbts[INPUT])->get_active_text());
hegyi@1: 	}
hegyi@1:     }
hegyi@1: }
hegyi@1:     
hegyi@1: void DijkstraBox::build_box()
hegyi@1: {
hegyi@1:   //if active tab is changed, labels of digraph nodes had to be loaded into comboboxes
hegyi@1:   //this can be done after the maps are loaded into ComboBoxes
hegyi@1:   signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
hegyi@1: 
hegyi@1:   addMapSelector("Cost map: ", true, NUM);
hegyi@1:   addMapSelector("Arcs of path here: ", true, NUM);
hegyi@1: 
hegyi@1:   Gtk::Label * source_label=new Gtk::Label("Source: ");
hegyi@1:   Gtk::Label * target_label=new Gtk::Label("Target: ");
hegyi@1: 
hegyi@1:   table.attach(*source_label, 0,1,0,1);
hegyi@1:   table.attach(*target_label, 0,1,1,2);
hegyi@1:   table.attach(source, 1,2,0,1);
hegyi@1:   table.attach(target, 1,2,1,2);
hegyi@1: 
hegyi@1: 
hegyi@1:   pack_start(table);
hegyi@1: 
hegyi@1:   resultlabel.set_text("Result: algorithm is not run yet.");
hegyi@1:   pack_start(resultlabel);
hegyi@1: }
hegyi@1: 
hegyi@1: void SuurballeBox::build_box()
hegyi@1: {
hegyi@1: }
hegyi@1: 
hegyi@1: void DijkstraBox::maplists_updated()
hegyi@1: {
hegyi@1:   if(tabcbt.get_active_text()!="")
hegyi@1:     {
hegyi@1:       source.clear();
hegyi@1:       target.clear();
hegyi@1:       const Digraph &g=mapstorage->digraph;
hegyi@1:       for (NodeIt i(g); i!=INVALID; ++i)
hegyi@1: 	{
hegyi@1: 	  std::ostringstream text;
hegyi@1: 	  text << mapstorage->getLabel(i);
hegyi@1: 	  source.prepend_text(text.str());
hegyi@1: 	  target.prepend_text(text.str());
hegyi@1: 	}
hegyi@1:     }
hegyi@1: }
hegyi@1: 
hegyi@1: void DijkstraBox::get_from_to(Node & from, Node & to, Digraph & g)
hegyi@1: {
hegyi@1:   int assigned=0;
hegyi@1:   for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
hegyi@1:     {
hegyi@1:       std::ostringstream text;
hegyi@1:       text << mapstorage->getLabel(i);
hegyi@1:       if(!(text.str().compare(source.get_active_text())))
hegyi@1: 	{
hegyi@1: 	  from=i;
hegyi@1: 	  assigned++;
hegyi@1: 	}
hegyi@1:       if(!(text.str().compare(target.get_active_text())))
hegyi@1: 	{
hegyi@1: 	  to=i;
hegyi@1: 	  assigned++;
hegyi@1: 	}
hegyi@1:     }
hegyi@1: }