← Back to branch summary

~centralelyon2010/inkscape/imagelinks2

~centralelyon2010/inkscape/imagelinks2

« back to all changes in this revision

Viewing changes to src/libvpsc/variable.h

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.h

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

#ifndef SEEN_REMOVEOVERLAP_VARIABLE_H

11

#define SEEN_REMOVEOVERLAP_VARIABLE_H

12

13

#include <vector>

14

#include <iostream>

15

class Block;

16

class Constraint;

17

#include "block.h"

18

19

typedef std::vector<Constraint*> Constraints;

20

class Variable

21

{

22

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

23

public:

24

const int id; // useful in log files

25

double desiredPosition;

26

const double weight;

27

double offset;

28

Block *block;

29

bool visited;

30

Constraints in;

31

Constraints out;

32

char *toString();

33

inline Variable(const int id, const double desiredPos, const double weight)

34

: id(id)

35

, desiredPosition(desiredPos)

36

, weight(weight)

37

, offset(0)

38

, block(NULL)

39

, visited(false)

40

{

41

}

42

inline double position() const {

43

return block->posn+offset;

44

}

45

//double position() const;

46

~Variable(void){

47

in.clear();

48

out.clear();

49

}

50

};

51

#endif // SEEN_REMOVEOVERLAP_VARIABLE_H

Older »