1.1 --- a/algowin.cc Fri Oct 13 15:14:18 2006 +0000
1.2 +++ b/algowin.cc Fri Oct 13 15:31:58 2006 +0000
1.3 @@ -44,6 +44,10 @@
1.4 ab=new DijkstraBox(tabnames);
1.5 set_title("Dijkstra Algorithm");
1.6 break;
1.7 + case 3:
1.8 + ab=new SuurballeBox(tabnames);
1.9 + set_title("Suurballe Algorithm");
1.10 + break;
1.11 default:
1.12 break;
1.13 }
2.1 --- a/dijkstrabox.cc Fri Oct 13 15:14:18 2006 +0000
2.2 +++ b/dijkstrabox.cc Fri Oct 13 15:31:58 2006 +0000
2.3 @@ -1,4 +1,7 @@
2.4 #include <dijkstrabox.h>
2.5 +#include <lemon/dijkstra.h>
2.6 +#include <lemon/suurballe.h>
2.7 +#include <lemon/path.h>
2.8
2.9 enum {INPUT, OUTPUT, MAP_NUM};
2.10
2.11 @@ -7,6 +10,23 @@
2.12 init(t);
2.13 }
2.14
2.15 +SuurballeBox::SuurballeBox(std::vector<std::string> t):DijkstraBox(t)
2.16 +{
2.17 + Gtk::Adjustment * adjustment=new Gtk::Adjustment(2, 1, 20, 1, 5);
2.18 + num_set = new Gtk::SpinButton(*adjustment, 5,0);
2.19 +
2.20 + Gtk::Label * label=new Gtk::Label("No. of paths to find: ");
2.21 +// hbox.pack_start(*label);
2.22 +// hbox.pack_start(*num_set);
2.23 +// hbox.show_all_children();
2.24 +
2.25 + table.attach(*label, 0,1,2,3);
2.26 + table.attach(*num_set, 1,2,2,3);
2.27 +
2.28 +
2.29 +// pack_start(hbox);
2.30 +}
2.31 +
2.32 void DijkstraBox::run()
2.33 {
2.34 if(
2.35 @@ -18,42 +38,28 @@
2.36 )
2.37 {
2.38 const Graph &g=mapstorage->graph;
2.39 + Node from, to;
2.40
2.41 - Graph::EdgeMap<double> * inputmap=
2.42 - (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
2.43 - Graph::EdgeMap<double> * outputmap=
2.44 - (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
2.45 + get_from_to(from, to, (Graph&)g);
2.46
2.47 - Node from, to;
2.48 - int assigned=0;
2.49 std::ostringstream o;
2.50
2.51 - //zero out output map
2.52 - for (EdgeIt i(g); i!=INVALID; ++i)
2.53 - {
2.54 - (*outputmap)[i]=0;
2.55 - }
2.56 -
2.57 - for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
2.58 - {
2.59 - std::ostringstream text;
2.60 - text << (*((mapstorage->nodemap_storage)["label"]))[i];
2.61 - if(!(text.str().compare(source.get_active_text())))
2.62 - {
2.63 - from=i;
2.64 - assigned++;
2.65 - }
2.66 - if(!(text.str().compare(target.get_active_text())))
2.67 - {
2.68 - to=i;
2.69 - assigned++;
2.70 - }
2.71 - }
2.72 if(!(from==to))
2.73 {
2.74 + Graph::EdgeMap<double> * inputmap=
2.75 + (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
2.76 + Graph::EdgeMap<double> * outputmap=
2.77 + (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
2.78 +
2.79 + //zero out output map
2.80 + for (EdgeIt i(g); i!=INVALID; ++i)
2.81 + {
2.82 + (*outputmap)[i]=0;
2.83 + }
2.84 +
2.85 Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
2.86 dijkstra.run(from, to);
2.87 -
2.88 +
2.89 if(dijkstra.reached(to))
2.90 {
2.91 Node n=to;
2.92 @@ -73,13 +79,78 @@
2.93 o << source.get_active_text() << " and " << target.get_active_text();
2.94 }
2.95 resultlabel.set_text(o.str());
2.96 +
2.97 + mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
2.98 + // mapstorage->changeActiveMap(true, E_COLOR,
2.99 + // (edgemapcbts[OUTPUT])->get_active_text());
2.100 + // mapstorage->changeActiveMap(true, E_TEXT,
2.101 + // (edgemapcbts[INPUT])->get_active_text());
2.102 + }
2.103 + }
2.104 +}
2.105
2.106 +void SuurballeBox::run()
2.107 +{
2.108 + if(
2.109 + tabcbt.get_active_text()!="" &&
2.110 + (edgemapcbts[INPUT])->get_active_text()!="" &&
2.111 + (edgemapcbts[OUTPUT])->get_active_text()!="" &&
2.112 + source.get_active_text()!="" &&
2.113 + target.get_active_text()!=""
2.114 + )
2.115 + {
2.116 + const Graph &g=mapstorage->graph;
2.117 + Node from, to;
2.118 +
2.119 + get_from_to(from, to, (Graph&)g);
2.120 +
2.121 + std::ostringstream o;
2.122 +
2.123 + if(!(from==to))
2.124 + {
2.125 + Graph::EdgeMap<double> * inputmap=
2.126 + (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
2.127 + Graph::EdgeMap<double> * outputmap=
2.128 + (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
2.129 +
2.130 + //zero out output map
2.131 + for (EdgeIt i(g); i!=INVALID; ++i)
2.132 + {
2.133 + (*outputmap)[i]=0;
2.134 + }
2.135 +
2.136 + Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
2.137 +
2.138 + int found=sb.run(num_set->get_value_as_int());
2.139 + if(found)
2.140 + {
2.141 + for(int j=0;j<found;j++)
2.142 + {
2.143 + DirPath<Graph> path(g);
2.144 + sb.getPath(path, j);
2.145 + for(int k=0;k<path.length();k++)
2.146 + {
2.147 + DirPath<Graph>::EdgeIt ei;
2.148 + path.nth(ei,k);
2.149 + (*outputmap)[ei]=j+1;
2.150 + }
2.151 + }
2.152 + o << "Result: found " << found << " paths between ";
2.153 + o << source.get_active_text() << " and " << target.get_active_text();
2.154 + }
2.155 + else
2.156 + {
2.157 + o << "Result: failed to find shortest path between ";
2.158 + o << source.get_active_text() << " and " << target.get_active_text();
2.159 + }
2.160 + resultlabel.set_text(o.str());
2.161 +
2.162 mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
2.163 + // mapstorage->changeActiveMap(true, E_COLOR,
2.164 + // (edgemapcbts[OUTPUT])->get_active_text());
2.165 + // mapstorage->changeActiveMap(true, E_TEXT,
2.166 + // (edgemapcbts[INPUT])->get_active_text());
2.167 }
2.168 - // mapstorage->changeActiveMap(true, E_COLOR,
2.169 - // (edgemapcbts[OUTPUT])->get_active_text());
2.170 - // mapstorage->changeActiveMap(true, E_TEXT,
2.171 - // (edgemapcbts[INPUT])->get_active_text());
2.172 }
2.173 }
2.174
2.175 @@ -107,6 +178,10 @@
2.176 pack_start(resultlabel);
2.177 }
2.178
2.179 +void SuurballeBox::build_box()
2.180 +{
2.181 +}
2.182 +
2.183 void DijkstraBox::maplists_updated()
2.184 {
2.185 if(tabcbt.get_active_text()!="")
2.186 @@ -123,3 +198,23 @@
2.187 }
2.188 }
2.189 }
2.190 +
2.191 +void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
2.192 +{
2.193 + int assigned=0;
2.194 + for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
2.195 + {
2.196 + std::ostringstream text;
2.197 + text << (*((mapstorage->nodemap_storage)["label"]))[i];
2.198 + if(!(text.str().compare(source.get_active_text())))
2.199 + {
2.200 + from=i;
2.201 + assigned++;
2.202 + }
2.203 + if(!(text.str().compare(target.get_active_text())))
2.204 + {
2.205 + to=i;
2.206 + assigned++;
2.207 + }
2.208 + }
2.209 +}
3.1 --- a/dijkstrabox.h Fri Oct 13 15:14:18 2006 +0000
3.2 +++ b/dijkstrabox.h Fri Oct 13 15:31:58 2006 +0000
3.3 @@ -7,7 +7,6 @@
3.4
3.5 #include <all_include.h>
3.6 #include <algobox.h>
3.7 -#include <lemon/dijkstra.h>
3.8 #include <libgnomecanvasmm.h>
3.9 #include <libgnomecanvasmm/polygon.h>
3.10
3.11 @@ -23,6 +22,7 @@
3.12 ///-implement \ref run function
3.13 class DijkstraBox : public AlgoBox
3.14 {
3.15 +protected:
3.16 ///Shows result of Dijkstra algorithm
3.17 Gtk::Label resultlabel;
3.18
3.19 @@ -36,6 +36,9 @@
3.20 ///Combobox for select target node
3.21 Gtk::ComboBoxText target;
3.22
3.23 + ///Gets to and from node from combobox
3.24 + void get_from_to(Node &, Node &, Graph &);
3.25 +
3.26 public:
3.27 ///Calls \ref AlgoBox::init function to initialize class properly, automatically.
3.28 DijkstraBox(std::vector<std::string> t);
3.29 @@ -46,11 +49,28 @@
3.30 ///at the moment. While Dijkstra nedds a bool map as output.
3.31 ///As postprocess this bool map should be transformed to
3.32 ///double map.
3.33 - void run();
3.34 + virtual void run();
3.35
3.36 ///Builds the graphical design of the interface.
3.37 - void build_box();
3.38 + virtual void build_box();
3.39
3.40 void maplists_updated();
3.41 };
3.42 +
3.43 +class SuurballeBox : public DijkstraBox
3.44 +{
3.45 + ///number of paths to find
3.46 + int num;
3.47 +
3.48 + ///Widget to set numbewr of paths to find
3.49 + Gtk::SpinButton * num_set;
3.50 +
3.51 + ///Holder widget
3.52 + Gtk::HBox hbox;
3.53 +
3.54 +public:
3.55 + SuurballeBox(std::vector<std::string> t);
3.56 + void run();
3.57 + void build_box();
3.58 +};
3.59 #endif //DIJKSTRABOX_H
4.1 --- a/main_win.cc Fri Oct 13 15:14:18 2006 +0000
4.2 +++ b/main_win.cc Fri Oct 13 15:31:58 2006 +0000
4.3 @@ -109,6 +109,8 @@
4.4 sigc::bind( sigc::mem_fun ( *this, &MainWin::createAlgoWin ), 1) );
4.5 ag->add( Gtk::Action::create("AlgoDijkstra", _("_Dijkstra")),
4.6 sigc::bind( sigc::mem_fun ( *this, &MainWin::createAlgoWin ), 2) );
4.7 + ag->add( Gtk::Action::create("AlgoSuurballe", _("_Suurballe")),
4.8 + sigc::bind( sigc::mem_fun ( *this, &MainWin::createAlgoWin ), 3) );
4.9
4.10 Gtk::RadioAction::Group tool_group;
4.11 ag->add( Gtk::RadioAction::create(tool_group, "MoveItem", Gtk::StockID("gd-move"), _("Move")),
4.12 @@ -162,6 +164,7 @@
4.13 " <menuitem action='AlgoGeneral'/>"
4.14 " <menuitem action='AlgoKruskal'/>"
4.15 " <menuitem action='AlgoDijkstra'/>"
4.16 + " <menuitem action='AlgoSuurballe'/>"
4.17 " </menu>"
4.18 " </menubar>"
4.19 " <toolbar name='ToolBar'>"