53cf6a99f8b887da5ef4f62ba3fbff866012d165
[tinc] / 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 }