ns.c File Reference

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

#include <assert.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/list.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	tst_t
	state for use in tight_subtree_search More...
struct	STheap_s
struct	dfs_state_t
	local state used by dfs_range* More...

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)
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)
	a stack of states
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 788 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 1138 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 1236 of file ns.c.

References aghead, agtail, ND_lim, ND_low, ND_par, ND_tree_in, ND_tree_out, and dfs_state_t::v.

Referenced by update().

Here is the caller graph for this function:

dfs_range_init()

static int dfs_range_init ( node_t *  v )

static

Definition at line 1170 of file ns.c.

References aghead, agtail, ND_lim, ND_low, ND_par, ND_tree_in, ND_tree_out, NULL, and dfs_state_t::v.

Referenced by init_cutvalues().

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 591 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 400 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 754 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 950 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 810 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 910 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 482 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 449 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 765 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 557 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 1057 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 979 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 666 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 744 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 727 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 512 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 523 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 491 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 489 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 419 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 429 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 832 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 326 of file ns.c.

References add_tree_edge(), aghead, agtail, last, ND_in, ND_out, ND_subtree, ND_subtree_set, SLACK, top(), TREE_EDGE, and tst_t::v.

Referenced by find_tight_subtree().

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 538 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 643 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 684 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 1071 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 1100 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().