Graphviz: lib/common/ns.c File Reference

Searching...

No Matches

Network Simplex algorithm for ranking nodes of a DAG, rank, rank2. More...

#include <assert.h>
#include <cgraph/list.h>
#include <common/render.h>
#include <limits.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <util/alloc.h>
#include <util/exit.h>
#include <util/overflow.h>
#include <util/prisize_t.h>
#include <util/streq.h>

Include dependency graph for ns.c:

Go to the source code of this file.

Data Structures
struct	subtree_s

struct	STheap_s

Macros
#define	LENGTH(e) (ND_rank(aghead(e)) - ND_rank(agtail(e)))

#define	SLACK(e) (LENGTH(e) - ED_minlen(e))

#define	SEQ(a, b, c) ((a) <= (b) && (b) <= (c))

#define	TREE_EDGE(e) (ED_tree_index(e) >= 0)

#define	SEARCHSIZE 30

#define	ND_subtree(n) (subtree_t*)ND_par(n)

#define	ND_subtree_set(n, value) (ND_par(n) = (edge_t*)value)

Typedefs
typedef struct subtree_s	subtree_t

typedef struct STheap_s	STheap_t

Functions
static void	dfs_cutval (node_t v, edge_t par)

static int	dfs_range_init (node_t v, edge_t par, int low)

static int	dfs_range (node_t v, edge_t par, int low)

static int	x_val (edge_t e, node_t v, int dir)

static int	add_tree_edge (edge_t *e)

static void	invalidate_path (node_t lca, node_t to_node)

static void	exchange_tree_edges (edge_t e, edge_t f)

static void	init_rank (void)

static edge_t *	leave_edge (void)

static void	dfs_enter_outedge (node_t *v)

static void	dfs_enter_inedge (node_t *v)

static edge_t *	enter_edge (edge_t *e)

static void	init_cutvalues (void)

static bool	on_heap (const subtree_t *tree)
	is this subtree stored in an STheap?

static int	tight_subtree_search (Agnode_t v, subtree_t st)

static subtree_t *	find_tight_subtree (Agnode_t *v)

static subtree_t *	STsetFind (Agnode_t *n0)

static subtree_t *	STsetUnion (subtree_t s0, subtree_t s1)

static Agedge_t *	inter_tree_edge_search (Agnode_t v, Agnode_t from, Agedge_t *best)

static Agedge_t *	inter_tree_edge (subtree_t *tree)

static size_t	STheapsize (const STheap_t *heap)

static void	STheapify (STheap_t *heap, size_t i)

static STheap_t *	STbuildheap (subtree_t **elt, size_t size)

static subtree_t *	STextractmin (STheap_t *heap)

static void	tree_adjust (Agnode_t v, Agnode_t from, int delta)

static subtree_t *	merge_trees (Agedge_t *e)

static int	feasible_tree (void)

static Agnode_t *	treeupdate (Agnode_t v, Agnode_t w, int cutvalue, int dir)

static void	rerank (Agnode_t *v, int delta)

static int	update (edge_t e, edge_t f)

static int	scan_and_normalize (void)

static void	reset_lists (void)

static void	freeTreeList (graph_t *g)

static void	LR_balance (void)

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

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

static void	TB_balance (void)

static bool	init_graph (graph_t *g)

static void	graphSize (graph_t g, int nn, int *ne)

int	rank2 (graph_t *g, int balance, int maxiter, int search_size)

int	rank (graph_t *g, int balance, int maxiter)

static void	x_cutval (edge_t *f)

Variables
static graph_t *	G

static size_t	N_nodes

static size_t	N_edges

static size_t	S_i

static int	Search_size

static nlist_t	Tree_node

static elist	Tree_edge

static edge_t *	Enter

static int	Low

static int	Lim

static int	Slack

Macro Definition Documentation

◆ LENGTH

#define LENGTH ( e ) (ND_rank(aghead(e)) - ND_rank(agtail(e)))

Definition at line 39 of file ns.c.

◆ ND_subtree

#define ND_subtree ( n ) (subtree_t*)ND_par(n)

Definition at line 299 of file ns.c.

◆ ND_subtree_set

#define ND_subtree_set	(	n,
		value
	)	(ND_par(n) = (edge_t*)value)

Definition at line 300 of file ns.c.

◆ SEARCHSIZE

#define SEARCHSIZE 30

Definition at line 48 of file ns.c.

◆ SEQ

#define SEQ	(	a,
		b,
		c
	)	((a) <= (b) && (b) <= (c))

Definition at line 41 of file ns.c.

◆ SLACK

#define SLACK ( e ) (LENGTH(e) - ED_minlen(e))

Definition at line 40 of file ns.c.

◆ TREE_EDGE

#define TREE_EDGE ( e ) (ED_tree_index(e) >= 0)

Definition at line 42 of file ns.c.

Typedef Documentation

◆ STheap_t

typedef struct STheap_s STheap_t

◆ subtree_t

typedef struct subtree_s subtree_t

Function Documentation

◆ add_tree_edge()

static int add_tree_edge ( edge_t * e )

static

Definition at line 52 of file ns.c.

References agerrorf(), aghead, agtail, ED_tree_index, nlist_t::list, elist::list, ND_in, ND_mark, ND_out, ND_tree_in, ND_tree_out, NULL, nlist_t::size, elist::size, TREE_EDGE, Tree_edge, and Tree_node.

Referenced by merge_trees(), and tight_subtree_search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ decreasingrankcmpf()

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

static

Definition at line 732 of file ns.c.

References ND_rank.

Referenced by TB_balance().

Here is the caller graph for this function:

◆ dfs_cutval()

static void dfs_cutval	(	node_t *	v,
		edge_t *	par
	)

static

Definition at line 1082 of file ns.c.

References aghead, agtail, dfs_cutval(), ND_tree_in, ND_tree_out, and x_cutval().

Referenced by dfs_cutval(), and init_cutvalues().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs_enter_inedge()

static void dfs_enter_inedge ( node_t * v )

static

Definition at line 245 of file ns.c.

References aghead, agtail, dfs_enter_inedge(), Enter, Lim, Low, ND_in, ND_lim, ND_tree_out, NULL, SEQ, SLACK, Slack, and TREE_EDGE.

Referenced by dfs_enter_inedge(), and enter_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs_enter_outedge()

static void dfs_enter_outedge ( node_t * v )

static

Definition at line 223 of file ns.c.

References aghead, agtail, dfs_enter_outedge(), Enter, Lim, Low, ND_lim, ND_out, ND_tree_in, NULL, SEQ, SLACK, Slack, and TREE_EDGE.

Referenced by dfs_enter_outedge(), and enter_edge().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs_range()

static int dfs_range	(	node_t *	v,
		edge_t *	par,
		int	low
	)

static

Definition at line 1132 of file ns.c.

References aghead, agtail, dfs_range(), ND_lim, ND_low, ND_par, ND_tree_in, and ND_tree_out.

Referenced by dfs_range(), and update().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ dfs_range_init()

static int dfs_range_init	(	node_t *	v,
		edge_t *	par,
		int	low
	)

static

Definition at line 1103 of file ns.c.

References aghead, agtail, dfs_range_init(), ND_lim, ND_low, ND_par, ND_tree_in, and ND_tree_out.

Referenced by dfs_range_init(), and init_cutvalues().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ enter_edge()

static edge_t * enter_edge ( edge_t * e )

static

Definition at line 267 of file ns.c.

References aghead, agtail, dfs_enter_inedge(), dfs_enter_outedge(), Enter, Lim, Low, ND_lim, ND_low, NULL, and Slack.

Referenced by LR_balance(), and rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ exchange_tree_edges()

static void exchange_tree_edges	(	edge_t *	e,
		edge_t *	f
	)

static

Definition at line 114 of file ns.c.

References aghead, agtail, ED_tree_index, elist::list, ND_tree_in, ND_tree_out, NULL, and Tree_edge.

Referenced by update().

Here is the caller graph for this function:

◆ feasible_tree()

static int feasible_tree ( void )

static

Definition at line 535 of file ns.c.

References error, find_tight_subtree(), free(), G, GD_nlist, gv_calloc(), subtree_s::heap_index, init_cutvalues(), inter_tree_edge(), merge_trees(), N_nodes, ND_next, ND_subtree, ND_subtree_set, NULL, elist::size, STbuildheap(), STextractmin(), STheapify(), STheapsize(), tree, and Tree_edge.

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ find_tight_subtree()

static subtree_t * find_tight_subtree ( Agnode_t * v )

static

Definition at line 344 of file ns.c.

References free(), gv_alloc(), NULL, subtree_s::par, subtree_s::rep, subtree_s::size, and tight_subtree_search().

Referenced by feasible_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ freeTreeList()

static void freeTreeList ( graph_t * g )

static

Definition at line 698 of file ns.c.

References free_list, GD_nlist, ND_mark, ND_next, ND_tree_in, ND_tree_out, and reset_lists().

Referenced by LR_balance(), and rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ graphSize()

static void graphSize	(	graph_t *	g,
		int *	nn,
		int *	ne
	)

static

Definition at line 894 of file ns.c.

References GD_nlist, ND_next, ND_out, and nedges.

Referenced by rank2().

Here is the caller graph for this function:

◆ increasingrankcmpf()

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

static

Definition at line 754 of file ns.c.

References ND_rank.

Referenced by TB_balance().

Here is the caller graph for this function:

◆ init_cutvalues()

static void init_cutvalues ( void )

static

Definition at line 291 of file ns.c.

References dfs_cutval(), dfs_range_init(), G, GD_nlist, and NULL.

Referenced by feasible_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_graph()

static bool init_graph ( graph_t * g )

static

Definition at line 854 of file ns.c.

References aghead, agtail, ED_cutvalue, ED_minlen, ED_tree_index, G, GD_nlist, gv_calloc(), nlist_t::list, elist::list, N_edges, N_nodes, ND_in, ND_mark, ND_next, ND_out, ND_priority, ND_rank, ND_tree_in, ND_tree_out, S_i, Tree_edge, and Tree_node.

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_rank()

static void init_rank ( void )

static

Definition at line 149 of file ns.c.

References agerr(), agerrorf(), aghead, agnameof(), AGPREV, agtail, ED_minlen, G, GD_nlist, MAX, N_nodes, ND_in, ND_next, ND_out, ND_priority, and ND_rank.

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inter_tree_edge()

static Agedge_t * inter_tree_edge ( subtree_t * tree )

static

Definition at line 426 of file ns.c.

References inter_tree_edge_search(), NULL, and tree.

Referenced by feasible_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ inter_tree_edge_search()

static Agedge_t * inter_tree_edge_search	(	Agnode_t *	v,
		Agnode_t *	from,
		Agedge_t *	best
	)

static

Definition at line 393 of file ns.c.

References aghead, agtail, inter_tree_edge_search(), ND_in, ND_out, SLACK, STsetFind(), and TREE_EDGE.

Referenced by inter_tree_edge(), and inter_tree_edge_search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ invalidate_path()

static void invalidate_path	(	node_t *	lca,
		node_t *	to_node
	)

static

Invalidate DFS attributes by walking up the tree from to_node till lca (inclusively). Called when updating tree to improve pruning in dfs_range(). Assigns ND_low(n) = -1 for the affected nodes.

Definition at line 90 of file ns.c.

References agerrorf(), aghead, agtail, ND_lim, ND_low, ND_par, and NULL.

Referenced by update().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ leave_edge()

static edge_t * leave_edge ( void )

static

Definition at line 184 of file ns.c.

References cnt(), ED_cutvalue, elist::list, NULL, S_i, Search_size, elist::size, and Tree_edge.

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ LR_balance()

static void LR_balance ( void )

static

Definition at line 709 of file ns.c.

References aghead, agtail, delta, ED_cutvalue, enter_edge(), freeTreeList(), G, elist::list, ND_lim, NULL, rerank(), elist::size, SLACK, and Tree_edge.

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ merge_trees()

static subtree_t * merge_trees ( Agedge_t * e )

static

Definition at line 501 of file ns.c.

References add_tree_edge(), aghead, agtail, delta, NULL, on_heap(), subtree_s::rep, SLACK, STsetFind(), STsetUnion(), tree_adjust(), and TREE_EDGE.

Referenced by feasible_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ on_heap()

static bool on_heap ( const subtree_t * tree )

static

Definition at line 310 of file ns.c.

References subtree_s::heap_index, SIZE_MAX, and tree.

Referenced by merge_trees(), resolveColor(), and STsetUnion().

Here is the caller graph for this function:

◆ rank()

int rank	(	graph_t *	g,
		int	balance,
		int	maxiter
	)

Definition at line 1001 of file ns.c.

References agget(), rank2(), and SEARCHSIZE.

Referenced by adjustRanks(), adjustSimple(), checkFlatAdjacent(), clust_ht(), constrainX(), constrainY(), dot_position(), flat_limits(), make_LR_constraints(), neighbor(), rank1(), set_xcoords(), and set_ycoords().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rank2()

int rank2	(	graph_t *	g,
		int	balance,
		int	maxiter,
		int	search_size
	)

Definition at line 923 of file ns.c.

References elapsed_sec(), enter_edge(), err, feasible_tree(), freeTreeList(), G, graphSize(), init_graph(), init_rank(), leave_edge(), LR_balance(), N_edges, N_nodes, PRISIZE_T, reset_lists(), scan_and_normalize(), Search_size, SEARCHSIZE, start_timer(), TB_balance(), update(), and Verbose.

Referenced by dot2_rank(), and rank().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ rerank()

static void rerank	(	Agnode_t *	v,
		int	delta
	)

static

Definition at line 610 of file ns.c.

References aghead, agtail, delta, ND_par, ND_rank, ND_tree_in, ND_tree_out, and rerank().

Referenced by LR_balance(), rerank(), and update().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ reset_lists()

static void reset_lists ( void )

static

Definition at line 688 of file ns.c.

References free(), nlist_t::list, elist::list, Tree_edge, and Tree_node.

Referenced by freeTreeList(), and rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ scan_and_normalize()

static int scan_and_normalize ( void )

static

Definition at line 671 of file ns.c.

References G, GD_nlist, MAX, MIN, ND_next, ND_node_type, ND_rank, and NORMAL.

Referenced by rank2(), and TB_balance().

Here is the caller graph for this function:

◆ STbuildheap()

static STheap_t * STbuildheap	(	subtree_t **	elt,
		size_t	size
	)

static

Definition at line 456 of file ns.c.

References gv_alloc(), SIZE_MAX, and STheapify().

Referenced by feasible_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ STextractmin()

static subtree_t * STextractmin ( STheap_t * heap )

static

Definition at line 467 of file ns.c.

References subtree_s::heap_index, SIZE_MAX, and STheapify().

Referenced by feasible_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ STheapify()

static void STheapify	(	STheap_t *	heap,
		size_t	i
	)

static

Definition at line 435 of file ns.c.

References subtree_s::heap_index, left, and right.

Referenced by feasible_tree(), STbuildheap(), and STextractmin().

Here is the caller graph for this function:

◆ STheapsize()

static size_t STheapsize ( const STheap_t * heap )

static

Definition at line 433 of file ns.c.

Referenced by feasible_tree().

Here is the caller graph for this function:

◆ STsetFind()

static subtree_t * STsetFind ( Agnode_t * n0 )

static

Definition at line 363 of file ns.c.

References ND_subtree, and subtree_s::par.

Referenced by inter_tree_edge_search(), and merge_trees().

Here is the caller graph for this function:

◆ STsetUnion()

static subtree_t * STsetUnion	(	subtree_t *	s0,
		subtree_t *	s1
	)

static

Definition at line 373 of file ns.c.

References on_heap(), subtree_s::par, s1(), and subtree_s::size.

Referenced by merge_trees().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ TB_balance()

static void TB_balance ( void )

static

Definition at line 776 of file ns.c.

References agget(), aghead, agtail, decreasingrankcmpf(), ED_minlen, ED_weight, free(), free_list, G, GD_nlist, gv_calloc(), increasingrankcmpf(), nlist_t::list, MAX, MIN, ND_in, ND_mark, ND_next, ND_node_type, ND_out, ND_rank, ND_tree_in, ND_tree_out, NORMAL, scan_and_normalize(), nlist_t::size, streq(), and Tree_node.

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ tight_subtree_search()

static int tight_subtree_search	(	Agnode_t *	v,
		subtree_t *	st
	)

static

Definition at line 315 of file ns.c.

References add_tree_edge(), aghead, agtail, ND_in, ND_out, ND_subtree, ND_subtree_set, SLACK, tight_subtree_search(), and TREE_EDGE.

Referenced by find_tight_subtree(), and tight_subtree_search().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ tree_adjust()

static void tree_adjust	(	Agnode_t *	v,
		Agnode_t *	from,
		int	delta
	)

static

Definition at line 482 of file ns.c.

References aghead, agtail, delta, ND_rank, ND_tree_in, ND_tree_out, and tree_adjust().

Referenced by merge_trees(), and tree_adjust().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ treeupdate()

static Agnode_t * treeupdate	(	Agnode_t *	v,
		Agnode_t *	w,
		int	cutvalue,
		int	dir
	)

static

Definition at line 587 of file ns.c.

References aghead, agtail, ED_cutvalue, ND_lim, ND_low, ND_par, and SEQ.

Referenced by update().

Here is the caller graph for this function:

◆ update()

static int update	(	edge_t *	e,
		edge_t *	f
	)

static

Definition at line 628 of file ns.c.

References agerrorf(), aghead, agtail, delta, dfs_range(), ED_cutvalue, exchange_tree_edges(), invalidate_path(), ND_lim, ND_low, ND_par, ND_tree_in, ND_tree_out, rerank(), SLACK, and treeupdate().

Referenced by rank2().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ x_cutval()

static void x_cutval ( edge_t * f )

static

Definition at line 1015 of file ns.c.

References agerrorf(), aghead, agtail, ED_cutvalue, graphviz_exit(), ND_in, ND_out, ND_par, sadd_overflow(), and x_val().

Referenced by dfs_cutval().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ x_val()

static int x_val	(	edge_t *	e,
		node_t *	v,
		int	dir
	)

static

Definition at line 1044 of file ns.c.

References aghead, agtail, ED_cutvalue, ED_weight, ND_lim, ND_low, SEQ, and TREE_EDGE.

Referenced by x_cutval().

Here is the caller graph for this function:

Variable Documentation

◆ Enter

edge_t* Enter

static

Definition at line 220 of file ns.c.

Referenced by dfs_enter_inedge(), dfs_enter_outedge(), and enter_edge().

◆ G

graph_t* G

static

Definition at line 44 of file ns.c.

Referenced by feasible_tree(), init_cutvalues(), init_graph(), init_rank(), LR_balance(), rank2(), scan_and_normalize(), and TB_balance().

◆ Lim

int Lim

static

Definition at line 221 of file ns.c.

Referenced by dfs_enter_inedge(), dfs_enter_outedge(), and enter_edge().

◆ Low

int Low

static

Definition at line 221 of file ns.c.

Referenced by dfs_enter_inedge(), dfs_enter_outedge(), and enter_edge().

◆ N_edges

size_t N_edges

static

Definition at line 45 of file ns.c.

Referenced by init_graph(), and rank2().

◆ N_nodes

size_t N_nodes

static

Definition at line 45 of file ns.c.

Referenced by feasible_tree(), init_graph(), init_rank(), and rank2().

◆ S_i

size_t S_i

static

Definition at line 46 of file ns.c.

Referenced by init_graph(), and leave_edge().

◆ Search_size

int Search_size

static

Definition at line 47 of file ns.c.

Referenced by leave_edge(), and rank2().

◆ Slack

int Slack

static

Definition at line 221 of file ns.c.

Referenced by dfs_enter_inedge(), dfs_enter_outedge(), and enter_edge().

◆ Tree_edge

elist Tree_edge

static

Definition at line 50 of file ns.c.

Referenced by add_tree_edge(), exchange_tree_edges(), feasible_tree(), init_graph(), leave_edge(), LR_balance(), and reset_lists().

◆ Tree_node

nlist_t Tree_node

static

Definition at line 49 of file ns.c.

Referenced by add_tree_edge(), init_graph(), reset_lists(), and TB_balance().

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ LENGTH

◆ ND_subtree

◆ ND_subtree_set

◆ SEARCHSIZE

◆ SEQ

◆ SLACK

◆ TREE_EDGE

Typedef Documentation

◆ STheap_t

◆ subtree_t

Function Documentation

◆ add_tree_edge()

◆ decreasingrankcmpf()

◆ dfs_cutval()

◆ dfs_enter_inedge()

◆ dfs_enter_outedge()

◆ dfs_range()

◆ dfs_range_init()

◆ enter_edge()

◆ exchange_tree_edges()

◆ feasible_tree()

◆ find_tight_subtree()

◆ freeTreeList()

◆ graphSize()

◆ increasingrankcmpf()

◆ init_cutvalues()

◆ init_graph()

◆ init_rank()

◆ inter_tree_edge()

◆ inter_tree_edge_search()

◆ invalidate_path()

◆ leave_edge()

◆ LR_balance()

◆ merge_trees()

◆ on_heap()

◆ rank()

◆ rank2()

◆ rerank()

◆ reset_lists()

◆ scan_and_normalize()

◆ STbuildheap()

◆ STextractmin()

◆ STheapify()

◆ STheapsize()

◆ STsetFind()

◆ STsetUnion()

◆ TB_balance()

◆ tight_subtree_search()

◆ tree_adjust()

◆ treeupdate()

◆ update()

◆ x_cutval()

◆ x_val()

Variable Documentation

◆ Enter

◆ G

◆ Lim

◆ Low

◆ N_edges

◆ N_nodes

◆ S_i

◆ Search_size

◆ Slack

◆ Tree_edge

◆ Tree_node