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.
#include "graph.h"
/* Implementation of Kruskal's algorithm.
#include "graph.h"
/* Implementation of Kruskal's algorithm.
Please note that sorting on weight is already done by add_edge().
*/
Please note that sorting on weight is already done by add_edge().
*/
for splay_each(node_t, n, node_tree)
n->status.visited = false;
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;
+ }
+ }
+
+ bool skipped = false;
+
for splay_each(edge_t, e, edge_weight_tree) {
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;
e->from->status.visited = true;
e->to->status.visited = true;
e->from->status.visited = true;
e->to->status.visited = true;
if(e->reverse->connection)
e->reverse->connection->status.mst = true;
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;
+ }