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
15/*
16 * Break cycles in a directed graph by depth-first search.
17 */
18
19#include "dot.h"
20
21void reverse_edge(edge_t * e)
22{
23 edge_t *f;
24
25 delete_fast_edge(e);
26 if ((f = find_fast_edge(aghead(e), agtail(e))))
27 merge_oneway(e, f);
28 else
29 virtual_edge(aghead(e), agtail(e), e);
30}
31
32static void
33dfs(node_t * n)
34{
35 int i;
36 edge_t *e;
37 node_t *w;
38
39 if (ND_mark(n))
40 return;
41 ND_mark(n) = TRUE;
42 ND_onstack(n) = TRUE;
43 for (i = 0; (e = ND_out(n).list[i]); i++) {
44 w = aghead(e);
45 if (ND_onstack(w)) {
46 reverse_edge(e);
47 i--;
48 } else {
49 if (ND_mark(w) == FALSE)
50 dfs(w);
51 }
52 }
53 ND_onstack(n) = FALSE;
54}
55
56
57void acyclic(graph_t * g)
58{
59 int c;
60 node_t *n;
61
62 for (c = 0; c < GD_comp(g).size; c++) {
63 GD_nlist(g) = GD_comp(g).list[c];
64 for (n = GD_nlist(g); n; n = ND_next(n))
65 ND_mark(n) = FALSE;
66 for (n = GD_nlist(g); n; n = ND_next(n))
67 dfs(n);
68 }
69}
70
71