Changeset 165:2cd447b0bd3a in glemon-0.x

Timestamp:

10/13/06 17:31:58 (18 years ago)

Author:

Hegyi Péter

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/glemon/trunk@2990

Message:

Suurballe algorithm is implemented in glemon.

Files:

• algowin.cc (modified) (1 diff)
• dijkstrabox.cc (modified) (6 diffs)
• dijkstrabox.h (modified) (4 diffs)
• main_win.cc (modified) (2 diffs)

algowin.cc

@@ -44 +44 @@
       ab=new DijkstraBox(tabnames);
       set_title("Dijkstra Algorithm");
+      break;
+    case 3:
+      ab=new SuurballeBox(tabnames);
+      set_title("Suurballe Algorithm");
       break;
     default:

dijkstrabox.cc

@@ -1 +1 @@
 #include <dijkstrabox.h>
+#include <lemon/dijkstra.h>
+#include <lemon/suurballe.h>
+#include <lemon/path.h>
 
 enum {INPUT, OUTPUT, MAP_NUM};
@@ -6 +9 @@
 {
   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);
 }
     
@@ -19 +39 @@
     {
       const Graph &g=mapstorage->graph;
-
-      Graph::EdgeMap<double> * inputmap=
-        (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
-      Graph::EdgeMap<double> * outputmap=
-        (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
-
       Node from, to;
-      int assigned=0;
+
+      get_from_to(from, to, (Graph&)g);
+
       std::ostringstream o;
 
-      //zero out output map
-      for (EdgeIt i(g); i!=INVALID; ++i)
-        {
-          (*outputmap)[i]=0;
-        }
-
-      for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
-        {
-          std::ostringstream text;
-          text << (*((mapstorage->nodemap_storage)["label"]))[i];
-          if(!(text.str().compare(source.get_active_text())))
-            {
-              from=i;
-              assigned++;
-            }
-          if(!(text.str().compare(target.get_active_text())))
-            {
-              to=i;
-              assigned++;
-            }
-        }
       if(!(from==to))
         {
+          Graph::EdgeMap<double> * inputmap=
+            (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
+          Graph::EdgeMap<double> * outputmap=
+            (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
+
+          //zero out output map
+          for (EdgeIt i(g); i!=INVALID; ++i)
+            {
+              (*outputmap)[i]=0;
+            }
+          
           Dijkstra<Graph, Graph::EdgeMap<double> > dijkstra(g, *inputmap);
           dijkstra.run(from, to);
-
+          
           if(dijkstra.reached(to))
             {
@@ -74 +80 @@
             }
           resultlabel.set_text(o.str());
-
+          
           mapstorage->mapChanged(true, (edgemapcbts[OUTPUT])->get_active_text());
-        }
-      //   mapstorage->changeActiveMap(true, E_COLOR,
-      //                              (edgemapcbts[OUTPUT])->get_active_text());
-      //   mapstorage->changeActiveMap(true, E_TEXT,
-      //                              (edgemapcbts[INPUT])->get_active_text());
+          //   mapstorage->changeActiveMap(true, E_COLOR,
+          //                          (edgemapcbts[OUTPUT])->get_active_text());
+          //   mapstorage->changeActiveMap(true, E_TEXT,
+          //                          (edgemapcbts[INPUT])->get_active_text());
+        }
+    }
+}
+
+void SuurballeBox::run()
+{
+  if(
+     tabcbt.get_active_text()!="" &&
+     (edgemapcbts[INPUT])->get_active_text()!="" &&
+     (edgemapcbts[OUTPUT])->get_active_text()!="" &&
+     source.get_active_text()!="" &&
+     target.get_active_text()!=""
+     )
+    {
+      const Graph &g=mapstorage->graph;
+      Node from, to;
+
+      get_from_to(from, to, (Graph&)g);
+
+      std::ostringstream o;
+
+      if(!(from==to))
+        {
+          Graph::EdgeMap<double> * inputmap=
+            (mapstorage->edgemap_storage)[(edgemapcbts[INPUT])->get_active_text()];
+          Graph::EdgeMap<double> * outputmap=
+            (mapstorage->edgemap_storage)[(edgemapcbts[OUTPUT])->get_active_text()];
+
+          //zero out output map
+          for (EdgeIt i(g); i!=INVALID; ++i)
+            {
+              (*outputmap)[i]=0;
+            }
+          
+          Suurballe<Graph, Graph::EdgeMap<double> > sb((Graph&)g, *inputmap, from, to);
+          
+          int found=sb.run(num_set->get_value_as_int());
+          if(found)
+            {
+              for(int j=0;j<found;j++)
+                {
+                  DirPath<Graph> path(g);
+                  sb.getPath(path, j);
+                  for(int k=0;k<path.length();k++)
+                    {
+                      DirPath<Graph>::EdgeIt ei;
+                      path.nth(ei,k);
+                      (*outputmap)[ei]=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, (edgemapcbts[OUTPUT])->get_active_text());
+          //   mapstorage->changeActiveMap(true, E_COLOR,
+          //                          (edgemapcbts[OUTPUT])->get_active_text());
+          //   mapstorage->changeActiveMap(true, E_TEXT,
+          //                          (edgemapcbts[INPUT])->get_active_text());
+        }
     }
 }
@@ -108 +179 @@
 }
 
+void SuurballeBox::build_box()
+{
+}
+
 void DijkstraBox::maplists_updated()
 {
@@ -124 +199 @@
     }
 }
+
+void DijkstraBox::get_from_to(Node & from, Node & to, Graph & g)
+{
+  int assigned=0;
+  for (NodeIt i(g); (i!=INVALID) && (assigned<2); ++i)
+    {
+      std::ostringstream text;
+      text << (*((mapstorage->nodemap_storage)["label"]))[i];
+      if(!(text.str().compare(source.get_active_text())))
+        {
+          from=i;
+          assigned++;
+        }
+      if(!(text.str().compare(target.get_active_text())))
+        {
+          to=i;
+          assigned++;
+        }
+    }
+}

dijkstrabox.h

@@ -8 +8 @@
 #include <all_include.h>
 #include <algobox.h>
-#include <lemon/dijkstra.h>
 #include <libgnomecanvasmm.h>
 #include <libgnomecanvasmm/polygon.h>
@@ -24 +23 @@
 class DijkstraBox : public AlgoBox
 {
+protected:
   ///Shows result of Dijkstra algorithm
   Gtk::Label resultlabel;
@@ -37 +37 @@
   Gtk::ComboBoxText target;
 
+  ///Gets to and from node from combobox
+  void get_from_to(Node &, Node &, Graph &);
+
 public:
   ///Calls \ref AlgoBox::init function to initialize class properly, automatically.
@@ -47 +50 @@
   ///As postprocess this bool map should be transformed to
   ///double map.
-  void run();
+  virtual void run();
 
   ///Builds the graphical design of the interface.
-  void build_box();
+  virtual void build_box();
 
   void maplists_updated();
 };
+
+class SuurballeBox : public DijkstraBox
+{
+  ///number of paths to find
+  int num;
+  
+  ///Widget to set numbewr of paths to find
+  Gtk::SpinButton * num_set;
+
+  ///Holder widget
+  Gtk::HBox hbox;
+
+public:
+  SuurballeBox(std::vector<std::string> t);
+  void run();
+  void build_box();
+};
 #endif //DIJKSTRABOX_H

main_win.cc

@@ -110 +110 @@
   ag->add( Gtk::Action::create("AlgoDijkstra", _("_Dijkstra")),
            sigc::bind( sigc::mem_fun ( *this, &MainWin::createAlgoWin ), 2) );
+  ag->add( Gtk::Action::create("AlgoSuurballe", _("_Suurballe")),
+           sigc::bind( sigc::mem_fun ( *this, &MainWin::createAlgoWin ), 3) );
 
   Gtk::RadioAction::Group tool_group;
@@ -163 +165 @@
       "      <menuitem action='AlgoKruskal'/>"
       "      <menuitem action='AlgoDijkstra'/>"
+      "      <menuitem action='AlgoSuurballe'/>"
       "    </menu>"
       "  </menubar>"