Graphviz  2.41.20170921.2350
gvtool_tred.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  * 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 
30 typedef struct {
32  int mark;
34 
35 #define MARK(n) (((Agmarknodeinfo_t*)(n->base.data))->mark)
36 
37 #define agrootof(n) ((n)->root)
38 
39 static 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 
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 }
CGRAPH_API void agclean(Agraph_t *g, int kind, char *rec_name)
Definition: rec.c:238
CGRAPH_API Agedge_t * agfstin(Agraph_t *g, Agnode_t *n)
Definition: edge.c:56
int gvToolTred(graph_t *g)
Definition: gvtool_tred.c:73
CGRAPH_API int agisdirected(Agraph_t *g)
Definition: graph.c:182
CGRAPH_API int agdelete(Agraph_t *g, void *obj)
Definition: obj.c:16
CGRAPH_API Agedge_t * agfstout(Agraph_t *g, Agnode_t *n)
Definition: edge.c:25
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
CGRAPH_API void aginit(Agraph_t *g, int kind, char *rec_name, int rec_size, int move_to_front)
Definition: rec.c:198
Definition: cgraph.h:83
#define AGNODE
Definition: cgraph.h:101
#define AGOUT2IN(e)
Definition: cgraph.h:402
#define NULL
Definition: logic.h:39
CGRAPH_API Agedge_t * agnxtin(Agraph_t *g, Agedge_t *e)
Definition: edge.c:70
#define MARK(n)
Definition: gvtool_tred.c:35
#define agrootof(n)
Definition: gvtool_tred.c:37
CGRAPH_API Agedge_t * agnxtout(Agraph_t *g, Agedge_t *e)
Definition: edge.c:40
#define TRUE
Definition: cgraph.h:38