1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
/*************************************************************************
* Copyright (c) 2011 AT&T Intellectual Property
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-v10.html
*
* Contributors: Details at https://graphviz.org
*************************************************************************/
#include <ortho/rawgraph.h>
#include <stddef.h>
#include <util/alloc.h>
#include <util/list.h>
#define UNSCANNED 0
#define SCANNING 1
#define SCANNED 2
rawgraph *make_graph(size_t n) {
rawgraph* g = gv_alloc(sizeof(rawgraph));
g->nvs = n;
g->vertices = gv_calloc(n, sizeof(vertex));
for(size_t i = 0; i < n; ++i) {
g->vertices[i].color = UNSCANNED;
}
return g;
}
void
free_graph(rawgraph* g)
{
for(size_t i = 0; i < g->nvs; ++i)
LIST_FREE(&g->vertices[i].adj_list);
free (g->vertices);
free (g);
}
void insert_edge(rawgraph *g, size_t v1, size_t v2) {
if (!edge_exists(g, v1, v2)) {
LIST_APPEND(&g->vertices[v1].adj_list, v2);
}
}
void remove_redge(rawgraph *g, size_t v1, size_t v2) {
LIST_REMOVE(&g->vertices[v1].adj_list, v2);
LIST_REMOVE(&g->vertices[v2].adj_list, v1);
}
bool edge_exists(rawgraph *g, size_t v1, size_t v2) {
return LIST_CONTAINS(&g->vertices[v1].adj_list, v2);
}
typedef LIST(size_t) int_stack_t;
static int DFS_visit(rawgraph *g, size_t v, int time, int_stack_t *sp) {
vertex* vp;
vp = g->vertices + v;
vp->color = SCANNING;
const adj_list_t adj = vp->adj_list;
time = time + 1;
for (size_t i = 0; i < LIST_SIZE(&adj); ++i) {
const size_t id = LIST_GET(&adj, i);
if(g->vertices[id].color == UNSCANNED)
time = DFS_visit(g, id, time, sp);
}
vp->color = SCANNED;
LIST_PUSH_BACK(sp, v);
return time + 1;
}
void
top_sort(rawgraph* g)
{
int time = 0;
int count = 0;
if (g->nvs == 0) return;
if (g->nvs == 1) {
g->vertices[0].topsort_order = count;
return;
}
int_stack_t sp = {0};
LIST_RESERVE(&sp, g->nvs);
for(size_t i = 0; i < g->nvs; ++i) {
if(g->vertices[i].color == UNSCANNED)
time = DFS_visit(g, i, time, &sp);
}
while (!LIST_IS_EMPTY(&sp)) {
const size_t v = LIST_POP_BACK(&sp);
g->vertices[v].topsort_order = count;
count++;
}
LIST_FREE(&sp);
}
|
