inkscape/src/removeoverlap/solve_VPSC.cpp, branch livecoding An experimental livecoding plugin for Inkscape Previously graph layout was done using the Kamada-Kawai layout algorithm 2006-07-12T00:55:58+00:00 Tim Dwyer tgdwyer@gmail.com 2006-07-12T00:55:58+00:00 12b21e1d27f43deaa748419919b40b80cedd0ddd 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. (bzr r1394) 
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.

(bzr r1394)
 make loop var unsigned etc, remove compiler warnings 2006-05-23T07:41:37+00:00 Ralf Stephan ralf@ark.in-berlin.de 2006-05-23T07:41:37+00:00 9a0c3a49801cd0f84adf3d32d71d05ca45dca9d5 (bzr r974) 
(bzr r974)
 Apparently a problem was reported with one of the test cases. 2006-05-10T07:13:45+00:00 Tim Dwyer tgdwyer@gmail.com 2006-05-10T07:13:45+00:00 0623102c16ecbf5ade1a7ef195659826a6f92548 I can't reproduce the problem, however solve_VPSC code in inkscape was getting quite out of date with that in www.sf.net/projects/adaptagrams. I've updated the code, which may fix the problem, or at least if it's reported again then I'll know it's still an issue. (bzr r803) 
I can't reproduce the problem, however solve_VPSC code in inkscape
was getting quite out of date with that in www.sf.net/projects/adaptagrams.
I've updated the code, which may fix the problem, or at least if it's
reported again then I'll know it's still an issue.

(bzr r803)
 Fixed bug to do with comparison of invalid constraints in pairing heaps. 2006-01-26T05:32:20+00:00 Tim Dwyer tgdwyer@gmail.com 2006-01-26T05:32:20+00:00 bd5d4e5d36392293eeb966cfdf4b68cca2099a9f Also numerical problem with constraint generation fixed. (bzr r30) 
Also numerical problem with constraint generation fixed.

(bzr r30)
 moving trunk for module inkscape 2006-01-16T02:36:01+00:00 MenTaLguY mental@rydia.net 2006-01-16T02:36:01+00:00 179fa413b047bede6e32109e2ce82437c5fb8d34 (bzr r1) 
(bzr r1)