Graphviz 13.0.0~dev.20241212.1010
Loading...
Searching...
No Matches
ccomps.c File Reference
#include <cgraph/cgraph.h>
#include <cgraph/list.h>
#include <common/render.h>
#include <common/utils.h>
#include <limits.h>
#include <pack/pack.h>
#include <stdbool.h>
#include <stdlib.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/gv_ctype.h>
#include <util/prisize_t.h>
Include dependency graph for ccomps.c:

Go to the source code of this file.

Data Structures

struct  stk_t
 
struct  ccgraphinfo_t
 
struct  ccgnodeinfo_t
 
struct  orig_t
 

Macros

#define GRECNAME   "ccgraphinfo"
 
#define NRECNAME   "ccgnodeinfo"
 
#define GD_cc_subg(g)   (((ccgraphinfo_t *)aggetrec(g, GRECNAME, 0))->cc_subg)
 
#define dnodeOf(v)   (((ccgnodeinfo_t *)aggetrec(v, NRECNAME, 0))->ptr.n)
 
#define dnodeSet(v, w)   (((ccgnodeinfo_t *)aggetrec(v, NRECNAME, 0))->ptr.n = w)
 
#define ptrOf(np)   (((ccgnodeinfo_t *)((np)->base.data))->ptr.v)
 
#define nodeOf(np)   (((ccgnodeinfo_t *)((np)->base.data))->ptr.n)
 
#define clustOf(np)   (((ccgnodeinfo_t *)((np)->base.data))->ptr.g)
 
#define clMark(n)   (((ccgnodeinfo_t *)(n->base.data))->mark)
 
#define ORIG_REC   "orig"
 

Functions

static bool marked (const stk_t *stk, Agnode_t *n)
 does n have a mark set?
 
static void mark (const stk_t *stk, Agnode_t *n)
 set a mark on n
 
static void unmark (const stk_t *stk, Agnode_t *n)
 unset a mark on n
 
static void initStk (stk_t *sp, void(*actionfn)(Agnode_t *, void *), bool(*markfn)(Agnode_t *, int))
 
static void freeStk (stk_t *sp)
 
static void push (stk_t *sp, Agnode_t *np)
 
static Agnode_tpop (stk_t *sp)
 
static size_t dfs (Agraph_t *g, Agnode_t *n, void *state, stk_t *stk)
 
static bool isLegal (const char *p)
 
static void insertFn (Agnode_t *n, void *state)
 
static bool markFn (Agnode_t *n, int v)
 
static void setPrefix (agxbuf *xb, const char *pfx)
 
Agraph_t ** pccomps (Agraph_t *g, size_t *ncc, char *pfx, bool *pinned)
 
Agraph_t ** ccomps (Agraph_t *g, size_t *ncc, char *pfx)
 
static void deriveClusters (Agraph_t *dg, Agraph_t *g)
 
static Agraph_tderiveGraph (Agraph_t *g)
 
static void unionNodes (Agraph_t *dg, Agraph_t *g)
 
static bool clMarkFn (Agnode_t *n, int v)
 
Agraph_tmapClust (Agraph_t *cl)
 
static Agraph_tprojectG (Agraph_t *subg, Agraph_t *g, int inCluster)
 
static void subgInduce (Agraph_t *root, Agraph_t *g, int inCluster)
 
static void subGInduce (Agraph_t *g, Agraph_t *out)
 
Agraph_t ** cccomps (Agraph_t *g, size_t *ncc, char *pfx)
 
int isConnected (Agraph_t *g)
 

Macro Definition Documentation

◆ clMark

#define clMark (   n)    (((ccgnodeinfo_t *)(n->base.data))->mark)

Definition at line 257 of file ccomps.c.

◆ clustOf

#define clustOf (   np)    (((ccgnodeinfo_t *)((np)->base.data))->ptr.g)

Definition at line 256 of file ccomps.c.

◆ dnodeOf

#define dnodeOf (   v)    (((ccgnodeinfo_t *)aggetrec(v, NRECNAME, 0))->ptr.n)

Definition at line 250 of file ccomps.c.

◆ dnodeSet

#define dnodeSet (   v,
 
)    (((ccgnodeinfo_t *)aggetrec(v, NRECNAME, 0))->ptr.n = w)

Definition at line 251 of file ccomps.c.

◆ GD_cc_subg

#define GD_cc_subg (   g)    (((ccgraphinfo_t *)aggetrec(g, GRECNAME, 0))->cc_subg)

Definition at line 237 of file ccomps.c.

◆ GRECNAME

#define GRECNAME   "ccgraphinfo"

Definition at line 235 of file ccomps.c.

◆ nodeOf

#define nodeOf (   np)    (((ccgnodeinfo_t *)((np)->base.data))->ptr.n)

Definition at line 255 of file ccomps.c.

◆ NRECNAME

#define NRECNAME   "ccgnodeinfo"

Definition at line 236 of file ccomps.c.

◆ ORIG_REC

#define ORIG_REC   "orig"

Definition at line 364 of file ccomps.c.

◆ ptrOf

#define ptrOf (   np)    (((ccgnodeinfo_t *)((np)->base.data))->ptr.v)

Definition at line 254 of file ccomps.c.

Function Documentation

◆ cccomps()

Agraph_t ** cccomps ( Agraph_t g,
size_t *  ncc,
char *  pfx 
)

Definition at line 439 of file ccomps.c.

References agbindrec(), agclean(), agclose(), agdelete(), agfstnode(), aginit(), agnameof(), agnedges(), agnnodes(), AGNODE, agnxtnode(), AGRAPH, agsubg(), agxbfree(), agxbprint(), agxbuse(), clMarkFn(), deriveGraph(), dfs(), freeStk(), GD_cc_subg, graphviz_node_induce(), GRECNAME, initStk(), insertFn(), marked(), NRECNAME, NULL, out(), PRISIZE_T, setPrefix(), subGInduce(), unionNodes(), and Verbose.

Referenced by doDot().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ ccomps()

Agraph_t ** ccomps ( Agraph_t g,
size_t *  ncc,
char *  pfx 
)

Definition at line 187 of file ccomps.c.

References agbindrec(), agfstnode(), agnnodes(), agnxtnode(), agsubg(), agxbfree(), agxbprint(), agxbuse(), dfs(), freeStk(), initStk(), insertFn(), marked(), markFn(), NULL, out(), PRISIZE_T, setPrefix(), and unmark().

Referenced by circomps(), main(), sfdp_layout(), and twopi_layout().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ clMarkFn()

static bool clMarkFn ( Agnode_t n,
int  v 
)
static

Definition at line 350 of file ccomps.c.

References clMark.

Referenced by cccomps().

Here is the caller graph for this function:

◆ deriveClusters()

static void deriveClusters ( Agraph_t dg,
Agraph_t g 
)
static

Definition at line 264 of file ccomps.c.

References agbindrec(), agfstnode(), agfstsubg(), agnameof(), agnode(), agnxtnode(), agnxtsubg(), clustOf, deriveClusters(), dnodeOf, dnodeSet, is_a_cluster(), and NRECNAME.

Here is the call graph for this function:

◆ deriveGraph()

static Agraph_t * deriveGraph ( Agraph_t g)
static

Definition at line 294 of file ccomps.c.

References agbindrec(), agedge(), agfstnode(), agfstout(), aghead, agnameof(), agnode(), agnxtnode(), agnxtout(), agopen(), Agstrictundirected, deriveClusters(), dnodeOf, dnodeSet, nodeOf, NRECNAME, and NULL.

Here is the call graph for this function:

◆ dfs()

static size_t dfs ( Agraph_t g,
Agnode_t n,
void *  state,
stk_t stk 
)
static

Definition at line 63 of file ccomps.c.

References stk_t::actionfn, agfstedge(), aghead, agnxtedge(), agtail, cnt(), marked(), pop(), and push().

Here is the call graph for this function:

◆ freeStk()

static void freeStk ( stk_t sp)
static

Definition at line 48 of file ccomps.c.

References stk_t::data.

Referenced by cccomps(), ccomps(), isConnected(), and pccomps().

Here is the caller graph for this function:

◆ initStk()

static void initStk ( stk_t sp,
void(*)(Agnode_t *, void *)  actionfn,
bool(*)(Agnode_t *, int)  markfn 
)
static

Definition at line 41 of file ccomps.c.

References stk_t::actionfn, stk_t::data, and stk_t::markfn.

Referenced by cccomps(), ccomps(), isConnected(), and pccomps().

Here is the caller graph for this function:

◆ insertFn()

static void insertFn ( Agnode_t n,
void *  state 
)
static

Definition at line 94 of file ccomps.c.

References agsubnode().

Referenced by cccomps(), ccomps(), and pccomps().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ isConnected()

int isConnected ( Agraph_t g)

Definition at line 508 of file ccomps.c.

References agfstnode(), agnnodes(), agnxtnode(), cnt(), dfs(), freeStk(), initStk(), markFn(), NULL, and unmark().

Here is the call graph for this function:

◆ isLegal()

static bool isLegal ( const char *  p)
static

Definition at line 83 of file ccomps.c.

References gv_isalnum().

Referenced by setPrefix().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ mapClust()

Agraph_t * mapClust ( Agraph_t cl)

Definition at line 366 of file ccomps.c.

References aggetrec(), orig_t::orig, and ORIG_REC.

Referenced by copyCluster(), and copyClusterInfo().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ mark()

static void mark ( const stk_t stk,
Agnode_t n 
)
static

Definition at line 36 of file ccomps.c.

References stk_t::markfn.

Referenced by find_pair_edges(), marktripath(), and push().

Here is the caller graph for this function:

◆ marked()

static bool marked ( const stk_t stk,
Agnode_t n 
)
static

Definition at line 33 of file ccomps.c.

References stk_t::markfn.

Referenced by cccomps(), ccomps(), dfs(), and pccomps().

Here is the caller graph for this function:

◆ markFn()

static bool markFn ( Agnode_t n,
int  v 
)
static

Definition at line 96 of file ccomps.c.

References ND_mark.

Referenced by ccomps(), isConnected(), and pccomps().

Here is the caller graph for this function:

◆ pccomps()

Agraph_t ** pccomps ( Agraph_t g,
size_t *  ncc,
char *  pfx,
bool *  pinned 
)

Definition at line 125 of file ccomps.c.

References agbindrec(), agfstnode(), agnnodes(), agnxtnode(), agsubg(), agxbfree(), agxbprint(), agxbuse(), dfs(), freeStk(), initStk(), insertFn(), isPinned, marked(), markFn(), NULL, out(), PRISIZE_T, setPrefix(), and unmark().

Referenced by neato_layout().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ pop()

static Agnode_t * pop ( stk_t sp)
static

Definition at line 55 of file ccomps.c.

References stk_t::data, and NULL.

◆ projectG()

static Agraph_t * projectG ( Agraph_t subg,
Agraph_t g,
int  inCluster 
)
static

Definition at line 380 of file ccomps.c.

References agbindrec(), agcopyattr(), agfindnode, agfstnode(), agnameof(), agnxtnode(), agsubg(), agsubnode(), graphviz_node_induce(), is_a_cluster(), NULL, orig_t::orig, and ORIG_REC.

Here is the call graph for this function:

◆ push()

static void push ( stk_t sp,
Agnode_t np 
)
static

Definition at line 50 of file ccomps.c.

References stk_t::data, and mark().

Here is the call graph for this function:

◆ setPrefix()

static void setPrefix ( agxbuf xb,
const char *  pfx 
)
static

Definition at line 104 of file ccomps.c.

References agxbput(), and isLegal().

Referenced by cccomps(), ccomps(), and pccomps().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ subGInduce()

static void subGInduce ( Agraph_t g,
Agraph_t out 
)
static

Definition at line 428 of file ccomps.c.

References out(), and subgInduce().

Here is the call graph for this function:

◆ subgInduce()

static void subgInduce ( Agraph_t root,
Agraph_t g,
int  inCluster 
)
static

Definition at line 413 of file ccomps.c.

References agfstsubg(), agnxtsubg(), GD_cc_subg, is_a_cluster(), projectG(), and subgInduce().

Here is the call graph for this function:

◆ unionNodes()

static void unionNodes ( Agraph_t dg,
Agraph_t g 
)
static

Definition at line 334 of file ccomps.c.

References agfstnode(), AGNODE, agnxtnode(), agsubnode(), AGTYPE, clustOf, nodeOf, and ptrOf.

Here is the call graph for this function:

◆ unmark()

static void unmark ( const stk_t stk,
Agnode_t n 
)
static

Definition at line 39 of file ccomps.c.

References stk_t::markfn.

Referenced by ccomps(), isConnected(), and pccomps().

Here is the caller graph for this function: