Graphviz: lib/pack/ccomps.c File Reference

Searching...

No Matches

#include "config.h"
#include <cgraph/cgraph.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/list.h>
#include <util/prisize_t.h>

Include dependency graph for ccomps.c:

Go to the source code of this file.

Data Structures
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
typedef	LIST (Agnode_t *)

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 stk_t	initStk (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)

Variables
	stk_t

Macro Definition Documentation

◆ clMark

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

Definition at line 255 of file ccomps.c.

◆ clustOf

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

Definition at line 254 of file ccomps.c.

◆ dnodeOf

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

Definition at line 248 of file ccomps.c.

◆ dnodeSet

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

Definition at line 249 of file ccomps.c.

◆ GD_cc_subg

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

Definition at line 235 of file ccomps.c.

◆ GRECNAME

#define GRECNAME "ccgraphinfo"

Definition at line 233 of file ccomps.c.

◆ nodeOf

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

Definition at line 253 of file ccomps.c.

◆ NRECNAME

#define NRECNAME "ccgnodeinfo"

Definition at line 234 of file ccomps.c.

◆ ORIG_REC

#define ORIG_REC "orig"

Definition at line 362 of file ccomps.c.

◆ ptrOf

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

Definition at line 252 of file ccomps.c.

Function Documentation

◆ cccomps()

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

Definition at line 437 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(), LIST, LIST_APPEND, LIST_DETACH, LIST_RESERVE, LIST_SIZE, marked(), NRECNAME, NULL, out(), PRISIZE_T, setPrefix(), stk_t, 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 185 of file ccomps.c.

References agbindrec(), agfstnode(), agnnodes(), agnxtnode(), agsubg(), agxbfree(), agxbprint(), agxbuse(), dfs(), freeStk(), initStk(), insertFn(), LIST, LIST_APPEND, LIST_DETACH, LIST_SIZE, marked(), markFn(), NULL, out(), PRISIZE_T, setPrefix(), stk_t, 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 348 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 262 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 292 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 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 LIST_FREE.

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

Here is the caller graph for this function:

◆ initStk()

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

static

Definition at line 43 of file ccomps.c.

References stk_t.

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 506 of file ccomps.c.

References agfstnode(), agnnodes(), agnxtnode(), cnt(), dfs(), freeStk(), initStk(), markFn(), NULL, stk_t, 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:

◆ LIST()

typedef LIST ( Agnode_t * )

Definition at line 26 of file ccomps.c.

◆ mapClust()

Agraph_t * mapClust ( Agraph_t * cl )

Definition at line 364 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 38 of file ccomps.c.

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 35 of file ccomps.c.

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 123 of file ccomps.c.

References agbindrec(), agfstnode(), agnnodes(), agnxtnode(), agsubg(), agxbfree(), agxbprint(), agxbuse(), dfs(), freeStk(), initStk(), insertFn(), isPinned, LIST, LIST_APPEND, LIST_DETACH, LIST_SIZE, marked(), markFn(), NULL, out(), PRISIZE_T, setPrefix(), stk_t, 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 LIST_IS_EMPTY, LIST_POP_BACK, and NULL.

◆ projectG()

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

static

Definition at line 378 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 LIST_PUSH_BACK, 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 426 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 411 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 332 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 41 of file ccomps.c.

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

Here is the caller graph for this function:

Variable Documentation

◆ stk_t

stk_t

Definition at line 32 of file ccomps.c.

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

Data Structures

Macros

Functions

Variables

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()

◆ LIST()

◆ mapClust()

◆ mark()

◆ marked()

◆ markFn()

◆ pccomps()

◆ pop()

◆ projectG()

◆ push()

◆ setPrefix()

◆ subGInduce()

◆ subgInduce()

◆ unionNodes()

◆ unmark()

Variable Documentation

◆ stk_t