Graphviz 13.1.0~dev.20250626.0830
Loading...
Searching...
No Matches
decomp.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11
12/*
13 * Decompose finds the connected components of a graph.
14 * It searches the temporary edges and ignores non-root nodes.
15 * The roots of the search are the real nodes of the graph,
16 * but any virtual nodes discovered are also included in the
17 * component.
18 */
19
20#include <dotgen/dot.h>
21#include <stddef.h>
22#include <stdint.h>
23#include <util/alloc.h>
24#include <util/list.h>
25
27static size_t Cmark;
28
29static void
34
35static void
37{
38 ND_mark(n) = Cmark;
39 if (Last_node) {
40 ND_prev(n) = Last_node;
41 ND_next(Last_node) = n;
42 } else {
43 ND_prev(n) = NULL;
44 GD_nlist(g) = n;
45 }
46 Last_node = n;
47 ND_next(n) = NULL;
48}
49
50static void
52{
53 size_t i = GD_comp(g).size++;
54 GD_comp(g).list = gv_recalloc(GD_comp(g).list, GD_comp(g).size - 1,
55 GD_comp(g).size, sizeof(node_t *));
56 GD_comp(g).list[i] = GD_nlist(g);
57}
58
59DEFINE_LIST(node_stack, node_t *)
60
61static void push(node_stack_t *sp, node_t *np) {
62 ND_mark(np) = Cmark + 1;
63 node_stack_push_back(sp, np);
64}
65
66static node_t *pop(node_stack_t *sp) {
67
68 if (node_stack_is_empty(sp)) {
69 return NULL;
70 }
71
72 return node_stack_pop_back(sp);
73}
74
75/* iterative dfs for components.
76 * We process the edges in reverse order of the recursive version to maintain
77 * the processing order of the nodes.
78 * Since are using a stack, we need to indicate nodes on the stack. Nodes unprocessed
79 * in this call to decompose will have mark < Cmark; processed nodes will have mark=Cmark;
80 * so we use mark = Cmark+1 to indicate nodes on the stack.
81 */
82static void search_component(node_stack_t *stk, graph_t *g, node_t *n) {
83 node_t *other;
84
85 push(stk, n);
86 while ((n = pop(stk))) {
87 if (ND_mark(n) == Cmark) continue;
88 add_to_component(g, n);
89 elist vec[] = {ND_flat_in(n), ND_flat_out(n), ND_in(n), ND_out(n)};
90
91 for (size_t c = 0; c < sizeof(vec) / sizeof(vec[0]); ++c) {
92 if (vec[c].list && vec[c].size != 0) {
93 for (size_t i = vec[c].size - 1; i != SIZE_MAX; i--) {
94 edge_t *const e = vec[c].list[i];
95 if ((other = aghead(e)) == n)
96 other = agtail(e);
97 if (ND_mark(other) != Cmark && other == UF_find(other))
98 push(stk, other);
99 }
100 }
101 }
102 }
103}
104
105void decompose(graph_t * g, int pass)
106{
107 graph_t *subg;
108 node_t *n, *v;
109 node_stack_t stk = {0};
110
111 if (++Cmark == 0)
112 Cmark = 1;
113 GD_comp(g).size = 0;
114 for (n = agfstnode(g); n; n = agnxtnode(g, n)) {
115 v = n;
116 if (pass > 0 && (subg = ND_clust(v)))
117 v = GD_rankleader(subg)[ND_rank(v)];
118 else if (v != UF_find(v))
119 continue;
120 if (ND_mark(v) != Cmark) {
122 search_component(&stk, g, v);
123 end_component(g);
124 }
125 }
126 node_stack_free(&stk);
127}
Memory allocation wrappers that exit on failure.
static void * gv_recalloc(void *ptr, size_t old_nmemb, size_t new_nmemb, size_t size)
Definition alloc.h:73
static Agnode_t * pop(void)
Definition ccomps.c:221
node_t * UF_find(node_t *n)
Definition utils.c:100
static void begin_component(graph_t *g)
Definition decomp.c:30
void decompose(graph_t *g, int pass)
Definition decomp.c:105
static void add_to_component(graph_t *g, node_t *n)
Definition decomp.c:36
static void end_component(graph_t *g)
Definition decomp.c:51
static void search_component(node_stack_t *stk, graph_t *g, node_t *n)
Definition decomp.c:82
static size_t Cmark
Definition decomp.c:27
static void push(node_stack_t *sp, node_t *np)
Definition decomp.c:61
static node_t * Last_node
Definition decomp.c:26
#define SIZE_MAX
Definition gmlscan.c:347
node NULL
Definition grammar.y:181
#define agtail(e)
Definition cgraph.h:988
#define aghead(e)
Definition cgraph.h:989
#define GD_nlist(g)
Definition types.h:393
#define GD_comp(g)
Definition types.h:362
#define GD_rankleader(g)
Definition types.h:396
#define ND_rank(n)
Definition types.h:523
#define ND_prev(n)
Definition types.h:521
Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition node.c:48
Agnode_t * agfstnode(Agraph_t *g)
Definition node.c:41
#define ND_next(n)
Definition types.h:510
#define ND_clust(n)
Definition types.h:489
#define ND_flat_out(n)
Definition types.h:493
#define ND_flat_in(n)
Definition types.h:492
#define ND_in(n)
Definition types.h:501
#define ND_out(n)
Definition types.h:515
#define ND_mark(n)
Definition acyclic.c:28
#define DEFINE_LIST(name, type)
Definition list.h:22
graph or subgraph
Definition cgraph.h:424
Definition types.h:251
edge_t ** list
Definition types.h:252