X-Git-Url: https://www.tinc-vpn.org/git/browse?p=tinc;a=blobdiff_plain;f=src%2Fgraph.c;h=29e25db16f16258330b4244ecdb6072046c882ad;hp=abc918d9b1ce881cb05d56db7c545c335256ed5a;hb=f48f8f4fedba365ceea30e1133bf1c560e9a522a;hpb=c2b9c06062d36bde859b630b99a08c7b7428e721

diff --git a/src/graph.c b/src/graph.c
index abc918d9..29e25db1 100644
--- 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.
 
-    $Id: graph.c,v 1.1.2.7 2002/02/18 16:25:16 guus Exp $
+    $Id: graph.c,v 1.1.2.10 2002/03/19 22:48:25 guus Exp $
 */
 
 /* We need to generate two trees from the graph:
@@ -77,11 +77,22 @@ void mst_kruskal(void)
   int safe_edges = 0;
   int skipped;
 
+  /* Clear MST status on connections */
+
+  for(node = connection_tree->head; node; node = node->next)
+    {
+      c = (connection_t *)node->data;
+      c->status.mst = 0;
+    }
+
   /* Do we have something to do at all? */
   
   if(!edge_weight_tree->head)
     return;
 
+  if(debug_lvl >= DEBUG_SCARY_THINGS)
+    syslog(LOG_DEBUG, "Running Kruskal's algorithm:");
+
   /* Clear visited status on nodes */
 
   for(node = node_tree->head; node; node = node->next)
@@ -95,14 +106,6 @@ void mst_kruskal(void)
   
   ((edge_t *)edge_weight_tree->head->data)->from.node->status.visited = 1;
 
-  /* Clear MST status on connections */
-
-  for(node = connection_tree->head; node; node = node->next)
-    {
-      c = (connection_t *)node->data;
-      c->status.mst = 0;
-    }
-
   /* Add safe edges */
 
   for(skipped = 0, node = edge_weight_tree->head; node; node = next)
@@ -123,12 +126,18 @@ void mst_kruskal(void)
 
       safe_edges++;
 
+      if(debug_lvl >= DEBUG_SCARY_THINGS)
+	syslog(LOG_DEBUG, " Adding edge %s - %s weight %d", e->from.node->name, e->to.node->name, e->weight);
+
       if(skipped)
         {
           next = edge_weight_tree->head;
           continue;
         }
     }
+
+  if(debug_lvl >= DEBUG_SCARY_THINGS)
+    syslog(LOG_DEBUG, "Done, counted %d nodes and %d safe edges.", nodes, safe_edges);
 }
 
 /* Implementation of a simple breadth-first search algorithm.
@@ -142,6 +151,7 @@ void sssp_bfs(void)
   node_t *n;
   halfconnection_t to_hc, from_hc;
   avl_tree_t *todo_tree;
+  int indirect;
 
   todo_tree = avl_alloc_tree(NULL, NULL);
 
@@ -151,11 +161,13 @@ void sssp_bfs(void)
     {
       n = (node_t *)node->data;
       n->status.visited = 0;
+      n->status.indirect = 1;
     }
 
   /* Begin with myself */
 
   myself->status.visited = 1;
+  myself->status.indirect = 0;
   myself->nexthop = myself;
   myself->via = myself;
   node = avl_alloc_node();
@@ -180,25 +192,47 @@ void sssp_bfs(void)
               else
                 to_hc = e->from, from_hc = e->to;
 
-              if(!to_hc.node->status.visited)
-                {
-                  to_hc.node->status.visited = 1;
-                  to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
-                  to_hc.node->via = (e->options & OPTION_INDIRECT || n->via != n) ? n->via : to_hc.node;
-		  to_hc.node->options = e->options;
-                  if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress))
-		  {
-                    node = avl_unlink(node_udp_tree, to_hc.node);
-                    to_hc.node->address = to_hc.udpaddress;
-		    if(to_hc.node->hostname)
-		      free(to_hc.node->hostname);
-		    to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress);
-                    avl_insert_node(node_udp_tree, node);
-		  }
-                  node = avl_alloc_node();
-                  node->data = to_hc.node;
-                  avl_insert_before(todo_tree, from, node);
-                }
+              /* Situation:
+
+	        	  /
+	        	 /
+		 ------(n)from_hc-----to_hc
+                	 \
+                	  \
+
+                 n->address is set to the to_hc.udpaddress of the edge left of n.
+		 We are currently examining the edge right of n:
+
+                 - If from_hc.udpaddress != n->address, then to_hc.node is probably
+		   not reachable for the nodes left of n. We do as if the indirectdata
+		   flag is set on edge e.
+		 - If edge e provides for better reachability of to_hc.node, update
+		   to_hc.node and (re)add it to the todo_tree to (re)examine the reachability
+		   of nodes behind it.
+	      */
+
+              indirect = n->status.indirect || e->options & OPTION_INDIRECT || ((n != myself) && sockaddrcmp(&n->address, &from_hc.udpaddress));
+
+              if(to_hc.node->status.visited && (!to_hc.node->status.indirect || indirect))
+	        continue;
+
+              to_hc.node->status.visited = 1;
+              to_hc.node->status.indirect = indirect;
+              to_hc.node->nexthop = (n->nexthop == myself) ? to_hc.node : n->nexthop;
+              to_hc.node->via = indirect ? n->via : to_hc.node;
+	      to_hc.node->options = e->options;
+              if(sockaddrcmp(&to_hc.node->address, &to_hc.udpaddress))
+	      {
+                node = avl_unlink(node_udp_tree, to_hc.node);
+                to_hc.node->address = to_hc.udpaddress;
+		if(to_hc.node->hostname)
+		  free(to_hc.node->hostname);
+		to_hc.node->hostname = sockaddr2hostname(&to_hc.udpaddress);
+                avl_insert_node(node_udp_tree, node);
+	      }
+              node = avl_alloc_node();
+              node->data = to_hc.node;
+              avl_insert_before(todo_tree, from, node);
             }
 
           avl_delete_node(todo_tree, from);