ccomps.c File Reference

connected components filter for graphs More...

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <cgraph/cgraph.h>
#include <cgraph/ingraphs.h>
#include <cgraph/list.h>
#include <common/render.h>
#include <common/utils.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/gv_ctype.h>
#include <util/prisize_t.h>
#include <util/strview.h>
#include <util/unreachable.h>
#include <getopt.h>
#include <string.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_%ld"

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)
static int	cmp (const void *x, const void *y)
static void	printSorted (Agraph_t *root, int c_cnt)
static int	processClusters (Agraph_t *g, char *graphName)
static void	bindGraphinfo (Agraph_t *g)
static int	process (Agraph_t *g, char *graphName)
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 49 of file ccomps.c.

ND_dn

#define ND_dn

(

n

)

((Agnode_t*)ND_ptr(n))

Definition at line 52 of file ccomps.c.

ND_ptr

#define ND_ptr

(

n

)

(((nodeinfo_t*)(n->base.data))->ptr)

Definition at line 51 of file ccomps.c.

Node_clust

#define Node_clust

(

n

)

((Agraph_t*)ND_ptr(n))

Definition at line 53 of file ccomps.c.

Node_mark

#define Node_mark

(

n

)

(((nodeinfo_t*)(n->base.data))->mark)

Definition at line 50 of file ccomps.c.

PFX1

#define PFX1   "%s_cc"

Definition at line 358 of file ccomps.c.

PFX2

#define PFX2   "%s_cc_%ld"

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

anonymous enum

anonymous enum

Enumerator
BY_INDEX
BY_SIZE

Definition at line 79 of file ccomps.c.

Function Documentation

bindGraphinfo()

static void bindGraphinfo ( Agraph_t *  g )

static

Definition at line 656 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 789 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 452 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 366 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 396 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 239 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 260 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 277 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 115 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 800 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 231 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, int  c_cnt  )

static

Definition at line 477 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 669 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 538 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 306 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 225 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 102 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 353 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 336 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 435 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 96 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 69 of file ccomps.c.

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

doEdges

bool doEdges = true

static

Definition at line 68 of file ccomps.c.

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

Inputs

char** Inputs

static

Definition at line 59 of file ccomps.c.

Referenced by init(), and main().

outfile

char* outfile = 0

static

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

Referenced by getName(), and split().

sorted

bool sorted = false

static

Definition at line 74 of file ccomps.c.

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

sortFinal

int sortFinal

static

Definition at line 76 of file ccomps.c.

Referenced by init(), and printSorted().

sortIndex

int sortIndex = 0

static

Definition at line 75 of file ccomps.c.

Referenced by init(), and printSorted().

Stk

node_stack_t Stk

static

Definition at line 223 of file ccomps.c.

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

sufcnt

int sufcnt = 0

static

Definition at line 73 of file ccomps.c.

Referenced by getName().

suffix

char* suffix = 0

static

Definition at line 70 of file ccomps.c.

Referenced by getName(), and split().

useClusters

bool useClusters = false

static

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

Referenced by usage().

verbose

bool verbose = false

static

Definition at line 60 of file ccomps.c.

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

x_final

int x_final = -1

static

Definition at line 78 of file ccomps.c.

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

x_index

int x_index = -1

static

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

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