source: glemon/dijkstrabox.cc @ 1:67188bd752db

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2006
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <mapstorage.h>
#include <mapselector.h>
#include <algobox.h>
#include <dijkstrabox.h>

#include <lemon/dijkstra.h>

//No Suurballe in Lemon 1.0
//#include <lemon/suurballe.h>
#include <lemon/path.h>

enum {INPUT, OUTPUT, MAP_NUM};

DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
{
  init(t);
}
    
SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
{
  Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
  num_set = new Gtk::SpinButton(*adjustment, 5,0);

  Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
//   hbox.pack_start(*label);
//   hbox.pack_start(*num_set);
//   hbox.show_all_children();

  table.attach(*label, 0,1,2,3);
  table.attach(*num_set, 1,2,2,3);


//   pack_start(hbox);
}
    
void DijkstraBox::run()
{
  if(
      tabcbt.get_active_text()!="" &&
      (arcmapcbts[INPUT])->get_active_text()!="" &&
      (arcmapcbts[OUTPUT])->get_active_text()!="" &&
      source.get_active_text()!="" &&
      target.get_active_text()!=""
    )
  {
    const Digraph &g=mapstorage->digraph;
    Node from, to;

    get_from_to(from, to, (Digraph&)g);

    std::ostringstream o;

    if(!(from==to))
    {
      std::string inputmapName = arcmapcbts[INPUT]->get_active_text();
      std::string outputmapName = arcmapcbts[OUTPUT]->get_active_text();

      MapStorage::NumericArcMap& inputmap = mapstorage->getNumericArcMap(inputmapName);
      MapStorage::NumericArcMap& outputmap = mapstorage->getNumericArcMap(outputmapName);

      //zero out output map
      for (ArcIt i(g); i!=INVALID; ++i)
      {
        outputmap[i]=0;
      }

      Dijkstra<Digraph, MapStorage::NumericArcMap > dijkstra(g, inputmap);
      dijkstra.run(from, to);

      if(dijkstra.reached(to))
      {
        Node n=to;
        int length=0;
        while (n!=INVALID && n!=from)
        {
          Arc e=dijkstra.predArc(n);
          outputmap[e]=1;
          n=dijkstra.predNode(n);
          length++;
        }
        o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
      }
      else
      {
        o << "Result: failed to find shortest path between ";
        o << source.get_active_text() << " and " << target.get_active_text();
      }
      resultlabel.set_text(o.str());

      mapstorage->mapChanged(true, (arcmapcbts[OUTPUT])->get_active_text());
      //   mapstorage->changeActiveMap(true, E_COLOR,
      //                              (arcmapcbts[OUTPUT])->get_active_text());
      //   mapstorage->changeActiveMap(true, E_TEXT,
      //                              (arcmapcbts[INPUT])->get_active_text());
    }
  }
}

void SuurballeBox::run()
{
  if(
     tabcbt.get_active_text()!="" &&
     (arcmapcbts[INPUT])->get_active_text()!="" &&
     (arcmapcbts[OUTPUT])->get_active_text()!="" &&
     source.get_active_text()!="" &&
     target.get_active_text()!=""
     )
    {
      const Digraph &g=mapstorage->digraph;
      Node from, to;

      get_from_to(from, to, (Digraph&)g);

      std::ostringstream o;

      if(!(from==to))
        {
          MapStorage::NumericArcMap& inputmap=
            mapstorage->getNumericArcMap(arcmapcbts[INPUT]->get_active_text());
          MapStorage::NumericArcMap& outputmap=
            mapstorage->getNumericArcMap(arcmapcbts[OUTPUT]->get_active_text());

          //zero out output map
          for (ArcIt i(g); i!=INVALID; ++i)
            {
              outputmap[i]=0;
            }
          
          //No Suurballe in Lemon 1.0
          //Suurballe<Digraph, MapStorage::NumericArcMap > sb((Digraph&)g, inputmap, from, to);
          
          int found=0;
          //No Suurballe in Lemon 1.0
          //found=sb.run(num_set->get_value_as_int());
          if(found)
            {
              for(int j=0;j<found;j++)
                {
                  Path<Digraph> path;
                  //No Suurballe in Lemon 1.0
                  //path=sb.path(j);
                  for(int k=0;k<path.length();k++)
                    {
                      outputmap[path.nth(k)]=j+1;
                    }
                }
              o << "Result: found " << found << " paths between ";
              o << source.get_active_text() << " and " << target.get_active_text();
            }
          else
            {
              o << "Result: failed to find shortest path between ";
              o << source.get_active_text() << " and " << target.get_active_text();
            }
          resultlabel.set_text(o.str());
          
          mapstorage->mapChanged(true, (arcmapcbts[OUTPUT])->get_active_text());
          //   mapstorage->changeActiveMap(true, E_COLOR,
          //                          (arcmapcbts[OUTPUT])->get_active_text());
          //   mapstorage->changeActiveMap(true, E_TEXT,
          //                          (arcmapcbts[INPUT])->get_active_text());
        }
    }
}
    
void DijkstraBox::build_box()
{
  //if active tab is changed, labels of digraph nodes had to be loaded into comboboxes
  //this can be done after the maps are loaded into ComboBoxes
  signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));

  addMapSelector("Cost map: ", true, NUM);
  addMapSelector("Arcs of path here: ", true, NUM);

  Gtk::Label * source_label=new Gtk::Label("Source: ");
  Gtk::Label * target_label=new Gtk::Label("Target: ");

  table.attach(*source_label, 0,1,0,1);
  table.attach(*target_label, 0,1,1,2);
  table.attach(source, 1,2,0,1);
  table.attach(target, 1,2,1,2);


  pack_start(table);

  resultlabel.set_text("Result: algorithm is not run yet.");
  pack_start(resultlabel);
}

void SuurballeBox::build_box()
{
}

void DijkstraBox::maplists_updated()
{
  if(tabcbt.get_active_text()!="")
    {
      source.clear();
      target.clear();
      const Digraph &g=mapstorage->digraph;
      for (NodeIt i(g); i!=INVALID; ++i)
        {
          std::ostringstream text;
          text << mapstorage->getLabel(i);
          source.prepend_text(text.str());
          target.prepend_text(text.str());
        }
    }
}

void DijkstraBox::get_from_to(Node & from, Node & to, Digraph & g)
{
  int assigned=0;
  for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
    {
      std::ostringstream text;
      text << mapstorage->getLabel(i);
      if(!(text.str().compare(source.get_active_text())))
        {
          from=i;
          assigned++;
        }
      if(!(text.str().compare(target.get_active_text())))
        {
          to=i;
          assigned++;
        }
    }
}