Graphviz: cmd/tools/sccmap.c File Reference

Searching...

No Matches

extract strongly connected components of directed graphs More...

#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <cgraph/cgraph.h>
#include <cgraph/exit.h>
#include <cgraph/ingraphs.h>
#include <cgraph/stack.h>
#include <cgraph/unreachable.h>
#include <getopt.h>
#include "openFile.h"

Include dependency graph for sccmap.c:

Go to the source code of this file.

Data Structures
struct	Agraphinfo_t

struct	Agnodeinfo_t

struct	sccstate

Macros
#define	INF UINT_MAX

Typedefs
typedef struct Agraphinfo_t	Agraphinfo_t

typedef struct Agnodeinfo_t	Agnodeinfo_t

Functions
static Agnode_t *	getrep (Agraph_t *g)

static void	setrep (Agraph_t g, Agnode_t rep)

static Agraph_t *	getscc (Agnode_t *n)

static void	setscc (Agnode_t n, Agraph_t scc)

static unsigned	getval (Agnode_t *n)

static void	setval (Agnode_t *n, unsigned v)

static void	nodeInduce (Agraph_t g, Agraph_t map)

static unsigned	visit (Agnode_t n, Agraph_t map, gv_stack_t sp, sccstate st)

static int	label (Agnode_t n, int nodecnt, int edgecnt)

static int	countComponents (Agraph_t g, int max_degree, float *nontree_frac)

static void	process (Agraph_t *G)

static void	usage (int v)

static void	scanArgs (int argc, char **argv)

int	main (int argc, char **argv)

Variables
static int	wantDegenerateComp

static int	Silent

static int	StatsOnly

static int	Verbose

static char *	CmdName

static char **	Files

static FILE *	outfp

static char *	useString

Macro Definition Documentation

◆ INF

#define INF UINT_MAX

Definition at line 41 of file sccmap.c.

Typedef Documentation

◆ Agnodeinfo_t

typedef struct Agnodeinfo_t Agnodeinfo_t

◆ Agraphinfo_t

typedef struct Agraphinfo_t Agraphinfo_t

Function Documentation

◆ countComponents()

static int countComponents	(	Agraph_t *	g,
		int *	max_degree,
		float *	nontree_frac
	)

static

Definition at line 175 of file sccmap.c.

References agdegree(), agfstnode(), agnxtnode(), getval(), label(), and setval().

Referenced by process().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ getrep()

static Agnode_t * getrep ( Agraph_t * g )

static

Definition at line 54 of file sccmap.c.

References Agraph_s::base, and Agobj_s::data.

Referenced by nodeInduce().

Here is the caller graph for this function:

◆ getscc()

static Agraph_t * getscc ( Agnode_t * n )

static

Definition at line 62 of file sccmap.c.

References Agnode_s::base, and Agobj_s::data.

Referenced by nodeInduce().

Here is the caller graph for this function:

◆ getval()

static unsigned getval ( Agnode_t * n )

static

Definition at line 70 of file sccmap.c.

References Agnode_s::base, and Agobj_s::data.

Referenced by countComponents(), label(), process(), and visit().

Here is the caller graph for this function:

◆ label()

static int label	(	Agnode_t *	n,
		int	nodecnt,
		int *	edgecnt
	)

static

Definition at line 158 of file sccmap.c.

References agfstedge(), agnxtedge(), agopp, getval(), label(), Agedge_s::node, Agnode_s::root, and setval().

Referenced by compile(), countComponents(), emitEdgeAttrs(), emitNodeAttrs(), glCompLabelDraw(), label(), and mkBlock().

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 318 of file sccmap.c.

References agclose(), agisdirected(), agnameof(), fileName(), Files, graphviz_exit(), newIngraph(), nextGraph(), process(), and scanArgs().

Here is the call graph for this function:

◆ nodeInduce()

static void nodeInduce	(	Agraph_t *	g,
		Agraph_t *	map
	)

static

Definition at line 91 of file sccmap.c.

References agedge(), agfstnode(), agfstout(), aghead, agnxtnode(), agnxtout(), agroot(), agsubedge(), agsubnode(), agtail, getrep(), getscc(), and NULL.

Referenced by visit().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ process()

static void process ( Agraph_t * G )

static

Definition at line 213 of file sccmap.c.

References agclose(), Agdirected, agfstnode(), aginit(), agnedges(), agnnodes(), AGNODE, agnxtnode(), agopen(), AGRAPH, agwrite(), countComponents(), G, getval(), outfp, Silent, stack_reset(), state, StatsOnly, Verbose, and visit().

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scanArgs()

static void scanArgs	(	int	argc,
		char **	argv
	)

static

Definition at line 266 of file sccmap.c.

References CmdName, Files, NULL, openFile(), outfp, Silent, StatsOnly, UNREACHABLE, usage, Verbose, and wantDegenerateComp.

Referenced by main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ setrep()

static void setrep	(	Agraph_t *	g,
		Agnode_t *	rep
	)

static

Definition at line 58 of file sccmap.c.

References Agraph_s::base, and Agobj_s::data.

Referenced by visit().

Here is the caller graph for this function:

◆ setscc()

static void setscc	(	Agnode_t *	n,
		Agraph_t *	scc
	)

static

Definition at line 66 of file sccmap.c.

References Agnode_s::base, and Agobj_s::data.

Referenced by visit().

Here is the caller graph for this function:

◆ setval()

static void setval	(	Agnode_t *	n,
		unsigned	v
	)

static

Definition at line 73 of file sccmap.c.

References Agnode_s::base, and Agobj_s::data.

Referenced by countComponents(), label(), and visit().

Here is the caller graph for this function:

◆ usage()

static void usage ( int v )

static

Definition at line 260 of file sccmap.c.

References CmdName, graphviz_exit(), and useString.

Here is the call graph for this function:

◆ visit()

static unsigned visit	(	Agnode_t *	n,
		Agraph_t *	map,
		gv_stack_t *	sp,
		sccstate *	st
	)

static

Definition at line 112 of file sccmap.c.

References agbindrec(), agfstout(), aghead, agnode(), agnxtout(), agraphof(), agsubg(), agsubnode(), agwrite(), sccstate::Comp, G, getval(), sccstate::ID, INF, sccstate::N_nodes_in_nontriv_SCC, nodeInduce(), outfp, Agnode_s::root, setrep(), setscc(), setval(), stack_pop(), stack_push(), stack_top(), StatsOnly, visit(), and wantDegenerateComp.

Referenced by process(), and visit().

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

◆ CmdName

char* CmdName

static

Definition at line 87 of file sccmap.c.

Referenced by scanArgs(), and usage().

◆ Files

char** Files

static

Definition at line 88 of file sccmap.c.

Referenced by main(), and scanArgs().

◆ outfp

FILE* outfp

static

Definition at line 89 of file sccmap.c.

Referenced by process(), scanArgs(), and visit().

◆ Silent

int Silent

static

Definition at line 84 of file sccmap.c.

Referenced by process(), and scanArgs().

◆ StatsOnly

int StatsOnly

static

Definition at line 85 of file sccmap.c.

Referenced by process(), scanArgs(), and visit().

◆ useString

char* useString

static

Initial value:

= "Usage: %s [-sdv?] <files>\n\
  -s           - only produce statistics\n\
  -S           - silent\n\
  -d           - allow degenerate components\n\
  -o<outfile>  - write to <outfile> (stdout)\n\
  -v           - verbose\n\
  -?           - print usage\n\
If no files are specified, stdin is used\n"

Definition at line 251 of file sccmap.c.

Referenced by usage().

◆ Verbose

int Verbose

static

Definition at line 86 of file sccmap.c.

Referenced by process(), and scanArgs().

◆ wantDegenerateComp

int wantDegenerateComp

static

Definition at line 83 of file sccmap.c.

Referenced by scanArgs(), and visit().

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ INF

Typedef Documentation

◆ Agnodeinfo_t

◆ Agraphinfo_t

Function Documentation

◆ countComponents()

◆ getrep()

◆ getscc()

◆ getval()

◆ label()

◆ main()

◆ nodeInduce()

◆ process()

◆ scanArgs()

◆ setrep()

◆ setscc()

◆ setval()

◆ usage()

◆ visit()

Variable Documentation

◆ CmdName

◆ Files

◆ outfp

◆ Silent

◆ StatsOnly

◆ useString

◆ Verbose

◆ wantDegenerateComp