1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#ifndef SPRING_ELECTRICAL_H
15#define SPRING_ELECTRICAL_H
16
17#include <SparseMatrix.h>
18
19enum {ERROR_NOT_SQUARE_MATRIX = -100};
20
21/* a flag to indicate that p should be set auto */
22#define AUTOP -1.0001234
23
24enum {SMOOTHING_NONE, SMOOTHING_STRESS_MAJORIZATION_GRAPH_DIST, SMOOTHING_STRESS_MAJORIZATION_AVG_DIST, SMOOTHING_STRESS_MAJORIZATION_POWER_DIST, SMOOTHING_SPRING, SMOOTHING_TRIANGLE, SMOOTHING_RNG};
25
26enum {QUAD_TREE_HYBRID_SIZE = 10000};
27
28enum {QUAD_TREE_NONE = 0, QUAD_TREE_NORMAL, QUAD_TREE_FAST, QUAD_TREE_HYBRID};
29
30enum {METHOD_STA = -1, METHOD_SPRING_ELECTRICAL, METHOD_SPRING_MAXENT, METHOD_STRESS_MAXENT, METHOD_STRESS_APPROX, METHOD_STRESS, METHOD_UNIFORM_STRESS, METHOD_FULL_STRESS, METHOD_NONE, METHOD_STO};
31
32struct spring_electrical_control_struct {
33 real p;/*a negativve real number default to -1. repulsive force = dist^p */
34 real q;/*a positive real number default to 2. attractive force = dist^q */
35 int random_start;/* whether to apply SE from a random layout, or from exisiting layout */
36 real K;/* the natural distance. If K < 0, K will be set to the average distance of an edge */
37 real C;/* another parameter. f_a(i,j) = C*dist(i,j)^2/K * d_ij, f_r(i,j) = K^(3-p)/dist(i,j)^(-p). By default C = 0.2. */
38 int multilevels;/* if <=1, single level */
39 int multilevel_coarsen_scheme;/* pass on to Multilevel_control->coarsen_scheme */
40 int multilevel_coarsen_mode;/* pass on to Multilevel_control->coarsen_mode */
41 int quadtree_size;/* cut off size above which quadtree approximation is used */
42 int max_qtree_level;/* max level of quadtree */
43 real bh;/* Barnes-Hutt constant, if width(snode)/dist[i,snode] < bh, treat snode as a supernode. default 0.2*/
44 real tol;/* minimum different between two subsequence config before terminating. ||x-xold|| < tol */
45 int maxiter;
46 real cool;/* default 0.9 */
47 real step;/* initial step size */
48 int adaptive_cooling;
49 int random_seed;
50 int beautify_leaves;
51 int use_node_weights;
52 int smoothing;
53 int overlap;
54 int do_shrinking;
55 int tscheme; /* octree scheme. 0 (no octree), 1 (normal), 2 (fast) */
56 int method;/* spring_electical, spring_maxent */
57 real initial_scaling;/* how to scale the layout of the graph before passing to overlap removal algorithm.
58 positive values are absolute in points, negative values are relative
59 to average label size.
60 */
61 real rotation;/* degree of rotation */
62 int edge_labeling_scheme; /* specifying whether to treat node of the form |edgelabel|* as a special node representing an edge label.
63 0 (no action, default), 1 (penalty based method to make that kind of node close to the center of its neighbor),
64 1 (penalty based method to make that kind of node close to the old center of its neighbor),
65 3 (two step process of overlap removal and straightening) */
66};
67
68typedef struct spring_electrical_control_struct *spring_electrical_control;
69
70spring_electrical_control spring_electrical_control_new(void);
71void spring_electrical_control_print(spring_electrical_control ctrl);
72
73void spring_electrical_embedding(int dim, SparseMatrix A0, spring_electrical_control ctrl, real *node_weights, real *x, int *flag);
74void spring_electrical_embedding_fast(int dim, SparseMatrix A0, spring_electrical_control ctrl, real *node_weights, real *x, int *flag);
75
76void multilevel_spring_electrical_embedding(int dim, SparseMatrix A0, SparseMatrix D, spring_electrical_control ctrl, real *node_weights, real *label_sizes,
77 real *x, int n_edge_label_nodes, int *edge_label_nodes, int *flag);
78
79void export_embedding(FILE *fp, int dim, SparseMatrix A, real *x, real *width);
80void spring_electrical_control_delete(spring_electrical_control ctrl);
81void print_matrix(real *x, int n, int dim);
82
83real average_edge_length(SparseMatrix A, int dim, real *coord);
84
85void spring_electrical_spring_embedding(int dim, SparseMatrix A, SparseMatrix D, spring_electrical_control ctrl, real *node_weights, real *x, int *flag);
86void force_print(FILE *fp, int n, int dim, real *x, real *force);
87
88enum {MAX_I = 20, OPT_UP = 1, OPT_DOWN = -1, OPT_INIT = 0};
89struct oned_optimizer_struct{
90 int i;
91 real work[MAX_I+1];
92 int direction;
93};
94typedef struct oned_optimizer_struct *oned_optimizer;
95void oned_optimizer_delete(oned_optimizer opt);
96oned_optimizer oned_optimizer_new(int i);
97void oned_optimizer_train(oned_optimizer opt, real work);
98int oned_optimizer_get(oned_optimizer opt);
99void interpolate_coord(int dim, SparseMatrix A, real *x);
100int power_law_graph(SparseMatrix A);
101void pcp_rotate(int n, int dim, real *x);
102#endif
103