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 <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/gv_math.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	network_simplex_ctx_t

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	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

Enumerations
enum	{ SEARCHSIZE = 30 }

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 (network_simplex_ctx_t ctx, edge_t e)

static void	invalidate_path (node_t lca, node_t to_node)

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

static void	init_rank (network_simplex_ctx_t *ctx)

static edge_t *	leave_edge (network_simplex_ctx_t *ctx)

static edge_t *	dfs_enter_outedge (node_t *v, int Low, int Lim)

static edge_t *	dfs_enter_inedge (node_t *v, int Low, int Lim)

static edge_t *	enter_edge (edge_t *e)

static void	init_cutvalues (network_simplex_ctx_t *ctx)

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

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

static subtree_t *	find_tight_subtree (network_simplex_ctx_t ctx, 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 (network_simplex_ctx_t ctx, Agedge_t e)

static int	feasible_tree (network_simplex_ctx_t *ctx)

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

static void	rerank (Agnode_t *v, int delta)

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

static int	scan_and_normalize (network_simplex_ctx_t *ctx)

static void	reset_lists (network_simplex_ctx_t *ctx)

static void	freeTreeList (network_simplex_ctx_t ctx, graph_t g)

static void	LR_balance (network_simplex_ctx_t *ctx)

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

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

static void	TB_balance (network_simplex_ctx_t *ctx)

static bool	init_graph (network_simplex_ctx_t ctx, graph_t g)

static void	graphSize (graph_t g, size_t nn, size_t *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)

Macro Definition Documentation

◆ LENGTH

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

Definition at line 40 of file ns.c.

◆ ND_subtree

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

Definition at line 305 of file ns.c.

◆ ND_subtree_set

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

Definition at line 306 of file ns.c.

◆ SEQ

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

Definition at line 42 of file ns.c.

◆ SLACK

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

Definition at line 41 of file ns.c.

◆ TREE_EDGE

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

Definition at line 43 of file ns.c.

Typedef Documentation

◆ STheap_t

typedef struct STheap_s STheap_t

◆ subtree_t

typedef struct subtree_s subtree_t

Enumeration Type Documentation

◆ anonymous enum

anonymous enum

Enumerator
SEARCHSIZE

Definition at line 53 of file ns.c.

Function Documentation

◆ add_tree_edge()

static int add_tree_edge	(	network_simplex_ctx_t *	ctx,
		edge_t *	e
	)

static

Definition at line 55 of file ns.c.

References agerrorf(), aghead, agtail, ED_tree_index, LIST_APPEND, LIST_SIZE, ND_in, ND_mark, ND_out, ND_tree_in, ND_tree_out, NULL, and TREE_EDGE.

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 753 of file ns.c.

References ND_rank.

Referenced by increasingrankcmpf(), and 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 1067 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 edge_t * dfs_enter_inedge	(	node_t *	v,
		int	Low,
		int	Lim
	)

static

Definition at line 246 of file ns.c.

References aghead, agtail, LIST, LIST_APPEND, LIST_FREE, LIST_IS_EMPTY, LIST_POP_BACK, Low, ND_in, ND_lim, ND_tree_out, NULL, SEQ, SLACK, and TREE_EDGE.

Referenced by enter_edge().

Here is the caller graph for this function:

◆ dfs_enter_outedge()

static edge_t * dfs_enter_outedge	(	node_t *	v,
		int	Low,
		int	Lim
	)

static

Definition at line 213 of file ns.c.

References aghead, agtail, LIST, LIST_APPEND, LIST_FREE, LIST_IS_EMPTY, LIST_POP_BACK, Low, ND_lim, ND_out, ND_tree_in, NULL, SEQ, SLACK, and TREE_EDGE.

Referenced by enter_edge().

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 1162 of file ns.c.

References aghead, agtail, LIST, LIST_BACK, LIST_FREE, LIST_IS_EMPTY, LIST_POP_BACK, LIST_PUSH_BACK, 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 1096 of file ns.c.

References aghead, agtail, LIST, LIST_BACK, LIST_FREE, LIST_IS_EMPTY, LIST_POP_BACK, LIST_PUSH_BACK, 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 280 of file ns.c.

References aghead, agtail, dfs_enter_inedge(), dfs_enter_outedge(), ND_lim, and ND_low.

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	(	network_simplex_ctx_t *	ctx,
		edge_t *	e,
		edge_t *	f
	)

static

Definition at line 112 of file ns.c.

References aghead, agtail, ED_tree_index, LIST_SET, ND_tree_in, ND_tree_out, and NULL.

Referenced by update().

Here is the caller graph for this function:

◆ feasible_tree()

static int feasible_tree ( network_simplex_ctx_t * ctx )

static

Definition at line 578 of file ns.c.

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

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	(	network_simplex_ctx_t *	ctx,
		Agnode_t *	v
	)

static

Definition at line 402 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	(	network_simplex_ctx_t *	ctx,
		graph_t *	g
	)

static

Definition at line 723 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,
		size_t *	nn,
		size_t *	ne
	)

static

Definition at line 881 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 765 of file ns.c.

References decreasingrankcmpf().

Referenced by TB_balance().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ init_cutvalues()

static void init_cutvalues ( network_simplex_ctx_t * ctx )

static

Definition at line 297 of file ns.c.

References dfs_cutval(), dfs_range_init(), network_simplex_ctx_t::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	(	network_simplex_ctx_t *	ctx,
		graph_t *	g
	)

static

Definition at line 845 of file ns.c.

References aghead, agtail, ED_cutvalue, ED_minlen, ED_tree_index, network_simplex_ctx_t::G, GD_nlist, gv_calloc(), LIST_RESERVE, ND_in, ND_mark, ND_next, ND_out, ND_priority, ND_rank, ND_tree_in, and ND_tree_out.

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 ( network_simplex_ctx_t * ctx )

static

Definition at line 144 of file ns.c.

References agerr(), agerrorf(), aghead, agnameof(), AGPREV, agtail, ED_minlen, network_simplex_ctx_t::G, GD_nlist, LIST, LIST_FREE, LIST_IS_EMPTY, LIST_POP_FRONT, LIST_PUSH_BACK, LIST_RESERVE, MAX, 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 450 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 88 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 ( network_simplex_ctx_t * ctx )

static

Definition at line 177 of file ns.c.

References cnt(), ED_cutvalue, LIST_GET, LIST_SIZE, and NULL.

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 ( network_simplex_ctx_t * ctx )

static

Definition at line 733 of file ns.c.

References aghead, agtail, delta, ED_cutvalue, enter_edge(), freeTreeList(), network_simplex_ctx_t::G, LIST_GET, LIST_SIZE, ND_lim, NULL, rerank(), and SLACK.

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	(	network_simplex_ctx_t *	ctx,
		Agedge_t *	e
	)

static

Definition at line 549 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 316 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 986 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 908 of file ns.c.

References elapsed_sec(), enter_edge(), err, feasible_tree(), freeTreeList(), network_simplex_ctx_t::G, graphSize(), init_graph(), init_rank(), leave_edge(), LR_balance(), PRISIZE_T, reset_lists(), scan_and_normalize(), 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 646 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 ( network_simplex_ctx_t * ctx )

static

Definition at line 718 of file ns.c.

References LIST_FREE.

Referenced by freeTreeList(), and rank2().

Here is the caller graph for this function:

◆ scan_and_normalize()

static int scan_and_normalize ( network_simplex_ctx_t * ctx )

static

Definition at line 703 of file ns.c.

References network_simplex_ctx_t::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 507 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 518 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 489 of file ns.c.

References subtree_s::heap_index, left, right, and SWAP.

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 487 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 420 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 430 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 ( network_simplex_ctx_t * ctx )

static

Definition at line 769 of file ns.c.

References agget(), aghead, agtail, decreasingrankcmpf(), ED_minlen, ED_weight, free(), free_list, network_simplex_ctx_t::G, GD_nlist, gv_calloc(), increasingrankcmpf(), LIST, LIST_APPEND, LIST_FREE, LIST_GET, LIST_RESERVE, LIST_SIZE, LIST_SORT, 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(), and streq().

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	(	network_simplex_ctx_t *	ctx,
		Agnode_t *	v,
		subtree_t *	st
	)

static

Definition at line 329 of file ns.c.

References add_tree_edge(), aghead, agtail, last, LIST, LIST_BACK, LIST_FREE, LIST_IS_EMPTY, LIST_POP_BACK, LIST_PUSH_BACK, 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 532 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,
		bool	dir
	)

static

Definition at line 630 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	(	network_simplex_ctx_t *	ctx,
		edge_t *	e,
		edge_t *	f
	)

static

Definition at line 663 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 1000 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 1029 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:

Data Structures

Macros

Typedefs

Enumerations

Functions

Macro Definition Documentation

◆ LENGTH

◆ ND_subtree

◆ ND_subtree_set

◆ SEQ

◆ SLACK

◆ TREE_EDGE

Typedef Documentation

◆ STheap_t

◆ subtree_t

Enumeration Type Documentation

◆ anonymous enum

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()