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 * Written by Stephen North
17 * Updated by Emden Gansner
18 * Adapted to gvToolTred(g) by John Ellson
19 */
20
21/*
22 * performs an inplace transitive reduction on a graph
23 */
24
25#include "config.h"
26#include <stdio.h>
27#include "cgraph.h"
28#include "gvc.h"
29
30typedef struct {
31 Agrec_t h;
32 int mark;
33} Agmarknodeinfo_t;
34
35#define MARK(n) (((Agmarknodeinfo_t*)(n->base.data))->mark)
36
37#define agrootof(n) ((n)->root)
38
39static int dfs(Agnode_t * n, Agedge_t * link, int warn)
40{
41 Agedge_t *e;
42 Agedge_t *f;
43 Agraph_t *g = agrootof(n);
44
45 MARK(n) = 1;
46
47 for (e = agfstin(g, n); e; e = f) {
48 f = agnxtin(g, e);
49 if (e == link)
50 continue;
51 if (MARK(agtail(e)))
52 agdelete(g, e);
53 }
54
55 for (e = agfstout(g, n); e; e = agnxtout(g, e)) {
56 if (MARK(aghead(e))) {
57 if (!warn) {
58 warn++;
59 fprintf(stderr,
60 "warning: %s has cycle(s), transitive reduction not unique\n",
61 agnameof(g));
62 fprintf(stderr, "cycle involves edge %s -> %s\n",
63 agnameof(agtail(e)), agnameof(aghead(e)));
64 }
65 } else
66 warn = dfs(aghead(e), AGOUT2IN(e), warn);
67 }
68
69 MARK(n) = 0;
70 return warn;
71}
72
73int gvToolTred(Agraph_t * g)
74{
75 Agnode_t *n;
76 int warn = 0;
77
78 if (agisdirected(g)) {
79 aginit(g, AGNODE, "info", sizeof(Agmarknodeinfo_t), TRUE);
80 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
81 warn = dfs(n, NULL, warn);
82 }
83 agclean(g, AGNODE, "info");
84 } else {
85 fprintf(stderr, "warning: %s is not a directed graph, not attempting tred\n",
86 agnameof(g));
87 }
88 return 0; // FIXME - return proper errors
89}
90