spring_electrical.c File Reference

#include "config.h"
#include <cgraph/list.h>
#include <sparse/SparseMatrix.h>
#include <sfdpgen/spring_electrical.h>
#include <sparse/QuadTree.h>
#include <sfdpgen/Multilevel.h>
#include <sfdpgen/post_process.h>
#include <neatogen/overlap.h>
#include <common/types.h>
#include <common/arith.h>
#include <math.h>
#include <common/globals.h>
#include <stdbool.h>
#include <stddef.h>
#include <string.h>
#include <time.h>
#include <util/agxbuf.h>
#include <util/alloc.h>
#include <util/bitarray.h>

Include dependency graph for spring_electrical.c:

Go to the source code of this file.

Data Structures
struct	oned_optimizer

Macros
#define	node_degree(i)   (ia[(i)+1] - ia[(i)])

Enumerations
enum	{ MAX_I = 20 , OPT_UP = 1 , OPT_DOWN = -1 , OPT_INIT = 0 }

Functions
spring_electrical_control	spring_electrical_control_new (void)
void	spring_electrical_control_delete (spring_electrical_control ctrl)
void	spring_electrical_control_print (spring_electrical_control ctrl)
static oned_optimizer	oned_optimizer_new (int i)
static void	oned_optimizer_train (oned_optimizer *opt, double work)
static int	oned_optimizer_get (const oned_optimizer opt)
double	average_edge_length (SparseMatrix A, int dim, double *coord)
static double	update_step (bool adaptive_cooling, double step, double Fnorm, double Fnorm0)
static void	set_leaves (double *x, int dim, double dist, double ang, int i, int j)
static void	beautify_leaves (int dim, SparseMatrix A, double *x)
void	spring_electrical_embedding_fast (int dim, SparseMatrix A0, spring_electrical_control ctrl, double *x, int *flag)
static void	spring_electrical_embedding_slow (int dim, SparseMatrix A0, spring_electrical_control ctrl, double *x, int *flag)
void	spring_electrical_embedding (int dim, SparseMatrix A0, spring_electrical_control ctrl, double *x, int *flag)
void	spring_electrical_spring_embedding (int dim, SparseMatrix A0, SparseMatrix D, spring_electrical_control ctrl, double *x, int *flag)
static void	interpolate_coord (int dim, SparseMatrix A, double *x)
static void	prolongate (int dim, SparseMatrix A, SparseMatrix P, SparseMatrix R, double *x, double *y, double delta)
static bool	power_law_graph (SparseMatrix A)
void	pcp_rotate (int n, int dim, double *x)
static void	rotate (int n, int dim, double *x, double angle)
static void	attach_edge_label_coordinates (int dim, SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes, double *x, double *x2)
static SparseMatrix	shorting_edge_label_nodes (SparseMatrix A, int n_edge_label_nodes, int *edge_label_nodes)
void	multilevel_spring_electrical_embedding (int dim, SparseMatrix A0, spring_electrical_control ctrl, double *label_sizes, double *x, int n_edge_label_nodes, int *edge_label_nodes, int *flag)

Variables
static const double	C = 0.2
static const int	quadtree_size = 45
	cut off size above which quadtree approximation is used
static const double	bh = 0.6
static const double	tol = 0.001
static const double	cool = 0.90
static char *	smoothings []
static char *	tschemes []

Macro Definition Documentation

node_degree

#define node_degree

(

i

)

(ia[(i)+1] - ia[(i)])

Definition at line 190 of file spring_electrical.c.

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
MAX_I
OPT_UP
OPT_DOWN
OPT_INIT

Definition at line 103 of file spring_electrical.c.

Function Documentation

attach_edge_label_coordinates()

static void attach_edge_label_coordinates ( int  dim, SparseMatrix  A, int  n_edge_label_nodes, int *  edge_label_nodes, double *  x, double *  x2  )

static

Definition at line 972 of file spring_electrical.c.

References A, dim, free(), gv_calloc(), and len().

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

average_edge_length()

double average_edge_length	(	SparseMatrix	A,
		int	dim,
		double *	coord
	)

Definition at line 155 of file spring_electrical.c.

References A, coord(), dim, dist(), and SparseMatrix_is_symmetric().

Referenced by spring_electrical_embedding(), spring_electrical_embedding_fast(), spring_electrical_embedding_slow(), and spring_electrical_spring_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

beautify_leaves()

static void beautify_leaves ( int  dim, SparseMatrix  A, double *  x  )

static

Definition at line 199 of file spring_electrical.c.

References A, bitarray_get(), bitarray_new(), bitarray_reset(), bitarray_set(), dim, dist(), distance(), M_PI, node_degree, set_leaves(), and SparseMatrix_has_diagonal().

Referenced by spring_electrical_embedding(), spring_electrical_embedding_fast(), spring_electrical_embedding_slow(), and spring_electrical_spring_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

interpolate_coord()

static void interpolate_coord ( int  dim, SparseMatrix  A, double *  x  )

static

Definition at line 826 of file spring_electrical.c.

References A, alpha, dim, free(), and gv_calloc().

Referenced by prolongate().

Here is the call graph for this function:

Here is the caller graph for this function:

multilevel_spring_electrical_embedding()

void multilevel_spring_electrical_embedding	(	int	dim,
		SparseMatrix	A0,
		spring_electrical_control	ctrl,
		double *	label_sizes,
		double *	x,
		int	n_edge_label_nodes,
		int *	edge_label_nodes,
		int *	flag
	)

Definition at line 1081 of file spring_electrical.c.

References A, spring_electrical_control_struct::adaptive_cooling, attach_edge_label_coordinates(), AUTOP, dim, spring_electrical_control_struct::do_shrinking, spring_electrical_control_struct::edge_labeling_scheme, ELSCHEME_STRAIGHTLINE_PENALTY, ELSCHEME_STRAIGHTLINE_PENALTY2, free(), grid, gv_calloc(), spring_electrical_control_struct::initial_scaling, spring_electrical_control_struct::K, MATRIX_TYPE_REAL, Multilevel_control::maxlevel, Multilevel_delete(), Multilevel_get_coarsest(), Multilevel_is_coarsest, Multilevel_is_finest, Multilevel_new(), multilevel_spring_electrical_embedding(), spring_electrical_control_struct::multilevels, NULL, spring_electrical_control_struct::overlap, spring_electrical_control_struct::p, pcp_rotate(), post_process_smoothing(), power_law_graph(), print_padding(), prolongate(), QUAD_TREE_FAST, QUAD_TREE_HYBRID, QUAD_TREE_HYBRID_SIZE, QUAD_TREE_NONE, spring_electrical_control_struct::random_start, remove_overlap(), RETURN, rotate(), spring_electrical_control_struct::rotation, shorting_edge_label_nodes(), SparseMatrix_delete(), SparseMatrix_get_real_adjacency_matrix_symmetrized(), SparseMatrix_is_symmetric(), SparseMatrix_remove_diagonal(), spring_electrical_embedding(), spring_electrical_embedding_fast(), spring_electrical_embedding_slow(), spring_electrical_control_struct::step, spring_electrical_control_struct::tscheme, and Verbose.

Referenced by multilevel_spring_electrical_embedding(), and sfdpLayout().

Here is the call graph for this function:

Here is the caller graph for this function:

oned_optimizer_get()

static int oned_optimizer_get ( const oned_optimizer  opt )

static

Definition at line 150 of file spring_electrical.c.

References oned_optimizer::i.

Referenced by spring_electrical_embedding(), and spring_electrical_embedding_fast().

Here is the caller graph for this function:

oned_optimizer_new()

static oned_optimizer oned_optimizer_new ( int  i )

static

Definition at line 111 of file spring_electrical.c.

References oned_optimizer::direction, oned_optimizer::i, and OPT_INIT.

Referenced by spring_electrical_embedding(), and spring_electrical_embedding_fast().

Here is the caller graph for this function:

oned_optimizer_train()

static void oned_optimizer_train ( oned_optimizer *  opt, double  work  )

static

Definition at line 118 of file spring_electrical.c.

References oned_optimizer::direction, oned_optimizer::i, MAX, MAX_I, MIN, OPT_DOWN, OPT_INIT, OPT_UP, and oned_optimizer::work.

Referenced by spring_electrical_embedding(), and spring_electrical_embedding_fast().

Here is the caller graph for this function:

pcp_rotate()

void pcp_rotate	(	int	n,
		int	dim,
		double *	x
	)

Definition at line 890 of file spring_electrical.c.

References center(), dim, and dist().

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

power_law_graph()

static bool power_law_graph ( SparseMatrix  A )

static

Definition at line 866 of file spring_electrical.c.

References A, free(), gv_calloc(), and MAX.

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

prolongate()

static void prolongate ( int  dim, SparseMatrix  A, SparseMatrix  P, SparseMatrix  R, double *  x, double *  y, double  delta  )

static

Definition at line 849 of file spring_electrical.c.

References A, delta, dim, drand(), SparseMatrix_struct::ia, interpolate_coord(), SparseMatrix_struct::ja, SparseMatrix_struct::m, and SparseMatrix_multiply_dense().

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

rotate()

static void rotate ( int  n, int  dim, double *  x, double  angle  )

static

Definition at line 942 of file spring_electrical.c.

References center(), and dim.

Referenced by applyDelta(), multilevel_spring_electrical_embedding(), and stripedBox().

Here is the call graph for this function:

Here is the caller graph for this function:

set_leaves()

static void set_leaves ( double *  x, int  dim, double  dist, double  ang, int  i, int  j  )

static

Definition at line 192 of file spring_electrical.c.

References dim, and dist().

Referenced by beautify_leaves().

Here is the call graph for this function:

Here is the caller graph for this function:

shorting_edge_label_nodes()

static SparseMatrix shorting_edge_label_nodes ( SparseMatrix  A, int  n_edge_label_nodes, int *  edge_label_nodes  )

static

Definition at line 1016 of file spring_electrical.c.

References A, B, free(), gv_calloc(), SparseMatrix_struct::ia, MATRIX_TYPE_PATTERN, NULL, and SparseMatrix_from_coordinate_arrays().

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

spring_electrical_control_delete()

void spring_electrical_control_delete

(

spring_electrical_control

ctrl

)

Definition at line 72 of file spring_electrical.c.

References free().

Referenced by sfdp_layout(), and SpringSmoother_delete().

Here is the call graph for this function:

Here is the caller graph for this function:

spring_electrical_control_new()

spring_electrical_control spring_electrical_control_new

(

void

)

Definition at line 48 of file spring_electrical.c.

References spring_electrical_control_struct::adaptive_cooling, AUTOP, spring_electrical_control_struct::beautify_leaves, spring_electrical_control_struct::do_shrinking, spring_electrical_control_struct::edge_labeling_scheme, gv_alloc(), spring_electrical_control_struct::initial_scaling, spring_electrical_control_struct::K, spring_electrical_control_struct::max_qtree_level, spring_electrical_control_struct::maxiter, spring_electrical_control_struct::multilevels, spring_electrical_control_struct::overlap, spring_electrical_control_struct::p, QUAD_TREE_HYBRID, spring_electrical_control_struct::random_seed, spring_electrical_control_struct::random_start, spring_electrical_control_struct::rotation, spring_electrical_control_struct::smoothing, SMOOTHING_NONE, spring_electrical_control_struct::step, and spring_electrical_control_struct::tscheme.

Referenced by sfdp_layout(), and SpringSmoother_new().

Here is the call graph for this function:

Here is the caller graph for this function:

spring_electrical_control_print()

void spring_electrical_control_print

(

spring_electrical_control

ctrl

)

Definition at line 84 of file spring_electrical.c.

References spring_electrical_control_struct::adaptive_cooling, spring_electrical_control_struct::beautify_leaves, bh, C, cool, spring_electrical_control_struct::do_shrinking, spring_electrical_control_struct::edge_labeling_scheme, spring_electrical_control_struct::initial_scaling, spring_electrical_control_struct::K, spring_electrical_control_struct::max_qtree_level, spring_electrical_control_struct::maxiter, spring_electrical_control_struct::multilevels, spring_electrical_control_struct::overlap, spring_electrical_control_struct::p, quadtree_size, spring_electrical_control_struct::random_seed, spring_electrical_control_struct::random_start, spring_electrical_control_struct::rotation, spring_electrical_control_struct::smoothing, smoothings, spring_electrical_control_struct::step, tol, spring_electrical_control_struct::tscheme, and tschemes.

Referenced by sfdp_layout().

Here is the caller graph for this function:

spring_electrical_embedding()

void spring_electrical_embedding	(	int	dim,
		SparseMatrix	A0,
		spring_electrical_control	ctrl,
		double *	x,
		int *	flag
	)

Definition at line 519 of file spring_electrical.c.

References A, spring_electrical_control_struct::adaptive_cooling, average_edge_length(), beautify_leaves(), spring_electrical_control_struct::beautify_leaves, bh, C, center(), dim, dist(), distance(), distance_cropped(), drand(), ERROR_NOT_SQUARE_MATRIX, F, FORMAT_CSR, free(), gv_calloc(), spring_electrical_control_struct::K, MAX, spring_electrical_control_struct::max_qtree_level, spring_electrical_control_struct::maxiter, MINDIST, NULL, oned_optimizer_get(), oned_optimizer_new(), oned_optimizer_train(), spring_electrical_control_struct::p, QuadTree_delete(), QuadTree_get_supernodes(), QuadTree_new_from_point_list(), quadtree_size, spring_electrical_control_struct::random_seed, spring_electrical_control_struct::random_start, RETURN, SparseMatrix_delete(), SparseMatrix_symmetrize(), spring_electrical_control_struct::step, tol, update_step(), and Verbose.

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

spring_electrical_embedding_fast()

void spring_electrical_embedding_fast	(	int	dim,
		SparseMatrix	A0,
		spring_electrical_control	ctrl,
		double *	x,
		int *	flag
	)

Definition at line 246 of file spring_electrical.c.

References A, spring_electrical_control_struct::adaptive_cooling, average_edge_length(), beautify_leaves(), spring_electrical_control_struct::beautify_leaves, bh, C, dim, dist(), distance(), drand(), ERROR_NOT_SQUARE_MATRIX, F, FORMAT_CSR, free(), gv_calloc(), spring_electrical_control_struct::K, spring_electrical_control_struct::max_qtree_level, spring_electrical_control_struct::maxiter, NULL, oned_optimizer_get(), oned_optimizer_new(), oned_optimizer_train(), spring_electrical_control_struct::p, QuadTree_delete(), QuadTree_get_repulsive_force(), QuadTree_new_from_point_list(), spring_electrical_control_struct::random_seed, spring_electrical_control_struct::random_start, RETURN, SparseMatrix_delete(), SparseMatrix_symmetrize(), spring_electrical_control_struct::step, tol, update_step(), and Verbose.

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

spring_electrical_embedding_slow()

static void spring_electrical_embedding_slow ( int  dim, SparseMatrix  A0, spring_electrical_control  ctrl, double *  x, int *  flag  )

static

Definition at line 391 of file spring_electrical.c.

References A, spring_electrical_control_struct::adaptive_cooling, average_edge_length(), beautify_leaves(), spring_electrical_control_struct::beautify_leaves, C, dim, dist(), distance(), distance_cropped(), drand(), ERROR_NOT_SQUARE_MATRIX, F, FORMAT_CSR, free(), gv_calloc(), spring_electrical_control_struct::K, spring_electrical_control_struct::maxiter, NULL, spring_electrical_control_struct::p, spring_electrical_control_struct::random_seed, spring_electrical_control_struct::random_start, RETURN, SparseMatrix_delete(), SparseMatrix_symmetrize(), spring_electrical_control_struct::step, tol, update_step(), and Verbose.

Referenced by multilevel_spring_electrical_embedding().

Here is the call graph for this function:

Here is the caller graph for this function:

spring_electrical_spring_embedding()

void spring_electrical_spring_embedding	(	int	dim,
		SparseMatrix	A0,
		SparseMatrix	D,
		spring_electrical_control	ctrl,
		double *	x,
		int *	flag
	)

Definition at line 686 of file spring_electrical.c.

References A, spring_electrical_control_struct::adaptive_cooling, average_edge_length(), beautify_leaves(), spring_electrical_control_struct::beautify_leaves, bh, C, center(), D, dim, dist(), distance(), distance_cropped(), drand(), ERROR_NOT_SQUARE_MATRIX, F, FORMAT_CSR, free(), gv_calloc(), spring_electrical_control_struct::K, MAX, spring_electrical_control_struct::maxiter, MINDIST, NULL, spring_electrical_control_struct::p, QuadTree_delete(), QuadTree_get_supernodes(), QuadTree_new_from_point_list(), quadtree_size, spring_electrical_control_struct::random_seed, spring_electrical_control_struct::random_start, RETURN, SparseMatrix_delete(), SparseMatrix_symmetrize(), spring_electrical_control_struct::step, tol, and update_step().

Referenced by SpringSmoother_smooth().

Here is the call graph for this function:

Here is the caller graph for this function:

update_step()

static double update_step ( bool  adaptive_cooling, double  step, double  Fnorm, double  Fnorm0  )

static

Definition at line 173 of file spring_electrical.c.

References cool.

Referenced by spring_electrical_embedding(), spring_electrical_embedding_fast(), spring_electrical_embedding_slow(), and spring_electrical_spring_embedding().

Here is the caller graph for this function:

Variable Documentation

bh

const double bh = 0.6

static

Barnes-Hutt constant, if width(snode) ÷ dist[i, snode] < bh, treat snode as a supernode.

Definition at line 40 of file spring_electrical.c.

Referenced by QuadTree_get_repulsive_force(), QuadTree_get_supernodes(), QuadTree_get_supernodes_internal(), QuadTree_repulsive_force_interact(), spring_electrical_control_print(), spring_electrical_embedding(), spring_electrical_embedding_fast(), and spring_electrical_spring_embedding().

C

const double C = 0.2

static

another parameter fₐ(i, j) = C × dist(i , j)² ÷ K × dᵢⱼ, fᵣ(i, j) = K³⁻ᵖ ÷ dist(i, j)⁻ᵖ

Definition at line 33 of file spring_electrical.c.

Referenced by spring_electrical_control_print(), spring_electrical_embedding(), spring_electrical_embedding_fast(), spring_electrical_embedding_slow(), and spring_electrical_spring_embedding().

cool

const double cool = 0.90

static

Definition at line 46 of file spring_electrical.c.

Referenced by fdp_tLayout(), init_params(), spring_electrical_control_print(), update_step(), and x_layout().

quadtree_size

const int quadtree_size = 45

static

Definition at line 36 of file spring_electrical.c.

Referenced by spring_electrical_control_print(), spring_electrical_embedding(), and spring_electrical_spring_embedding().

smoothings

char* smoothings[]

static

Initial value:

= {
  "NONE", "STRESS_MAJORIZATION_GRAPH_DIST", "STRESS_MAJORIZATION_AVG_DIST", "STRESS_MAJORIZATION_POWER_DIST", "SPRING", "TRIANGLE", "RNG"
}

Definition at line 76 of file spring_electrical.c.

Referenced by spring_electrical_control_print().

tol

const double tol = 0.001

static

minimum different between two subsequence config before terminating. ||x - xold||_∞ < tol ÷ K

Definition at line 44 of file spring_electrical.c.

Referenced by cg(), check_compatibility(), conjugate_gradient(), conjugate_gradient(), conjugate_gradient_f(), conjugate_gradient_mkernel(), edge_bundling(), power_iteration(), SparseMatrix_solve(), spring_electrical_control_print(), spring_electrical_embedding(), spring_electrical_embedding_fast(), spring_electrical_embedding_slow(), spring_electrical_spring_embedding(), and StressMajorizationSmoother_smooth().

tschemes

char* tschemes[]

static

Initial value:

= {
  "NONE", "NORMAL", "FAST", "HYBRID"
}

Definition at line 80 of file spring_electrical.c.

Referenced by spring_electrical_control_print().