git.meshlink.io Git - meshlink/blob - src/graph.c

   1 /*
   2     graph.c -- graph algorithms
   3     Copyright (C) 2001 Guus Sliepen <guus@sliepen.warande.net>,
   4                   2001 Ivo Timmermans <itimmermans@bigfoot.com>
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  19
  20     $Id: graph.c,v 1.1.2.4 2001/10/30 12:59:12 guus Exp $
  21 */
  22
  23 /* We need to generate two trees from the graph:
  24
  25    1. A minimum spanning tree for broadcasts,
  26    2. A single-source shortest path tree for unicasts.
  27
  28    Actually, the first one alone would suffice but would make unicast packets
  29    take longer routes than necessary.
  30
  31    For the MST algorithm we can choose from Prim's or Kruskal's. I personally
  32    favour Kruskal's, because we make an extra AVL tree of edges sorted on
  33    weights (metric). That tree only has to be updated when an edge is added or
  34    removed, and during the MST algorithm we just have go linearly through that
  35    tree, adding safe edges until #edges = #nodes - 1. The implementation here
  36    however is not so fast, because I tried to avoid having to make a forest and
  37    merge trees.
  38
  39    For the SSSP algorithm Dijkstra's seems to be a nice choice. Currently a
  40    simple breadth-first search is presented here.
  41 */
  42
  43 #include <syslog.h>
  44 #include "config.h"
  45 #include <string.h>
  46
  47 #include <avl_tree.h>
  48
  49 #include "node.h"
  50 #include "edge.h"
  51 #include "connection.h"
  52
  53 #include "system.h"
  54
  55 /* Implementation of Kruskal's algorithm.
  56    Running time: O(EN)
  57    Please note that sorting on weight is already done by add_edge().
  58 */
  59
  60 void mst_kruskal(void)
  61 {
  62   avl_node_t *node;
  63   edge_t *e;
  64   node_t *n;
  65   connection_t *c;
  66   int nodes = 0;
  67   int safe_edges = 0;
  68   int skipped;
  69
  70   /* Clear visited status on nodes */
  71
  72   for(node = node_tree->head; node; node = node->next)
  73     {
  74       n = (node_t *)node->data;
  75       n->status.visited = 0;
  76       nodes++;
  77     }
  78
  79   /* Starting point */
  80
  81   ((edge_t *)edge_weight_tree->head->data)->from->status.visited = 1;
  82
  83   /* Clear MST status on connections */
  84
  85   for(node = connection_tree->head; node; node = node->next)
  86     {
  87       c = (connection_t *)node->data;
  88       c->status.mst = 0;
  89     }
  90
  91   /* Add safe edges */
  92
  93   while(safe_edges < nodes - 1)
  94   for(skipped = 0, node = edge_weight_tree->head; node; node = node->next)
  95     {
  96       e = (edge_t *)node->data;
  97
  98       if(e->from->status.visited == e->to->status.visited)
  99         {
 100           skipped = 1;
 101           continue;
 102         }
 103
 104       e->from->status.visited = 1;
 105       e->to->status.visited = 1;
 106       if(e->connection)
 107         e->connection->status.mst = 1;
 108
 109       safe_edges++;
 110
 111       if(skipped)
 112         break;
 113     }
 114 }
 115
 116 /* Implementation of a simple breadth-first search algorithm.
 117    Running time: O(E)
 118 */
 119
 120 void sssp_bfs(void)
 121 {
 122   avl_node_t *node, *from, *next, *to;
 123   edge_t *e;
 124   node_t *n, *check;
 125   avl_tree_t *todo_tree;
 126
 127   todo_tree = avl_alloc_tree(NULL, NULL);
 128
 129   /* Clear visited status on nodes */
 130
 131   for(node = node_tree->head; node; node = node->next)
 132     {
 133       n = (node_t *)node->data;
 134       n->status.visited = 0;
 135     }
 136
 137   /* Begin with myself */
 138
 139   myself->status.visited = 1;
 140   myself->nexthop = myself;
 141   myself->via = myself;
 142   node = avl_alloc_node();
 143   node->data = myself;
 144   avl_insert_top(todo_tree, node);
 145
 146   /* Loop while todo_tree is filled */
 147
 148   while(todo_tree->head)
 149     {
 150       for(from = todo_tree->head; from; from = next)
 151         {
 152           next = from->next;
 153           n = (node_t *)from->data;
 154
 155           for(to = n->edge_tree->head; to; to = to->next)
 156             {
 157               e = (edge_t *)to->data;
 158
 159               if(e->from == n)
 160                 check = e->to;
 161               else
 162                 check = e->from;
 163
 164               if(!check->status.visited)
 165                 {
 166                   check->status.visited = 1;
 167                   check->nexthop = (n->nexthop == myself) ? check : n->nexthop;
 168                   check->via = check; /* FIXME: only if !(e->options & INDIRECT), otherwise use n->via */
 169                   node = avl_alloc_node();
 170                   node->data = check;
 171                   avl_insert_before(todo_tree, from, node);
 172                 }
 173             }
 174
 175            avl_delete_node(todo_tree, from);
 176         }
 177     }
 178
 179   avl_free_tree(todo_tree);
 180 }