Graphviz  2.41.20170921.2350
acyclic.c
Go to the documentation of this file.
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 
22 {
23  edge_t *f;
24 
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 
32 static void
33 dfs(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 
57 void 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 
#define GD_nlist(g)
Definition: types.h:401
void acyclic(graph_t *g)
Definition: acyclic.c:57
Agedge_t * find_fast_edge(Agnode_t *, Agnode_t *)
Definition: fastgr.c:42
void delete_fast_edge(Agedge_t *)
Definition: fastgr.c:115
#define ND_mark(n)
Definition: types.h:514
Agedge_t * virtual_edge(Agnode_t *, Agnode_t *, Agedge_t *)
Definition: fastgr.c:199
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
void merge_oneway(Agedge_t *, Agedge_t *)
Definition: fastgr.c:334
#define ND_onstack(n)
Definition: types.h:519
#define ND_next(n)
Definition: types.h:517
#define GD_comp(g)
Definition: types.h:366
#define ND_out(n)
Definition: types.h:522
void reverse_edge(edge_t *e)
Definition: acyclic.c:21
#define FALSE
Definition: cgraph.h:35
#define TRUE
Definition: cgraph.h:38