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/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	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 (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 void	dfs_enter_outedge (network_simplex_ctx_t ctx, node_t v)

static void	dfs_enter_inedge (network_simplex_ctx_t ctx, node_t v)

static edge_t *	enter_edge (network_simplex_ctx_t ctx, 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)
	a stack of states

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, int 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, 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)

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

◆ ND_subtree_set

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

Definition at line 303 of file ns.c.

◆ SEARCHSIZE

#define SEARCHSIZE 30

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

static

Definition at line 58 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, network_simplex_ctx_t::Tree_edge, and network_simplex_ctx_t::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 791 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 1142 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	(	network_simplex_ctx_t *	ctx,
		node_t *	v
	)

static

Definition at line 248 of file ns.c.

References aghead, agtail, dfs_enter_inedge(), network_simplex_ctx_t::Enter, network_simplex_ctx_t::Lim, network_simplex_ctx_t::Low, ND_in, ND_lim, ND_tree_out, NULL, SEQ, SLACK, network_simplex_ctx_t::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	(	network_simplex_ctx_t *	ctx,
		node_t *	v
	)

static

Definition at line 226 of file ns.c.

References aghead, agtail, dfs_enter_outedge(), network_simplex_ctx_t::Enter, network_simplex_ctx_t::Lim, network_simplex_ctx_t::Low, ND_lim, ND_out, ND_tree_in, NULL, SEQ, SLACK, network_simplex_ctx_t::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 1240 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 1174 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	(	network_simplex_ctx_t *	ctx,
		edge_t *	e
	)

static

Definition at line 270 of file ns.c.

References aghead, agtail, dfs_enter_inedge(), dfs_enter_outedge(), network_simplex_ctx_t::Enter, network_simplex_ctx_t::Lim, network_simplex_ctx_t::Low, ND_lim, ND_low, NULL, and network_simplex_ctx_t::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	(	network_simplex_ctx_t *	ctx,
		edge_t *	e,
		edge_t *	f
	)

static

Definition at line 120 of file ns.c.

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

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 594 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(), merge_trees(), network_simplex_ctx_t::N_nodes, ND_next, ND_subtree, ND_subtree_set, NULL, elist::size, STbuildheap(), STextractmin(), STheapify(), STheapsize(), tree, and network_simplex_ctx_t::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	(	network_simplex_ctx_t *	ctx,
		Agnode_t *	v
	)

static

Definition at line 403 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 757 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 953 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 813 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 ( network_simplex_ctx_t * ctx )

static

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

References aghead, agtail, ED_cutvalue, ED_minlen, ED_tree_index, network_simplex_ctx_t::G, GD_nlist, gv_calloc(), nlist_t::list, elist::list, network_simplex_ctx_t::N_edges, network_simplex_ctx_t::N_nodes, ND_in, ND_mark, ND_next, ND_out, ND_priority, ND_rank, ND_tree_in, ND_tree_out, network_simplex_ctx_t::S_i, network_simplex_ctx_t::Tree_edge, and network_simplex_ctx_t::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 ( network_simplex_ctx_t * ctx )

static

Definition at line 155 of file ns.c.

References agerr(), agerrorf(), aghead, agnameof(), AGPREV, agtail, ED_minlen, network_simplex_ctx_t::G, GD_nlist, MAX, network_simplex_ctx_t::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 485 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 452 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 96 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 190 of file ns.c.

References cnt(), ED_cutvalue, elist::list, NULL, network_simplex_ctx_t::S_i, network_simplex_ctx_t::Search_size, elist::size, and network_simplex_ctx_t::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 ( network_simplex_ctx_t * ctx )

static

Definition at line 768 of file ns.c.

References aghead, agtail, delta, ED_cutvalue, enter_edge(), freeTreeList(), network_simplex_ctx_t::G, elist::list, ND_lim, NULL, rerank(), elist::size, SLACK, and network_simplex_ctx_t::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	(	network_simplex_ctx_t *	ctx,
		Agedge_t *	e
	)

static

Definition at line 560 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 313 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 1061 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 982 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(), network_simplex_ctx_t::N_edges, network_simplex_ctx_t::N_nodes, PRISIZE_T, reset_lists(), scan_and_normalize(), network_simplex_ctx_t::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 669 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 747 of file ns.c.

References free(), nlist_t::list, elist::list, network_simplex_ctx_t::Tree_edge, and network_simplex_ctx_t::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 ( network_simplex_ctx_t * ctx )

static

Definition at line 730 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 515 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 526 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 494 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 492 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 422 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 432 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 835 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(), 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 network_simplex_ctx_t::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	(	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, 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 541 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 646 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 687 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 1075 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 1104 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

Functions

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