1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14 /* Implements graph.h */
15
16#include "config.h"
17
18#include "rawgraph.h"
19#include "memory.h"
20#include "intset.h"
21
22#define UNSCANNED 0
23#define SCANNING 1
24#define SCANNED 2
25
26rawgraph*
27make_graph(int n)
28{
29 int i;
30 rawgraph* g = NEW(rawgraph);
31 g->nvs = n;
32 g->vertices = N_NEW(n, vertex);
33 for(i=0;i<n;i++) {
34 g->vertices[i].adj_list = openIntSet ();
35 g->vertices[i].color = UNSCANNED;
36 }
37 return g;
38}
39
40void
41free_graph(rawgraph* g)
42{
43 int i;
44 for(i=0;i<g->nvs;i++)
45 dtclose(g->vertices[i].adj_list);
46 free (g->vertices);
47 free (g);
48}
49
50void
51insert_edge(rawgraph* g, int v1, int v2)
52{
53 intitem obj;
54
55 obj.id = v2;
56 dtinsert(g->vertices[v1].adj_list,&obj);
57}
58
59void
60remove_redge(rawgraph* g, int v1, int v2)
61{
62 intitem obj;
63 obj.id = v2;
64 dtdelete (g->vertices[v1].adj_list, &obj);
65 obj.id = v1;
66 dtdelete (g->vertices[v2].adj_list, &obj);
67}
68
69int
70edge_exists(rawgraph* g, int v1, int v2)
71{
72 return (dtmatch (g->vertices[v1].adj_list, &v2) != 0);
73}
74
75typedef struct {
76 int top;
77 int* vals;
78} stack;
79
80static stack*
81mkStack (int i)
82{
83 stack* sp = NEW(stack);
84 sp->vals = N_NEW(i,int);
85 sp->top = -1;
86 return sp;
87}
88
89static void
90freeStack (stack* s)
91{
92 free (s->vals);
93 free (s);
94}
95
96static void
97pushStack (stack* s, int i)
98{
99 s->top++;
100 s->vals[s->top] = i;
101}
102
103static int
104popStack (stack* s)
105{
106 int v;
107
108 if (s->top == -1) return -1;
109 v = s->vals[s->top];
110 s->top--;
111 return v;
112}
113
114static int
115DFS_visit(rawgraph* g, int v, int time, stack* sp)
116{
117 Dt_t* adj;
118 Dtlink_t* link;
119 int id;
120 vertex* vp;
121
122 vp = g->vertices + v;
123 vp->color = SCANNING;
124 /* g->vertices[v].d = time; */
125 adj = vp->adj_list;
126 time = time + 1;
127
128 for(link = dtflatten (adj); link; link = dtlink(adj,link)) {
129 id = ((intitem*)dtobj(adj,link))->id;
130 if(g->vertices[id].color == UNSCANNED)
131 time = DFS_visit(g, id, time, sp);
132 }
133 vp->color = SCANNED;
134 /* g->vertices[v].f = time; */
135 pushStack (sp, v);
136 return (time + 1);
137}
138
139void
140top_sort(rawgraph* g)
141{
142 int i, v;
143 int time = 0;
144 int count = 0;
145 stack* sp;
146
147 if (g->nvs == 0) return;
148 if (g->nvs == 1) {
149 g->vertices[0].topsort_order = count;
150 return;
151 }
152
153 sp = mkStack (g->nvs);
154 for(i=0;i<g->nvs;i++) {
155 if(g->vertices[i].color == UNSCANNED)
156 time = DFS_visit(g, i, time, sp);
157 }
158 while((v = popStack(sp)) >= 0) {
159 g->vertices[v].topsort_order = count;
160 count++;
161 }
162 freeStack (sp);
163}
164