1 /* topsort.c (topological sorting of acyclic digraph) */
2
3 /***********************************************************************
4 * This code is part of GLPK (GNU Linear Programming Kit).
5 * Copyright (C) 2010-2016 Free Software Foundation, Inc.
6 * Written by Andrew Makhorin <mao@gnu.org>.
7 *
8 * GLPK is free software: you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * GLPK is distributed in the hope that it will be useful, but WITHOUT
14 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
16 * License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with GLPK. If not, see <http://www.gnu.org/licenses/>.
20 ***********************************************************************/
21
22 #include "env.h"
23 #include "glpk.h"
24
25 /***********************************************************************
26 * NAME
27 *
28 * glp_top_sort - topological sorting of acyclic digraph
29 *
30 * SYNOPSIS
31 *
32 * int glp_top_sort(glp_graph *G, int v_num);
33 *
34 * DESCRIPTION
35 *
36 * The routine glp_top_sort performs topological sorting of vertices of
37 * the specified acyclic digraph.
38 *
39 * The parameter v_num specifies an offset of the field of type int in
40 * the vertex data block, to which the routine stores the vertex number
41 * assigned. If v_num < 0, vertex numbers are not stored.
42 *
43 * The vertices are numbered from 1 to n, where n is the total number
44 * of vertices in the graph. The vertex numbering has the property that
45 * for every arc (i->j) in the graph the condition num(i) < num(j)
46 * holds. Special case num(i) = 0 means that vertex i is not assigned a
47 * number, because the graph is *not* acyclic.
48 *
49 * RETURNS
50 *
51 * If the graph is acyclic and therefore all the vertices have been
52 * assigned numbers, the routine glp_top_sort returns zero. Otherwise,
53 * if the graph is not acyclic, the routine returns the number of
54 * vertices which have not been numbered, i.e. for which num(i) = 0. */
55
top_sort(glp_graph * G,int num[])56 static int top_sort(glp_graph *G, int num[])
57 { glp_arc *a;
58 int i, j, cnt, top, *stack, *indeg;
59 /* allocate working arrays */
60 indeg = xcalloc(1+G->nv, sizeof(int));
61 stack = xcalloc(1+G->nv, sizeof(int));
62 /* determine initial indegree of each vertex; push into the stack
63 the vertices having zero indegree */
64 top = 0;
65 for (i = 1; i <= G->nv; i++)
66 { num[i] = indeg[i] = 0;
67 for (a = G->v[i]->in; a != NULL; a = a->h_next)
68 indeg[i]++;
69 if (indeg[i] == 0)
70 stack[++top] = i;
71 }
72 /* assign numbers to vertices in the sorted order */
73 cnt = 0;
74 while (top > 0)
75 { /* pull vertex i from the stack */
76 i = stack[top--];
77 /* it has zero indegree in the current graph */
78 xassert(indeg[i] == 0);
79 /* so assign it a next number */
80 xassert(num[i] == 0);
81 num[i] = ++cnt;
82 /* remove vertex i from the current graph, update indegree of
83 its adjacent vertices, and push into the stack new vertices
84 whose indegree becomes zero */
85 for (a = G->v[i]->out; a != NULL; a = a->t_next)
86 { j = a->head->i;
87 /* there exists arc (i->j) in the graph */
88 xassert(indeg[j] > 0);
89 indeg[j]--;
90 if (indeg[j] == 0)
91 stack[++top] = j;
92 }
93 }
94 /* free working arrays */
95 xfree(indeg);
96 xfree(stack);
97 return G->nv - cnt;
98 }
99
glp_top_sort(glp_graph * G,int v_num)100 int glp_top_sort(glp_graph *G, int v_num)
101 { glp_vertex *v;
102 int i, cnt, *num;
103 if (v_num >= 0 && v_num > G->v_size - (int)sizeof(int))
104 xerror("glp_top_sort: v_num = %d; invalid offset\n", v_num);
105 if (G->nv == 0)
106 { cnt = 0;
107 goto done;
108 }
109 num = xcalloc(1+G->nv, sizeof(int));
110 cnt = top_sort(G, num);
111 if (v_num >= 0)
112 { for (i = 1; i <= G->nv; i++)
113 { v = G->v[i];
114 memcpy((char *)v->data + v_num, &num[i], sizeof(int));
115 }
116 }
117 xfree(num);
118 done: return cnt;
119 }
120
121 /* eof */
122