From: Guus Sliepen <guus@tinc-vpn.org>
Date: Mon, 29 Oct 2001 13:14:57 +0000 (+0000)
Subject: Working version of Kruskal's algorithm. The running time is very bad though.
X-Git-Tag: release-1.0pre5~41
X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=commitdiff_plain;h=cc9473d8c6467e9eaa82fe8a639d8edba232ee76

Working version of Kruskal's algorithm. The running time is very bad though.
---

diff --git a/src/graph.c b/src/graph.c
index c7ca8af1..7b8880dc 100644
--- a/src/graph.c
+++ b/src/graph.c
@@ -17,17 +17,17 @@
     along with this program; if not, write to the Free Software
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
-    $Id: graph.c,v 1.1.2.2 2001/10/28 22:42:49 guus Exp $
+    $Id: graph.c,v 1.1.2.3 2001/10/29 13:14:57 guus Exp $
 */
 
 /* We need to generate two trees from the graph:
 
    1. A minimum spanning tree for broadcasts,
    2. A single-source shortest path tree for unicasts.
-   
+
    Actually, the first one alone would suffice but would make unicast packets
    take longer routes than necessary.
-   
+
    For the MST algorithm we can choose from Prim's or Kruskal's. I personally
    favour Kruskal's, because we make an extra AVL tree of edges sorted on
    weights (metric). That tree only has to be updated when an edge is added or
@@ -40,6 +40,7 @@
 
 #include <syslog.h>
 #include "config.h"
+#include <string.h>
 
 #include <avl_tree.h>
 
@@ -50,7 +51,7 @@
 #include "system.h"
 
 /* Implementation of Kruskal's algorithm.
-   Running time: O(E)
+   Running time: O(EN)
    Please note that sorting on weight is already done by add_edge().
 */
 
@@ -62,7 +63,8 @@ void mst_kruskal(void)
   connection_t *c;
   int nodes = 0;
   int safe_edges = 0;
-  
+  int skipped;
+
   syslog(LOG_DEBUG, _("Running Kruskal's algorithm:"));
 
   /* Clear visited status on nodes */
@@ -74,6 +76,10 @@ void mst_kruskal(void)
       nodes++;
     }
 
+  /* Starting point */
+  
+  ((edge_t *)edge_weight_tree->head->data)->from->status.visited = 1;
+
   /* Clear MST status on connections */
 
   for(node = connection_tree->head; node; node = node->next)
@@ -84,25 +90,32 @@ void mst_kruskal(void)
 
   /* Add safe edges */
 
-  for(node = edge_weight_tree->head; node; node = node->next)
+  while(safe_edges < nodes - 1)
+  for(skipped = 0, node = edge_weight_tree->head; node; node = node->next)
     {
 // Algorithm should work without this:
 //      if(safe_edges = nodes - 1)
 //        break;
 
       e = (edge_t *)node->data;
-      
-      if(e->from->status.visited && e->to->status.visited)
-        continue;
+
+      if(e->from->status.visited == e->to->status.visited)
+        {
+          skipped = 1;
+          continue;
+        }
 
       e->from->status.visited = 1;
       e->to->status.visited = 1;
       if(e->connection)
         e->connection->status.mst = 1;
 
-      safe_edges++;      
+      safe_edges++;
 
       syslog(LOG_DEBUG, _("Adding safe edge %s - %s weight %d"), e->from->name, e->to->name, e->weight);
+
+      if(skipped)
+        break;
     }
 
   syslog(LOG_DEBUG, _("Done."));
@@ -125,7 +138,7 @@ void sssp_bfs(void)
   int nodes = 0;
   int visited = 0;
   avl_tree_t *todo_tree;
-  
+
   syslog(LOG_DEBUG, _("Running BFS algorithm:"));
 
   todo_tree = avl_alloc_tree(NULL, NULL);
@@ -157,7 +170,7 @@ void sssp_bfs(void)
         {
           next = from->next;
           n = (node_t *)from->data;
-          
+
           for(to = n->edge_tree->head; to; to = to->next)
             {
               e = (edge_t *)to->data;
@@ -170,10 +183,13 @@ void sssp_bfs(void)
               if(!check->status.visited)
                 {
                   check->status.visited = 1;
-                  check->nexthop = (n->nexthop == myself)?n:n->nexthop;
+                  check->nexthop = (n->nexthop == myself) ? n : n->nexthop;
                   check->via = check; /* FIXME: only if !(e->options & INDIRECT), otherwise use n->via */
-                  avl_insert_before(todo_tree, todo_tree->head, to);
+                  node = avl_alloc_node();
+                  node->data = check;
+                  avl_insert_before(todo_tree, from, node);
                   visited++;
+                  syslog(LOG_DEBUG, _("Node %s nexthop %s via %s"), check->name, check->nexthop->name, check->via->name);
                 }
             }
 
@@ -183,6 +199,8 @@ void sssp_bfs(void)
 
   syslog(LOG_DEBUG, _("Done."));
 
+  avl_free_tree(todo_tree);
+
   if(visited != nodes)
     {
       syslog(LOG_ERR, _("Implementation of BFS algorithm is screwed: %d nodes, visited %d"), nodes, visited);
diff --git a/src/graph.h b/src/graph.h
new file mode 100644
index 00000000..c69fc98b
--- /dev/null
+++ b/src/graph.h
@@ -0,0 +1,25 @@
+/*
+    graph.h -- header for graph.c
+    Copyright (C) 2001 Guus Sliepen <guus@sliepen.warande.net>,
+                  2001 Ivo Timmermans <itimmermans@bigfoot.com>
+
+    This program is free software; you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation; either version 2 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program; if not, write to the Free Software
+    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+
+    $Id: graph.h,v 1.1.2.1 2001/10/29 13:14:57 guus Exp $
+*/
+
+extern void mst_kruskal(void);
+extern void mst_prim(void);
+extern void sssp_bfs(void);