From 1ddd6111a40733929089316838020f89176cbda2 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Thu, 17 Jan 2013 11:21:18 +0100 Subject: [PATCH] Fix the minimum spanning tree algorithm. Tinc uses Kruskal's algorithm to calculate a MST. However, this was broken in commit 6e80da3370249caa1082c23c3ef55f338d1e9e74. Revert back to the working algorithm from tinc 1.0. Thanks to Cheng LI for spotting the problem. --- src/graph.c | 25 +++++++++++++++++++++---- 1 file changed, 21 insertions(+), 4 deletions(-) diff --git a/src/graph.c b/src/graph.c index 73db3b2f..4cf30eb7 100644 --- a/src/graph.c +++ b/src/graph.c @@ -61,7 +61,7 @@ #include "graph.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(). */ @@ -78,11 +78,24 @@ static void mst_kruskal(void) { for splay_each(node_t, n, node_tree) n->status.visited = false; + /* Starting point */ + + for splay_each(edge_t, e, edge_weight_tree) { + if(e->from->status.reachable) { + e->from->status.visited = true; + break; + } + } + /* Add safe edges */ + bool skipped = false; + for splay_each(edge_t, e, edge_weight_tree) { - if(!e->reverse || (e->from->status.visited && e->to->status.visited)) + if(!e->reverse || (e->from->status.visited == e->to->status.visited)) { + skipped = true; continue; + } e->from->status.visited = true; e->to->status.visited = true; @@ -93,8 +106,12 @@ static void mst_kruskal(void) { if(e->reverse->connection) e->reverse->connection->status.mst = true; - logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, - e->to->name, e->weight); + logger(DEBUG_SCARY_THINGS, LOG_DEBUG, " Adding edge %s - %s weight %d", e->from->name, e->to->name, e->weight); + + if(skipped) { + skipped = false; + next = edge_weight_tree->head; + } } } -- 2.20.1