1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/dijkstrabox.cc Mon Jul 07 08:10:39 2008 -0500
1.3 @@ -0,0 +1,247 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2006
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#include <mapstorage.h>
1.23 +#include <mapselector.h>
1.24 +#include <algobox.h>
1.25 +#include <dijkstrabox.h>
1.26 +
1.27 +#include <lemon/dijkstra.h>
1.28 +
1.29 +//No Suurballe in Lemon 1.0
1.30 +//#include <lemon/suurballe.h>
1.31 +#include <lemon/path.h>
1.32 +
1.33 +enum {INPUT, OUTPUT, MAP_NUM};
1.34 +
1.35 +DijkstraBox::DijkstraBox(std::vector<std::string> t):AlgoBox()
1.36 +{
1.37 + init(t);
1.38 +}
1.39 +
1.40 +SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
1.41 +{
1.42 + Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
1.43 + num_set = new Gtk::SpinButton(*adjustment, 5,0);
1.44 +
1.45 + Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
1.46 +// hbox.pack_start(*label);
1.47 +// hbox.pack_start(*num_set);
1.48 +// hbox.show_all_children();
1.49 +
1.50 + table.attach(*label, 0,1,2,3);
1.51 + table.attach(*num_set, 1,2,2,3);
1.52 +
1.53 +
1.54 +// pack_start(hbox);
1.55 +}
1.56 +
1.57 +void DijkstraBox::run()
1.58 +{
1.59 + if(
1.60 + tabcbt.get_active_text()!="" &&
1.61 + (arcmapcbts[INPUT])->get_active_text()!="" &&
1.62 + (arcmapcbts[OUTPUT])->get_active_text()!="" &&
1.63 + source.get_active_text()!="" &&
1.64 + target.get_active_text()!=""
1.65 + )
1.66 + {
1.67 + const Digraph &g=mapstorage->digraph;
1.68 + Node from, to;
1.69 +
1.70 + get_from_to(from, to, (Digraph&)g);
1.71 +
1.72 + std::ostringstream o;
1.73 +
1.74 + if(!(from==to))
1.75 + {
1.76 + std::string inputmapName = arcmapcbts[INPUT]->get_active_text();
1.77 + std::string outputmapName = arcmapcbts[OUTPUT]->get_active_text();
1.78 +
1.79 + MapStorage::NumericArcMap& inputmap = mapstorage->getNumericArcMap(inputmapName);
1.80 + MapStorage::NumericArcMap& outputmap = mapstorage->getNumericArcMap(outputmapName);
1.81 +
1.82 + //zero out output map
1.83 + for (ArcIt i(g); i!=INVALID; ++i)
1.84 + {
1.85 + outputmap[i]=0;
1.86 + }
1.87 +
1.88 + Dijkstra<Digraph, MapStorage::NumericArcMap > dijkstra(g, inputmap);
1.89 + dijkstra.run(from, to);
1.90 +
1.91 + if(dijkstra.reached(to))
1.92 + {
1.93 + Node n=to;
1.94 + int length=0;
1.95 + while (n!=INVALID && n!=from)
1.96 + {
1.97 + Arc e=dijkstra.predArc(n);
1.98 + outputmap[e]=1;
1.99 + n=dijkstra.predNode(n);
1.100 + length++;
1.101 + }
1.102 + o << "Result: " << length << " long path, with cost " << dijkstra.dist(to);
1.103 + }
1.104 + else
1.105 + {
1.106 + o << "Result: failed to find shortest path between ";
1.107 + o << source.get_active_text() << " and " << target.get_active_text();
1.108 + }
1.109 + resultlabel.set_text(o.str());
1.110 +
1.111 + mapstorage->mapChanged(true, (arcmapcbts[OUTPUT])->get_active_text());
1.112 + // mapstorage->changeActiveMap(true, E_COLOR,
1.113 + // (arcmapcbts[OUTPUT])->get_active_text());
1.114 + // mapstorage->changeActiveMap(true, E_TEXT,
1.115 + // (arcmapcbts[INPUT])->get_active_text());
1.116 + }
1.117 + }
1.118 +}
1.119 +
1.120 +void SuurballeBox::run()
1.121 +{
1.122 + if(
1.123 + tabcbt.get_active_text()!="" &&
1.124 + (arcmapcbts[INPUT])->get_active_text()!="" &&
1.125 + (arcmapcbts[OUTPUT])->get_active_text()!="" &&
1.126 + source.get_active_text()!="" &&
1.127 + target.get_active_text()!=""
1.128 + )
1.129 + {
1.130 + const Digraph &g=mapstorage->digraph;
1.131 + Node from, to;
1.132 +
1.133 + get_from_to(from, to, (Digraph&)g);
1.134 +
1.135 + std::ostringstream o;
1.136 +
1.137 + if(!(from==to))
1.138 + {
1.139 + MapStorage::NumericArcMap& inputmap=
1.140 + mapstorage->getNumericArcMap(arcmapcbts[INPUT]->get_active_text());
1.141 + MapStorage::NumericArcMap& outputmap=
1.142 + mapstorage->getNumericArcMap(arcmapcbts[OUTPUT]->get_active_text());
1.143 +
1.144 + //zero out output map
1.145 + for (ArcIt i(g); i!=INVALID; ++i)
1.146 + {
1.147 + outputmap[i]=0;
1.148 + }
1.149 +
1.150 + //No Suurballe in Lemon 1.0
1.151 + //Suurballe<Digraph, MapStorage::NumericArcMap > sb((Digraph&)g, inputmap, from, to);
1.152 +
1.153 + int found=0;
1.154 + //No Suurballe in Lemon 1.0
1.155 + //found=sb.run(num_set->get_value_as_int());
1.156 + if(found)
1.157 + {
1.158 + for(int j=0;j<found;j++)
1.159 + {
1.160 + Path<Digraph> path;
1.161 + //No Suurballe in Lemon 1.0
1.162 + //path=sb.path(j);
1.163 + for(int k=0;k<path.length();k++)
1.164 + {
1.165 + outputmap[path.nth(k)]=j+1;
1.166 + }
1.167 + }
1.168 + o << "Result: found " << found << " paths between ";
1.169 + o << source.get_active_text() << " and " << target.get_active_text();
1.170 + }
1.171 + else
1.172 + {
1.173 + o << "Result: failed to find shortest path between ";
1.174 + o << source.get_active_text() << " and " << target.get_active_text();
1.175 + }
1.176 + resultlabel.set_text(o.str());
1.177 +
1.178 + mapstorage->mapChanged(true, (arcmapcbts[OUTPUT])->get_active_text());
1.179 + // mapstorage->changeActiveMap(true, E_COLOR,
1.180 + // (arcmapcbts[OUTPUT])->get_active_text());
1.181 + // mapstorage->changeActiveMap(true, E_TEXT,
1.182 + // (arcmapcbts[INPUT])->get_active_text());
1.183 + }
1.184 + }
1.185 +}
1.186 +
1.187 +void DijkstraBox::build_box()
1.188 +{
1.189 + //if active tab is changed, labels of digraph nodes had to be loaded into comboboxes
1.190 + //this can be done after the maps are loaded into ComboBoxes
1.191 + signal_upon_maplist_updated().connect(sigc::mem_fun(*this, &DijkstraBox::maplists_updated));
1.192 +
1.193 + addMapSelector("Cost map: ", true, NUM);
1.194 + addMapSelector("Arcs of path here: ", true, NUM);
1.195 +
1.196 + Gtk::Label * source_label=new Gtk::Label("Source: ");
1.197 + Gtk::Label * target_label=new Gtk::Label("Target: ");
1.198 +
1.199 + table.attach(*source_label, 0,1,0,1);
1.200 + table.attach(*target_label, 0,1,1,2);
1.201 + table.attach(source, 1,2,0,1);
1.202 + table.attach(target, 1,2,1,2);
1.203 +
1.204 +
1.205 + pack_start(table);
1.206 +
1.207 + resultlabel.set_text("Result: algorithm is not run yet.");
1.208 + pack_start(resultlabel);
1.209 +}
1.210 +
1.211 +void SuurballeBox::build_box()
1.212 +{
1.213 +}
1.214 +
1.215 +void DijkstraBox::maplists_updated()
1.216 +{
1.217 + if(tabcbt.get_active_text()!="")
1.218 + {
1.219 + source.clear();
1.220 + target.clear();
1.221 + const Digraph &g=mapstorage->digraph;
1.222 + for (NodeIt i(g); i!=INVALID; ++i)
1.223 + {
1.224 + std::ostringstream text;
1.225 + text << mapstorage->getLabel(i);
1.226 + source.prepend_text(text.str());
1.227 + target.prepend_text(text.str());
1.228 + }
1.229 + }
1.230 +}
1.231 +
1.232 +void DijkstraBox::get_from_to(Node & from, Node & to, Digraph & g)
1.233 +{
1.234 + int assigned=0;
1.235 + for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
1.236 + {
1.237 + std::ostringstream text;
1.238 + text << mapstorage->getLabel(i);
1.239 + if(!(text.str().compare(source.get_active_text())))
1.240 + {
1.241 + from=i;
1.242 + assigned++;
1.243 + }
1.244 + if(!(text.str().compare(target.get_active_text())))
1.245 + {
1.246 + to=i;
1.247 + assigned++;
1.248 + }
1.249 + }
1.250 +}