← Back to branch summary

~centralelyon2010/inkscape/imagelinks2

~centralelyon2010/inkscape/imagelinks2

« back to all changes in this revision

Viewing changes to src/libvpsc/variable.cpp

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/libvpsc/variable.cpp

1

/**

2

*

3

* Authors:

4

* Tim Dwyer <tgdwyer@gmail.com>

5

*

6

* Copyright (C) 2005 Authors

7

*

8

* Released under GNU LGPL. Read the file 'COPYING' for more information.

9

*/

10

#include "variable.h"

11

std::ostream& operator <<(std::ostream &os, const Variable &v) {

12

os << "(" << v.id << "=" << v.position() << ")";

13

return os;

14

}

15

Older »