- More changes needed for Kruskal's algorithm

[tinc] / src / graph.c

diff --git a/src/graph.c b/src/graph.c
index 50695e4..c7ca8af 100644 (file)
--- a/src/graph.c
+++ b/src/graph.c
@@ -17,7 +17,7 @@
     along with this program; if not, write to the Free Software
     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 
     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.1 2001/10/28 10:16:18 guus Exp $
+    $Id: graph.c,v 1.1.2.2 2001/10/28 22:42:49 guus Exp $

 */
 
 /* We need to generate two trees from the graph:
 */
 
 /* We need to generate two trees from the graph:


@@ -34,12 +34,15 @@
    removed, and during the MST algorithm we just have go linearly through that
    tree, adding safe edges until #edges = #nodes - 1.
 
    removed, and during the MST algorithm we just have go linearly through that
    tree, adding safe edges until #edges = #nodes - 1.
 

-   For the SSSP algorithm Dijkstra's seems to be a nice choice.
+   For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
+   simple breadth-first search is presented here.

 */
 
 #include <syslog.h>
 #include "config.h"
 
 */
 
 #include <syslog.h>
 #include "config.h"
 

+#include <avl_tree.h>
+

 #include "node.h"
 #include "edge.h"
 #include "connection.h"
 #include "node.h"
 #include "edge.h"
 #include "connection.h"


@@ -47,35 +50,35 @@
 #include "system.h"
 
 /* Implementation of Kruskal's algorithm.
 #include "system.h"
 
 /* Implementation of Kruskal's algorithm.

-   Running time: O(V)
-   Please note that sorting on weight is already done by add_vertex().
+   Running time: O(E)
+   Please note that sorting on weight is already done by add_edge().

 */
 
 */
 

-void kruskal(void)
+void mst_kruskal(void)

 {
   avl_node_t *node;
   edge_t *e;
   node_t *n;
   connection_t *c;
 {
   avl_node_t *node;
   edge_t *e;
   node_t *n;
   connection_t *c;

-  int nodes;
+  int nodes = 0;

   int safe_edges = 0;
   
   syslog(LOG_DEBUG, _("Running Kruskal's algorithm:"));
 
   int safe_edges = 0;
   
   syslog(LOG_DEBUG, _("Running Kruskal's algorithm:"));
 

-  /* Clear MST status on nodes */
+  /* Clear visited status on nodes */

 
   for(node = node_tree->head; node; node = node->next)
     {
       n = (node_t *)node->data;
 
   for(node = node_tree->head; node; node = node->next)
     {
       n = (node_t *)node->data;

-      n->status.mst = 0;
-      node++;
+      n->status.visited = 0;
+      nodes++;

     }
 
   /* Clear MST status on connections */
 
   for(node = connection_tree->head; node; node = node->next)
     {
     }
 
   /* Clear MST status on connections */
 
   for(node = connection_tree->head; node; node = node->next)
     {

-      c = (edge_t *)node->data;
+      c = (connection_t *)node->data;

       c->status.mst = 0;
     }
 
       c->status.mst = 0;
     }
 


@@ -89,11 +92,11 @@ void kruskal(void)
 
       e = (edge_t *)node->data;
       
 
       e = (edge_t *)node->data;
       

-      if(e->from->status.mst && e->to->status.mst)
+      if(e->from->status.visited && e->to->status.visited)

         continue;
 
         continue;
 

-      e->from->status.mst = 1;
-      e->to->status.mst = 1;
+      e->from->status.visited = 1;
+      e->to->status.visited = 1;

       if(e->connection)
         e->connection->status.mst = 1;
 
       if(e->connection)
         e->connection->status.mst = 1;
 


@@ -109,3 +112,79 @@ void kruskal(void)
       syslog(LOG_ERR, _("Implementation of Kruskal's algorithm is screwed: %d nodes, found %d safe edges"), nodes, safe_edges);
     }
 }
       syslog(LOG_ERR, _("Implementation of Kruskal's algorithm is screwed: %d nodes, found %d safe edges"), nodes, safe_edges);
     }
 }

+
+/* Implementation of a simple breadth-first search algorithm.
+   Running time: O(E)
+*/
+
+void sssp_bfs(void)
+{
+  avl_node_t *node, *from, *next, *to;
+  edge_t *e;
+  node_t *n, *check;
+  int nodes = 0;
+  int visited = 0;
+  avl_tree_t *todo_tree;
+  
+  syslog(LOG_DEBUG, _("Running BFS algorithm:"));
+
+  todo_tree = avl_alloc_tree(NULL, NULL);
+
+  /* Clear visited status on nodes */
+
+  for(node = node_tree->head; node; node = node->next)
+    {
+      n = (node_t *)node->data;
+      n->status.visited = 0;
+      nodes++;
+    }
+
+  /* Begin with myself */
+
+  myself->status.visited = 1;
+  myself->nexthop = myself;
+  myself->via = myself;
+  node = avl_alloc_node();
+  node->data = myself;
+  avl_insert_top(todo_tree, node);
+  visited++;
+
+  /* Loop while todo_tree is filled */
+
+  while(todo_tree->head)
+    {
+      for(from = todo_tree->head; from; from = next)
+        {
+          next = from->next;
+          n = (node_t *)from->data;
+          
+          for(to = n->edge_tree->head; to; to = to->next)
+            {
+              e = (edge_t *)to->data;
+
+              if(e->from == n)
+                check = e->to;
+              else
+                check = e->from;
+
+              if(!check->status.visited)
+                {
+                  check->status.visited = 1;
+                  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);
+                  visited++;
+                }
+            }
+
+           avl_delete_node(todo_tree, from);
+        }
+    }
+
+  syslog(LOG_DEBUG, _("Done."));
+
+  if(visited != nodes)
+    {
+      syslog(LOG_ERR, _("Implementation of BFS algorithm is screwed: %d nodes, visited %d"), nodes, visited);
+    }
+}