~centralelyon2010/inkscape/imagelinks2

Committer: tgdwyer
Date: 2006-07-12 00:55:58 UTC
Revision ID: tgdwyer@users.sourceforge.net-20060712005558-4pqys3ou7f5er3dm

Previously graph layout was done using the Kamada-Kawai layout algorithm
implemented in Boost. I am replacing this with a custom implementation of
a constrained stress-majorization algorithm.

The stress-majorization algorithm is more robust and has better convergence
characteristics than Kamada-Kawai, and also simple constraints can be placed
on node position (for example, to enforce downward-pointing edges, non-overlap constraints, or cluster constraints).

Another big advantage is that we no longer need Boost.

I've tested the basic functionality, but I have yet to properly handle
disconnected graphs or to properly scale the resulting layout.

This commit also includes significant refactoring... the quadratic program solver - libvpsc (Variable Placement with Separation Constraints) has been moved to src/libvpsc and the actual graph layout algorithm is in libcola.

files added:
src/libcola

src/libcola/Makefile_insert

src/libcola/cola.cpp

src/libcola/cola.h

src/libcola/conjugate_gradient.cpp

src/libcola/conjugate_gradient.h

src/libcola/cycle_detector.cpp

src/libcola/cycle_detector.h

src/libcola/defs.h

src/libcola/gradient_projection.cpp

src/libcola/gradient_projection.h

src/libcola/shortest_paths.cpp

src/libcola/shortest_paths.h

src/libcola/straightener.cpp

src/libcola/straightener.h

src/libvpsc

src/libvpsc/COPYING

src/libvpsc/Makefile_insert

src/libvpsc/block.cpp

src/libvpsc/block.h

src/libvpsc/blocks.cpp

src/libvpsc/blocks.h

src/libvpsc/constraint.cpp

src/libvpsc/constraint.h

src/libvpsc/csolve_VPSC.cpp

src/libvpsc/csolve_VPSC.h

src/libvpsc/generate-constraints.cpp

src/libvpsc/generate-constraints.h

src/libvpsc/isnan.h

src/libvpsc/pairingheap

src/libvpsc/pairingheap/.dirstamp

src/libvpsc/pairingheap/PairingHeap.cpp

src/libvpsc/pairingheap/PairingHeap.h

src/libvpsc/pairingheap/dsexceptions.h

src/libvpsc/placement_SolveVPSC.h

src/libvpsc/remove_rectangle_overlap.cpp

src/libvpsc/remove_rectangle_overlap.h

src/libvpsc/solve_VPSC.cpp

src/libvpsc/solve_VPSC.h

src/libvpsc/variable.cpp

src/libvpsc/variable.h

files removed:
src/removeoverlap/block.cpp

src/removeoverlap/block.h

src/removeoverlap/blocks.cpp

src/removeoverlap/blocks.h

src/removeoverlap/constraint.cpp

src/removeoverlap/constraint.h

src/removeoverlap/generate-constraints.cpp

src/removeoverlap/generate-constraints.h

src/removeoverlap/pairingheap

src/removeoverlap/pairingheap/.cvsignore

src/removeoverlap/pairingheap/PairingHeap.cpp

src/removeoverlap/pairingheap/PairingHeap.h

src/removeoverlap/pairingheap/dsexceptions.h

src/removeoverlap/placement_SolveVPSC.cpp

src/removeoverlap/placement_SolveVPSC.h

src/removeoverlap/remove_rectangle_overlap-test.cpp

src/removeoverlap/remove_rectangle_overlap.cpp

src/removeoverlap/remove_rectangle_overlap.h

src/removeoverlap/solve_VPSC.cpp

src/removeoverlap/solve_VPSC.h

src/removeoverlap/variable.cpp

src/removeoverlap/variable.h

files modified:
configure.ac

mkinstalldirs

src/Makefile.am

src/Makefile_insert

src/graphlayout/graphlayout.cpp

src/removeoverlap/Makefile_insert

src/removeoverlap/removeoverlap.cpp

Show diffs side-by-side

added added

removed removed

src/libcola/cola.h

#ifndef COLA_H

#define COLA_H

#include <utility>

#include <iterator>

#include <vector>

#include <algorithm>

#include <cmath>

#include <iostream>

#include <cassert>

#include "shortest_paths.h"

#include "gradient_projection.h"

#include <libvpsc/generate-constraints.h>

#include "straightener.h"

typedef vector<unsigned> Cluster;

typedef vector<Cluster*> Clusters;

namespace cola {

typedef pair<unsigned, unsigned> Edge;

// defines references to three variables for which the goal function

// will be altered to prefer points u-b-v are in a linear arrangement

// such that b is placed at u+t(v-u).

struct LinearConstraint {

LinearConstraint(unsigned u, unsigned v, unsigned b, double w,

double frac_ub, double frac_bv,

double* X, double* Y)

: u(u),v(v),b(b),w(w),frac_ub(frac_ub),frac_bv(frac_bv),

tAtProjection(true)

{

assert(frac_ub<=1.0);

assert(frac_bv<=1.0);

assert(frac_ub>=0);

assert(frac_bv>=0);

if(tAtProjection) {

double uvx = X[v] - X[u],

uvy = Y[v] - Y[u],

vbx = X[b] - X[u],

vby = Y[b] - Y[u];

t = uvx * vbx + uvy * vby;

t/= uvx * uvx + uvy * uvy;

// p is the projection point of b on line uv

//double px = scalarProj * uvx + X[u];

//double py = scalarProj * uvy + Y[u];

// take t=|up|/|uv|

} else {

double numerator=X[b]-X[u];

double denominator=X[v]-X[u];

if(fabs(denominator)<0.001) {

// if line is close to vertical then use Y coords to compute T

numerator=Y[b]-Y[u];

denominator=Y[v]-Y[u];

}

if(fabs(denominator)<0.0001) {

denominator=1;

}

t=numerator/denominator;

}

duu=(1-t)*(1-t);

duv=t*(1-t);

dub=t-1;

dvv=t*t;

dvb=-t;

dbb=1;

//printf("New LC: t=%f\n",t);

}

unsigned u;

unsigned v;

unsigned b;

double w; // weight

double t;

// 2nd partial derivatives of the goal function

// (X[b] - (1-t) X[u] - t X[v])^2

double duu;

double duv;

double dub;

double dvv;

double dvb;

double dbb;

// Length of each segment as a fraction of the total edge length

double frac_ub;

double frac_bv;

bool tAtProjection;

};

typedef vector<LinearConstraint*> LinearConstraints;

class TestConvergence {

public:

double old_stress;

TestConvergence(const double& tolerance = 0.001, const unsigned maxiterations = 1000)

: old_stress(DBL_MAX),

tolerance(tolerance),

maxiterations(maxiterations),

iterations(0) { }

virtual ~TestConvergence() {}

virtual bool operator()(double new_stress, double* X, double* Y) {

100

//std::cout<<"iteration="<<iterations<<", new_stress="<<new_stress<<std::endl;

101

if (old_stress == DBL_MAX) {

102

old_stress = new_stress;

103

if(++iterations>=maxiterations) {;

104

return true;

105

} else {

106

return false;

107

}

108

}

109

bool converged =

110

fabs(new_stress - old_stress) / (new_stress + 1e-10) < tolerance

111

|| ++iterations > maxiterations;

112

old_stress = new_stress;

113

return converged;

114

}

115

private:

116

double tolerance;

117

unsigned maxiterations;

118

unsigned iterations;

119

};

120

static TestConvergence defaultTest(0.0001,100);

121

class ConstrainedMajorizationLayout {

122

public:

123

ConstrainedMajorizationLayout(

124

vector<Rectangle*>& rs,

125

vector<Edge>& es,

126

double* eweights,

127

double idealLength,

128

TestConvergence& done=defaultTest)

129

: constrainedLayout(false),

130

n(rs.size()),

131

lapSize(n), lap2(new double*[lapSize]),

132

Q(lap2), Dij(new double*[lapSize]),

133

tol(0.0001),

134

done(done),

135

X(new double[n]),

136

Y(new double[n]),

137

clusters(NULL),

138

linearConstraints(NULL),

139

gpX(NULL),

140

gpY(NULL),

141

straightenEdges(NULL)

142

{

143

assert(rs.size()==n);

144

boundingBoxes = new Rectangle*[rs.size()];

145

copy(rs.begin(),rs.end(),boundingBoxes);

146

147

double** D=new double*[n];

148

for(unsigned i=0;i<n;i++) {

149

D[i]=new double[n];

150

}

151

shortest_paths::johnsons(n,D,es,eweights);

152

edge_length = idealLength;

153

// Lij_{i!=j}=1/(Dij^2)

154

155

for(unsigned i = 0; i<n; i++) {

156

X[i]=rs[i]->getCentreX();

157

Y[i]=rs[i]->getCentreY();

158

double degree = 0;

159

lap2[i]=new double[n];

160

Dij[i]=new double[n];

161

for(unsigned j=0;j<n;j++) {

162

double w = edge_length * D[i][j];

163

Dij[i][j]=w;

164

if(i==j) continue;

165

degree+=lap2[i][j]=w>1e-30?1.f/(w*w):0;

166

}

167

lap2[i][i]=-degree;

168

delete [] D[i];

169

}

170

delete [] D;

171

}

172

173

void moveBoundingBoxes() {

174

for(unsigned i=0;i<lapSize;i++) {

175

boundingBoxes[i]->moveCentreX(X[i]);

176

boundingBoxes[i]->moveCentreY(Y[i]);

177

}

178

}

179

180

void setupConstraints(

181

AlignmentConstraints* acsx, AlignmentConstraints* acsy,

182

bool avoidOverlaps,

183

PageBoundaryConstraints* pbcx = NULL,

184

PageBoundaryConstraints* pbcy = NULL,

185

SimpleConstraints* scx = NULL,

186

SimpleConstraints* scy = NULL,

187

Clusters* cs = NULL,

188

vector<straightener::Edge*>* straightenEdges = NULL);

189

190

void addLinearConstraints(LinearConstraints* linearConstraints);

191

192

void setupDummyVars();

193

194

~ConstrainedMajorizationLayout() {

195

if(boundingBoxes) {

196

delete [] boundingBoxes;

197

}

198

if(constrainedLayout) {

199

delete gpX;

200

delete gpY;

201

}

202

for(unsigned i=0;i<lapSize;i++) {

203

delete [] lap2[i];

204

delete [] Dij[i];

205

}

206

delete [] lap2;

207

delete [] Dij;

208

delete [] X;

209

delete [] Y;

210

}

211

bool run();

212

void straighten(vector<straightener::Edge*>&, Dim);

213

bool avoidOverlaps;

214

bool constrainedLayout;

215

private:

216

double euclidean_distance(unsigned i, unsigned j) {

217

return sqrt(

218

(X[i] - X[j]) * (X[i] - X[j]) +

219

(Y[i] - Y[j]) * (Y[i] - Y[j]));

220

}

221

double compute_stress(double **Dij);

222

void majlayout(double** Dij,GradientProjection* gp, double* coords);

223

void majlayout(double** Dij,GradientProjection* gp, double* coords,

224

double* b);

225

unsigned n; // is lapSize + dummyVars

226

unsigned lapSize; // lapSize is the number of variables for actual nodes

227

double** lap2; // graph laplacian

228

double** Q; // quadratic terms matrix used in computations

229

double** Dij;

230

double tol;

231

TestConvergence& done;

232

Rectangle** boundingBoxes;

233

double *X, *Y;

234

Clusters* clusters;

235

double edge_length;

236

LinearConstraints *linearConstraints;

237

GradientProjection *gpX, *gpY;

238

vector<straightener::Edge*>* straightenEdges;

239

};

240

}

241

#endif // COLA_H

242

// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=4:softtabstop=4

Older »