Project

General

Profile

Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (5.69 KB)

1
//=========================================================================
2
//  GRAPHCOMPONENT.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 __GRAPHCOMPONENT_H_
18
#define __GRAPHCOMPONENT_H_
19

    
20
#include <algorithm>
21
#include <vector>
22
#include <deque>
23
#include "geometry.h"
24

    
25
NAMESPACE_BEGIN
26

    
27
class Edge;
28
class GraphComponent;
29

    
30
/**
31
 * A vertex in a graph component.
32
 */
33
class Vertex {
34
    public:
35
        /**
36
         * All neighbours of this vertex. Updated during building the graph.
37
         */
38
        std::vector<Vertex *> neighbours;
39

    
40
        /**
41
         * All incoming and outgoing edges. Updated during building the graph.
42
         */
43
        std::vector<Edge *> edges;
44

    
45
        /**
46
         * Position and size assigned to this vertex. Embedding algorithms will set
47
         * the position here.
48
         */
49
        Rc rc;
50

    
51
        /**
52
         * Used to look up the vertex. Not used by any graph algorithm.
53
         */
54
        void *identity;
55

    
56
        /**
57
         * The parent of this vertex in the spanning tree. Filled by calculateSpanningTree in
58
         * the owner graphComponent.
59
         */
60
        Vertex *spanningTreeParent;
61

    
62
        /**
63
         * Children vertices of this vertex in the spanning tree. Filled by calculateSpanningTree in
64
         * the owner graphComponent.
65
         */
66
        std::vector<Vertex *> spanningTreeChildren;
67

    
68
        /**
69
         * The connected graph component this vertex is part of. Filled by calculateConnectedSubComponents
70
         * in the owner graphComponent.
71
         */
72
        GraphComponent *connectedSubComponent;
73

    
74
        /**
75
         * Used to colorize the vertex in graph algorithms.
76
         */
77
        int color;
78

    
79
        /**
80
         * Center coordinate relative to parent.
81
         */
82
        Pt starTreeCenter;
83

    
84
        /**
85
         * Subtree enclosing circle center.
86
         */
87
        Pt starTreeCircleCenter;
88

    
89
        /**
90
         * Subtree enclosing circle radius.
91
         */
92
        double starTreeRadius;
93

    
94
    public:
95
        Vertex(Pt pt, Rs rc, void *identity = NULL);
96
};
97

    
98
/**
99
 * An edge between two vertices in a graph component.
100
 */
101
class Edge {
102
    public:
103
        /**
104
         * One of the vertices where the edge ends.
105
         */
106
        Vertex *source;
107

    
108
        /**
109
         * One of the vertices where the edge ends.
110
         */
111
        Vertex *target;
112

    
113
        /**
114
         * Used to look up the edge. Not used by any graph algorithm.
115
         */
116
        void *identity;
117

    
118
        /**
119
         * The connected graph component this edge is part of. Filled by calculateConnectedSubComponents
120
         * in the owner graphComponent.
121
         */
122
        GraphComponent *connectedSubComponent;
123

    
124
        /**
125
         * Used to colorize the edge in graph algorithms.
126
         */
127
        int color;
128

    
129
    public:
130
        Edge(Vertex *source, Vertex *target, void *identity = NULL);
131
};
132

    
133
/**
134
 * A graph or a connected component of a graph.
135
 */
136
class GraphComponent {
137
    private:
138
        /**
139
         * True means this graphComponent owns the vertices and edges so it will
140
         * delete them in the descructor.
141
         */
142
        bool owner;
143

    
144
        /**
145
         * A list of vertices present in this component.
146
         */
147
        std::vector<Vertex *> vertices;
148

    
149
        /**
150
         * A list of edges present in this component.
151
         */
152
        std::vector<Edge *> edges;
153

    
154
    public:
155
        /**
156
         * The root of the spanning tree. Filled by calculateSpanningTree.
157
         */
158
        Vertex *spanningTreeRoot;
159

    
160
        /**
161
         * Contains all vertices in the order of the spanning tree traversal.
162
         */
163
        std::vector<Vertex *> spanningTreeVertices;
164

    
165
        /**
166
         * A list of connected sub graph components. These components do not own the
167
         * vertices and edges present in this component but still refer to them.
168
         */
169
        std::vector<GraphComponent *> connectedSubComponents;
170

    
171
    public:
172
        GraphComponent();
173
        ~GraphComponent();
174

    
175
        int addVertex(Vertex *vertex);
176
        int addEdge(Edge *edge);
177
        int indexOfVertex(Vertex *vertex);
178
        Vertex *findVertex(void *identity);
179
        Rc getBoundingRectangle();
180

    
181
        /**
182
         * Calculates the spanning tree using breadth search starting from the
183
         * vertex having the highest rank.
184
         */
185
        void calculateSpanningTree();
186
        void calculateSpanningTree(Vertex *rootVertex);
187

    
188
        /**
189
         * Calculates the list of connected sub graph components by colorizing vertices and edges.
190
         */
191
        void calculateConnectedSubComponents();
192

    
193
        bool isEmpty() {
194
            return vertices.size() == 0;
195
        }
196

    
197
        int getVertexCount() {
198
            return vertices.size();
199
        }
200

    
201
        std::vector<Vertex *>& getVertices() {
202
            return vertices;
203
        }
204

    
205
        Vertex *getVertex(int index) {
206
            return vertices[index];
207
        }
208

    
209
        int getEdgeCount() {
210
            return edges.size();
211
        }
212

    
213
        std::vector<Edge *> getEdges() {
214
            return edges;
215
        }
216

    
217
        Edge *getEdge(int index) {
218
            return edges[index];
219
        }
220

    
221
    private:
222
        void addToSpanningTreeParent(Vertex *parentVertex, Vertex *vertex);
223
        void colorizeConnectedSubComponent(GraphComponent *childComponent, Vertex *vertex, int color);
224
};
225

    
226
NAMESPACE_END
227

    
228

    
229
#endif