Project

General

Profile

Statistics
| Branch: | Revision:

root / src / layout / startreeembedding.h @ 8aeaaccc

History | View | Annotate | Download (2.52 KB)

1
//=========================================================================
2
//  STARTREEEMBEDDING.H - part of
3
//                  OMNeT++/OMNEST
4
//           Discrete System Simulation in C++
5
//
6
//  Author: Levente Meszaros
7
//
8
//=========================================================================
9

    
10
/*--------------------------------------------------------------*
11
  Copyright (C) 2006-2008 OpenSim Ltd.
12

13
  This file is distributed WITHOUT ANY WARRANTY. See the file
14
  `license' for details on this and other legal matters.
15
*--------------------------------------------------------------*/
16

    
17
#ifndef __STARTREEEMBEDDING_H_
18
#define __STARTREEEMBEDDING_H_
19

    
20
#include "vector"
21
#include "geometry.h"
22
#include "graphcomponent.h"
23

    
24
NAMESPACE_BEGIN
25

    
26
/**
27
 * This is a planar graph embedding for a connected graph component with spanning tree.
28
 *
29
 * Vertices are positioned recursively accoring to the spanning tree as follows.
30
 * The parent vertex is positioned in the center and its sub trees are positioned around it.
31
 * The parent vertex and each subtree is modelled with a circle and the circles
32
 * are positioned on the plane by putting one circle next to two already positioned ones.
33
 * The best circle position for a child subtree circle is the one which minimizes the distance
34
 * from the parent circle. When all child subtrees are positioned the parent tree is wrapped
35
 * by the smallest radius circle.
36
 *
37
 * The second pass rotates the subtree circles in place to move the weight point of the subtree
38
 * opposite to the parent.
39
 *
40
 * The resulting embedding will not have overlapping vertices.
41
 */
42
class StarTreeEmbedding
43
{
44
    public:
45
        /**
46
         * Minimum distance between vertices
47
         */
48
        double vertexSpacing;
49

    
50
    private:
51
        /**
52
         * A connected graph component which must have a spanning tree.
53
         */
54
        GraphComponent *graphComponent;
55

    
56
    public:
57
        StarTreeEmbedding(GraphComponent *graphComponent, double vertexSpacing);
58
        void embed();
59

    
60
    private:
61
        /**
62
         * Calculates center coordinates relative to parents.
63
         */
64
        void calculateCenter();
65
        void calculateCenterRecursive(Vertex *vertex);
66

    
67
        /**
68
         * Rotate the child subtrees to have the weight point opposite to the parent.
69
         */
70
        void rotateCenter();
71
        void rotateCenterRecursive(Vertex *vertex);
72

    
73
        /**
74
         * Calculates absolute positions.
75
         */
76
        void calculatePosition();
77
        void calculatePositionRecursive(Vertex *vertex, Pt pt);
78
};
79

    
80
NAMESPACE_END
81

    
82

    
83
#endif