tred.c File Reference

transitive reduction filter for directed graphs, API: cgraph.h, implements graphviz_tred, used in cmd/tools/tred.c More...

#include <cgraph/cghdr.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <util/alloc.h>
#include <util/list.h>

Include dependency graph for tred.c:

Go to the source code of this file.

Data Structures
struct	nodeinfo_t

Macros
#define	ON_STACK(ninfo, n)   (ninfo[AGSEQ(n)].on_stack)
#define	DISTANCE(ninfo, n)   (ninfo[AGSEQ(n)].dist)
#define	agrootof(n)   ((n)->root)

Functions
static unsigned char	uchar_min (unsigned char a, unsigned char b)
typedef	LIST (Agedge_t *)
static Agedge_t *	pop (edge_stack_t *sp, nodeinfo_t *ninfo)
static Agedge_t *	top (edge_stack_t *sp)
static int	dfs (Agnode_t *n, nodeinfo_t *ninfo, int warn, const graphviz_tred_options_t *opts)
void	graphviz_tred (Agraph_t *g, const graphviz_tred_options_t *opts)
	programmatic access to tred - transitive reduction

Macro Definition Documentation

agrootof

#define agrootof

(

n

)

((n)->root)

Definition at line 39 of file tred.c.

DISTANCE

#define DISTANCE	(		ninfo,
			n
	)		(ninfo[AGSEQ(n)].dist)

Definition at line 38 of file tred.c.

ON_STACK

#define ON_STACK	(		ninfo,
			n
	)		(ninfo[AGSEQ(n)].on_stack)

Definition at line 37 of file tred.c.

Function Documentation

dfs()

static int dfs ( Agnode_t *  n, nodeinfo_t *  ninfo, int  warn, const graphviz_tred_options_t *  opts  )

static

Definition at line 98 of file tred.c.

References agdelete(), agfstout(), aghead, AGINEDGE, agnameof(), agnxtout(), AGOUTEDGE, agrootof, agtail, Agedge_s::base, DISTANCE, Agedgepair_s::in, LIST_FREE, Agedge_s::node, NULL, Agtag_s::objtype, ON_STACK, opts, Agedgepair_s::out, pop(), prev, push(), Agobj_s::tag, top(), and uchar_min().

Referenced by graphviz_tred().

Here is the call graph for this function:

Here is the caller graph for this function:

LIST()

typedef LIST

(

Agedge_t *

)

Definition at line 47 of file tred.c.

References aghead, LIST_PUSH_BACK, and ON_STACK.

pop()

static Agedge_t * pop ( edge_stack_t *  sp, nodeinfo_t *  ninfo  )

static

Definition at line 58 of file tred.c.

References aghead, LIST_IS_EMPTY, LIST_POP_BACK, NULL, and ON_STACK.

top()

static Agedge_t * top ( edge_stack_t *  sp )

static

Definition at line 73 of file tred.c.

References LIST_BACK, LIST_IS_EMPTY, and NULL.

Referenced by compile_clusters(), construct_graph(), dfs(), figColorResolve(), pop(), rcross(), set_boundaries(), tight_subtree_search(), voronoi(), write_dict(), write_dicts(), write_edge(), write_edges(), write_graph(), write_hdr(), write_hdr(), write_node(), write_nodes(), write_subgs(), writeHdr(), and writeTrl().

Here is the caller graph for this function:

uchar_min()

static unsigned char uchar_min ( unsigned char  a, unsigned char  b  )

static

Definition at line 41 of file tred.c.

Referenced by dfs().

Here is the caller graph for this function: