Graphviz: cmd/tools/ccomps.c File Reference

Searching...

No Matches

connected components filter for graphs More...

#include <assert.h>
#include <cgraph/cgraph.h>
#include <cgraph/ingraphs.h>
#include <common/render.h>
#include <common/utils.h>
#include <getopt.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/gv_ctype.h>
#include <util/list.h>
#include <util/prisize_t.h>
#include <util/strview.h>
#include <util/unreachable.h>

Include dependency graph for ccomps.c:

Go to the source code of this file.

Data Structures
struct	graphinfo_t

struct	nodeinfo_t

Macros
#define	GD_cc_subg(g) (((graphinfo_t *)(g->base.data))->cc_subg)

#define	Node_mark(n) (((nodeinfo_t *)(n->base.data))->mark)

#define	ND_ptr(n) (((nodeinfo_t *)(n->base.data))->ptr)

#define	ND_dn(n) ((Agnode_t *)ND_ptr(n))

#define	Node_clust(n) ((Agraph_t *)ND_ptr(n))

#define	PFX1 "%s_cc"

#define	PFX2 "%s_cc_%" PRISIZE_T

Enumerations
enum	{ INTERNAL , EXTERNAL , SILENT , EXTRACT }

enum	{ BY_INDEX = 1 , BY_SIZE = 2 }

Functions
static void	usage (int v)

static void	split (void)

static void	init (int argc, char *argv[])

static void	push (Agnode_t *np)

static Agnode_t *	pop (void)

static int	dfs (Agraph_t g, Agnode_t n, Agraph_t *out)

static char *	getName (void)

static void	gwrite (Agraph_t *g)

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)

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)
	add all nodes in cluster nodes of `dg` to `g`

static int	cmp (const void x, const void y)

static void	printSorted (Agraph_t *root, size_t c_cnt)

static int	processClusters (Agraph_t g, char graphName)
	return 0 if graph is connected

static void	bindGraphinfo (Agraph_t *g)

static int	process (Agraph_t g, char graphName)
	return 0 if graph is connected

static char *	chkGraphName (Agraph_t *g)

int	main (int argc, char *argv[])

Variables
static char **	Inputs

static bool	verbose = false

static enum { ... }	printMode = INTERNAL

static bool	useClusters = false

static bool	doEdges = true
	induce edges

static bool	doAll = true
	induce subgraphs

static char *	suffix = 0

static char *	outfile = 0

static strview_t	rootpath

static int	sufcnt = 0

static bool	sorted = false

static int	sortIndex = 0

static int	sortFinal

static int	x_index = -1

static int	x_final = -1

static enum { ... }	x_mode

static char *	x_node

static char *	useString

static node_stack_t	Stk

Macro Definition Documentation

◆ GD_cc_subg

#define GD_cc_subg ( g ) (((graphinfo_t *)(g->base.data))->cc_subg)

Definition at line 51 of file ccomps.c.

◆ ND_dn

#define ND_dn ( n ) ((Agnode_t *)ND_ptr(n))

Definition at line 54 of file ccomps.c.

◆ ND_ptr

#define ND_ptr ( n ) (((nodeinfo_t *)(n->base.data))->ptr)

Definition at line 53 of file ccomps.c.

◆ Node_clust

#define Node_clust ( n ) ((Agraph_t *)ND_ptr(n))

Definition at line 55 of file ccomps.c.

◆ Node_mark

#define Node_mark ( n ) (((nodeinfo_t *)(n->base.data))->mark)

Definition at line 52 of file ccomps.c.

◆ PFX1

#define PFX1 "%s_cc"

Definition at line 329 of file ccomps.c.

◆ PFX2

#define PFX2 "%s_cc_%" PRISIZE_T

Definition at line 330 of file ccomps.c.

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Enumerator
INTERNAL	all components need to be generated before output
EXTERNAL
SILENT
EXTRACT

Definition at line 59 of file ccomps.c.

◆ anonymous enum

anonymous enum

Enumerator
BY_INDEX
BY_SIZE

Definition at line 77 of file ccomps.c.

Function Documentation

◆ bindGraphinfo()

static void bindGraphinfo ( Agraph_t * g )

static

Definition at line 599 of file ccomps.c.

References agfstsubg(), aginit(), agnxtsubg(), AGRAPH, and bindGraphinfo().

Referenced by bindGraphinfo(), and process().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ chkGraphName()

static char * chkGraphName ( Agraph_t * g )

static

Definition at line 719 of file ccomps.c.

References agnameof(), agxbprint(), and agxbuse().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ cmp()

static int cmp	(	const void *	x,
		const void *	y
	)

static

Definition at line 404 of file ccomps.c.

References agnnodes().

Referenced by printSorted().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ deriveClusters()

static void deriveClusters	(	Agraph_t *	dg,
		Agraph_t *	g
	)

static

Definition at line 336 of file ccomps.c.

References agbindrec(), agfstnode(), agfstsubg(), agnameof(), agnode(), agnxtnode(), agnxtsubg(), deriveClusters(), is_a_cluster(), ND_dn, and ND_ptr.

Referenced by deriveClusters(), and deriveGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ deriveGraph()

static Agraph_t * deriveGraph ( Agraph_t * g )

static

Definition at line 361 of file ccomps.c.

References agbindrec(), agedge(), agfstnode(), agfstout(), aghead, agnameof(), agnode(), agnxtnode(), agnxtout(), agopen(), Agstrictundirected, deriveClusters(), ND_dn, ND_ptr, and NULL.

Referenced by cccomps(), and processClusters().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs()

static int dfs	(	Agraph_t *	g,
		Agnode_t *	n,
		Agraph_t *	out
	)

static

Definition at line 228 of file ccomps.c.

References agfstedge(), aghead, agnxtedge(), agsubnode(), agtail, cnt(), Node_mark, out(), pop(), and push().

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

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getName()

static char * getName ( void )

static

Definition at line 247 of file ccomps.c.

References agxbdisown(), agxbprint(), agxbput(), strview_t::data, outfile, rootpath, strview_t::size, sufcnt, and suffix.

Referenced by gwrite(), and gwrite().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ gwrite()

static void gwrite ( Agraph_t * g )

static

Definition at line 263 of file ccomps.c.

References agwrite(), free(), getName(), graphviz_exit(), and outfile.

Referenced by printSorted(), process(), and processClusters().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init()

static void init	(	int	argc,
		char *	argv[]
	)

static

Definition at line 110 of file ccomps.c.

References BY_INDEX, BY_SIZE, doAll, doEdges, EXTERNAL, EXTRACT, gv_isdigit(), Inputs, INTERNAL, outfile, printMode, SILENT, sorted, sortFinal, sortIndex, split(), UNREACHABLE, usage, useClusters, verbose, x_final, x_index, x_mode, and x_node.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 730 of file ccomps.c.

References agclose(), chkGraphName(), graphviz_exit(), init(), Inputs, newIngraph(), nextGraph(), process(), and Stk.

Here is the call graph for this function:

◆ pop()

static Agnode_t * pop ( void )

static

Definition at line 221 of file ccomps.c.

References NULL, and Stk.

Referenced by closesubg(), closesubg(), construct_graph(), dfs(), dfs(), dfs(), freestack(), freestack(), genTree(), and search_component().

Here is the caller graph for this function:

◆ printSorted()

static void printSorted	(	Agraph_t *	root,
		size_t	c_cnt
	)

static

Definition at line 428 of file ccomps.c.

References agfstsubg(), agnameof(), agnnodes(), agnxtsubg(), BY_INDEX, BY_SIZE, cmp(), doAll, free(), GD_cc_subg, gv_calloc(), gwrite(), sortFinal, sortIndex, subGInduce(), and x_mode.

Referenced by process(), and processClusters().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ process()

static int process	(	Agraph_t *	g,
		char *	graphName
	)

static

Definition at line 607 of file ccomps.c.

References agdelete(), agfindnode, agfstnode(), aginit(), agnameof(), agnedges(), agnnodes(), AGNODE, agnxtnode(), AGRAPH, agsubg(), agxbfree(), agxbprint(), agxbuse(), bindGraphinfo(), BY_INDEX, BY_SIZE, dfs(), doAll, doEdges, EXTERNAL, EXTRACT, GD_cc_subg, graphName, graphviz_node_induce(), gwrite(), INTERNAL, Node_mark, out(), PFX1, PFX2, printMode, printSorted(), PRISIZE_T, processClusters(), sorted, subGInduce(), useClusters, verbose, x_final, x_index, x_mode, and x_node.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ processClusters()

static int processClusters	(	Agraph_t *	g,
		char *	graphName
	)

static

Definition at line 489 of file ccomps.c.

References agclose(), agdelete(), agfindnode, agfstnode(), aginit(), agnameof(), agnedges(), agnnodes(), agnxtnode(), AGRAPH, agsubg(), agxbfree(), agxbprint(), agxbuse(), BY_INDEX, BY_SIZE, deriveGraph(), dfs(), doAll, doEdges, EXTERNAL, EXTRACT, GD_cc_subg, graphName, graphviz_node_induce(), gwrite(), INTERNAL, ND_dn, Node_mark, out(), PFX1, PFX2, printMode, printSorted(), PRISIZE_T, sorted, subGInduce(), unionNodes(), verbose, x_final, x_index, x_mode, and x_node.

Referenced by process().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ projectG()

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

static

Definition at line 287 of file ccomps.c.

References agcopyattr(), agfindnode, agfstnode(), agnameof(), agnxtnode(), agsubg(), agsubnode(), doEdges, and graphviz_node_induce().

Referenced by subgInduce().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ push()

static void push ( Agnode_t * np )

static

Definition at line 216 of file ccomps.c.

References Node_mark, and Stk.

Referenced by dfs(), and dfs().

Here is the caller graph for this function:

◆ split()

static void split ( void )

static

Definition at line 99 of file ccomps.c.

References strview_t::data, outfile, rootpath, strview(), and suffix.

Referenced by init(), init(), and Block::splitBetween().

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

References out(), and subgInduce().

Referenced by cccomps(), printSorted(), process(), and processClusters().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ subgInduce()

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

static

Definition at line 314 of file ccomps.c.

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

Referenced by subGInduce(), and subgInduce().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ unionNodes()

static void unionNodes	(	Agraph_t *	dg,
		Agraph_t *	g
	)

static

Definition at line 392 of file ccomps.c.

References agfstnode(), AGNODE, agnxtnode(), agsubnode(), AGTYPE, ND_dn, ND_ptr, and Node_clust.

Referenced by cccomps(), and processClusters().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ usage()

static void usage ( int v )

static

Definition at line 94 of file ccomps.c.

References graphviz_exit(), and useString.

Here is the call graph for this function:

Variable Documentation

◆ doAll

bool doAll = true

static

Definition at line 67 of file ccomps.c.

Referenced by init(), newPos(), printSorted(), process(), processClusters(), and vAdjust().

◆ doEdges

bool doEdges = true

static

Definition at line 66 of file ccomps.c.

Referenced by init(), neato_layout(), process(), processClusters(), and projectG().

◆ Inputs

char** Inputs

static

Definition at line 57 of file ccomps.c.

Referenced by init(), and main().

◆ outfile

char* outfile = 0

static

Definition at line 69 of file ccomps.c.

Referenced by getName(), gwrite(), init(), and split().

◆ []

enum { ... } printMode

Referenced by init(), process(), and processClusters().

◆ rootpath

strview_t rootpath

static

Definition at line 70 of file ccomps.c.

Referenced by getName(), and split().

◆ sorted

bool sorted = false

static

Definition at line 72 of file ccomps.c.

Referenced by init(), process(), and processClusters().

◆ sortFinal

int sortFinal

static

Definition at line 74 of file ccomps.c.

Referenced by init(), and printSorted().

◆ sortIndex

int sortIndex = 0

static

Definition at line 73 of file ccomps.c.

Referenced by init(), and printSorted().

◆ Stk

node_stack_t Stk

static

Definition at line 214 of file ccomps.c.

Referenced by main(), pop(), and push().

◆ sufcnt

int sufcnt = 0

static

Definition at line 71 of file ccomps.c.

Referenced by getName().

◆ suffix

char* suffix = 0

static

Definition at line 68 of file ccomps.c.

Referenced by getName(), and split().

◆ useClusters

bool useClusters = false

static

Definition at line 65 of file ccomps.c.

Referenced by Import_coord_clusters_from_dot(), init(), process(), and subgInduce().

◆ useString

char* useString

static

Initial value:

=
    "Usage: ccomps [-svenCx?] [-X[#%]s[-f]] [-o<out template>] <files>\n\
  -s - silent\n\
  -x - external\n\
  -X - extract component\n\
  -C - use clusters\n\
  -e - do not induce edges\n\
  -n - do not induce subgraphs\n\
  -v - verbose\n\
  -o - output file template\n\
  -z - sort by size, largest first\n\
  -? - print usage\n\
If no files are specified, stdin is used\n"

Definition at line 80 of file ccomps.c.

Referenced by usage().

◆ verbose

bool verbose = false

static

Definition at line 58 of file ccomps.c.

Referenced by init(), process(), and processClusters().

◆ x_final

int x_final = -1

static

Definition at line 76 of file ccomps.c.

Referenced by init(), process(), and processClusters().

◆ x_index

int x_index = -1

static

Definition at line 75 of file ccomps.c.

Referenced by init(), process(), and processClusters().

◆ []

enum { ... } x_mode

Referenced by init(), printSorted(), process(), and processClusters().

◆ x_node

char* x_node

static

Definition at line 78 of file ccomps.c.

Referenced by init(), process(), and processClusters().

Data Structures

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

◆ GD_cc_subg

◆ ND_dn

◆ ND_ptr

◆ Node_clust

◆ Node_mark

◆ PFX1

◆ PFX2

Enumeration Type Documentation

◆ anonymous enum

◆ anonymous enum

Function Documentation

◆ bindGraphinfo()

◆ chkGraphName()

◆ cmp()

◆ deriveClusters()

◆ deriveGraph()

◆ dfs()

◆ getName()

◆ gwrite()

◆ init()

◆ main()

◆ pop()

◆ printSorted()

◆ process()

◆ processClusters()

◆ projectG()

◆ push()

◆ split()

◆ subGInduce()

◆ subgInduce()

◆ unionNodes()

◆ usage()

Variable Documentation

◆ doAll

◆ doEdges

◆ Inputs

◆ outfile

◆ []

◆ rootpath

◆ sorted

◆ sortFinal

◆ sortIndex

◆ Stk

◆ sufcnt

◆ suffix

◆ useClusters

◆ useString

◆ verbose

◆ x_final

◆ x_index

◆ []

◆ x_node