Graphviz  2.41.20170921.2350
comp.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 /* comp.c:
16  * Written by Emden R. Gansner
17  *
18  * Support for "connected components". Components are either connected
19  * or have a port node or have a pinned node.
20  *
21  */
22 
23 /* use PRIVATE interface */
24 #define FDP_PRIVATE 1
25 
26 #include <fdp.h>
27 #include <comp.h>
28 #include <pack.h>
29 #include <assert.h>
30 
31 #define MARK(n) (marks[ND_id(n)])
32 
33 static void dfs(Agraph_t * g, Agnode_t * n, Agraph_t * out, char *marks)
34 {
35  Agedge_t *e;
36  Agnode_t *other;
37 
38  MARK(n) = 1;
39  agsubnode(out,n,1);
40  for (e = agfstedge(g, n); e; e = agnxtedge(g, e, n)) {
41  if ((other = agtail(e)) == n)
42  other = aghead(e);
43  if (!MARK(other))
44  dfs(g, other, out, marks);
45  }
46 }
47 
48 /* findCComp:
49  * Finds generalized connected components of graph g.
50  * This merges all components containing a port node or a pinned node.
51  * Assumes nodes have unique id's in range [0,agnnodes(g)-1].
52  * Components are stored as subgraphs of g, with name sg_<i>.
53  * Returns 0-terminated array of components.
54  * If cnt is non-0, count of components is stored there.
55  * If pinned is non-0, *pinned is set to 1 if there are pinned nodes.
56  * Note that if ports and/or pinned nodes exists, they will all be
57  * in the first component returned by findCComp.
58  */
59 static int C_cnt = 0;
60 graph_t **findCComp(graph_t * g, int *cnt, int *pinned)
61 {
62  node_t *n;
63  graph_t *subg;
64  char name[128];
65  int c_cnt = 0;
66  char *marks;
67  bport_t *pp;
68  graph_t **comps;
69  graph_t **cp;
70  int pinflag = 0;
71 
72 /* fprintf (stderr, "comps of %s starting at %d \n", g->name, c_cnt); */
73  marks = N_NEW(agnnodes(g), char); /* freed below */
74 
75  /* Create component based on port nodes */
76  subg = 0;
77  if ((pp = PORTS(g))) {
78  sprintf(name, "cc%s_%d", agnameof(g), c_cnt++ + C_cnt);
79  subg = agsubg(g, name,1);
80  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
81  GD_alg(subg) = (void *) NEW(gdata);
82  PORTS(subg) = pp;
83  NPORTS(subg) = NPORTS(g);
84  for (; pp->n; pp++) {
85  if (MARK(pp->n))
86  continue;
87  dfs(g, pp->n, subg, marks);
88  }
89  }
90 
91  /* Create/extend component based on pinned nodes */
92  /* Note that ports cannot be pinned */
93  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
94  if (MARK(n))
95  continue;
96  if (ND_pinned(n) != P_PIN)
97  continue;
98  if (!subg) {
99  sprintf(name, "cc%s_%d", agnameof(g), c_cnt++ + C_cnt);
100  subg = agsubg(g, name,1);
101  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE);
102  GD_alg(subg) = (void *) NEW(gdata);
103  }
104  pinflag = 1;
105  dfs(g, n, subg, marks);
106  }
107  if (subg)
108  nodeInduce(subg);
109 
110  /* Pick up remaining components */
111  for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
112  if (MARK(n))
113  continue;
114  sprintf(name, "cc%s+%d", agnameof(g), c_cnt++ + C_cnt);
115  subg = agsubg(g, name,1);
116  agbindrec(subg, "Agraphinfo_t", sizeof(Agraphinfo_t), TRUE); //node custom data
117  GD_alg(subg) = (void *) NEW(gdata);
118  dfs(g, n, subg, marks);
119  nodeInduce(subg);
120  }
121  free(marks);
122  C_cnt += c_cnt;
123 
124  if (cnt)
125  *cnt = c_cnt;
126  if (pinned)
127  *pinned = pinflag;
128  /* freed in layout */
129  comps = cp = N_NEW(c_cnt + 1, graph_t *);
130  for (subg = agfstsubg(g); subg; subg = agnxtsubg(subg)) {
131  *cp++ = subg;
132  c_cnt--;
133  }
134  assert(c_cnt == 0);
135  *cp = 0;
136 
137  return comps;
138 }
graph_t ** findCComp(graph_t *g, int *cnt, int *pinned)
Definition: comp.c:60
#define ND_pinned(n)
Definition: types.h:525
#define N_NEW(n, t)
Definition: memory.h:36
int nodeInduce(Agraph_t *g)
Definition: ccomps.c:718
#define assert(x)
Definition: cghdr.h:47
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
CGRAPH_API Agraph_t * agfstsubg(Agraph_t *g)
Definition: subg.c:72
#define MARK(n)
Definition: comp.c:31
CGRAPH_API Agraph_t * agnxtsubg(Agraph_t *subg)
Definition: subg.c:77
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agraph_t * agsubg(Agraph_t *g, char *name, int cflag)
Definition: subg.c:52
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
#define GD_alg(g)
Definition: types.h:361
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
CGRAPH_API int agnnodes(Agraph_t *g)
Definition: graph.c:162
CGRAPH_API void * agbindrec(void *obj, char *name, unsigned int size, int move_to_front)
Definition: rec.c:86
#define P_PIN
Definition: const.h:285
CGRAPH_API Agnode_t * agsubnode(Agraph_t *g, Agnode_t *n, int createflag)
Definition: node.c:254
#define NEW(t)
Definition: memory.h:35
#define TRUE
Definition: cgraph.h:38