Graphviz: lib/pack/ccomps.c File Reference

Searching...

No Matches

#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_t *	pop (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_t *	deriveGraph (Agraph_t *g)

static void	unionNodes (Agraph_t dg, Agraph_t g)

static bool	clMarkFn (Agnode_t *n, int v)

Agraph_t *	mapClust (Agraph_t *cl)

static Agraph_t *	projectG (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,
		w
	)	(((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:

Data Structures

Macros

Functions

Macro Definition Documentation

◆ clMark

◆ clustOf

◆ dnodeOf

◆ dnodeSet

◆ GD_cc_subg

◆ GRECNAME

◆ nodeOf

◆ NRECNAME

◆ ORIG_REC

◆ ptrOf

Function Documentation

◆ cccomps()

◆ ccomps()

◆ clMarkFn()

◆ deriveClusters()

◆ deriveGraph()

◆ dfs()

◆ freeStk()

◆ initStk()

◆ insertFn()

◆ isConnected()

◆ isLegal()

◆ mapClust()

◆ mark()

◆ marked()

◆ markFn()

◆ pccomps()

◆ pop()

◆ projectG()

◆ push()

◆ setPrefix()

◆ subGInduce()

◆ subgInduce()

◆ unionNodes()

◆ unmark()