Graphviz 13.0.0~dev.20241212.1010
Loading...
Searching...
No Matches
sccmap.c File Reference

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/ingraphs.h>
#include <cgraph/list.h>
#include <getopt.h>
#include "openFile.h"
#include <util/exit.h>
#include <util/unreachable.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_tgetrep (Agraph_t *g)
 
static void setrep (Agraph_t *g, Agnode_t *rep)
 
static Agraph_tgetscc (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, node_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 178 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 161 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 321 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 216 of file sccmap.c.

References agclose(), Agdirected, agfstnode(), aginit(), agnedges(), agnnodes(), AGNODE, agnxtnode(), agopen(), AGRAPH, agwrite(), sccstate::Comp, countComponents(), G, getval(), sccstate::ID, sccstate::N_nodes_in_nontriv_SCC, outfp, Silent, 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 269 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 263 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,
node_stack_t *  sp,
sccstate st 
)
static

Definition at line 114 of file sccmap.c.

References agbindrec(), agfstout(), aghead, agnode(), agnxtout(), agraphof(), agsubg(), agsubnode(), agwrite(), G, getval(), INF, nodeInduce(), outfp, setrep(), setscc(), setval(), 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 254 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().