Project

General

Profile

Statistics
| Branch: | Revision:

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

History | View | Annotate | Download (6.41 KB)

1
//=========================================================================
2
//  GRAPHCOMPONENT.CC - 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
#include <float.h>
18
#include "graphcomponent.h"
19

    
20
USING_NAMESPACE
21

    
22
Vertex::Vertex(Pt pt, Rs rs, void *identity) {
23
    this->rc = Rc(pt, rs);
24
    this->identity = identity;
25

    
26
    color = 0;
27
    connectedSubComponent = NULL;
28
    spanningTreeParent = NULL;
29
    starTreeCenter = Pt::getNil();
30
    starTreeCircleCenter = Pt::getNil();
31
    starTreeRadius = -1;
32
}
33

    
34
Edge::Edge(Vertex *source, Vertex *target, void *identity) {
35
    this->source = source;
36
    this->target = target;
37
    this->identity = identity;
38

    
39
    color = 0;
40
    connectedSubComponent = NULL;
41
}
42

    
43
GraphComponent::GraphComponent() {
44
    owner = true;
45
    spanningTreeRoot = NULL;
46
}
47

    
48
GraphComponent::~GraphComponent() {
49
    if (owner) {
50
        for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++)
51
            delete *it;
52

    
53
        for (std::vector<Edge *>::iterator it = edges.begin(); it != edges.end(); it++)
54
            delete *it;
55

    
56
        for (std::vector<GraphComponent *>::iterator it = connectedSubComponents.begin(); it != connectedSubComponents.end(); it++)
57
            delete *it;
58
    }
59
}
60

    
61
int GraphComponent::addVertex(Vertex *vertex) {
62
    vertices.push_back(vertex);
63
    return vertices.size() - 1;
64
}
65

    
66
int GraphComponent::addEdge(Edge *edge) {
67
    edges.push_back(edge);
68
    edge->source->edges.push_back(edge);
69
    edge->target->edges.push_back(edge);
70
    edge->source->neighbours.push_back(edge->target);
71
    edge->target->neighbours.push_back(edge->source);
72
    return edges.size() - 1;
73
}
74

    
75
int GraphComponent::indexOfVertex(Vertex *vertex) {
76
    std::vector<Vertex *>::iterator it = find(vertices.begin(), vertices.end(), vertex);
77

    
78
    if (it == vertices.end())
79
        return -1;
80
    else
81
        return it - vertices.begin();
82
}
83

    
84
Vertex *GraphComponent::findVertex(void *identity)
85
{
86
    for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++) {
87
        Vertex *vertex = *it;
88

    
89
        if (vertex->identity == identity)
90
            return vertex;
91
    }
92

    
93
    return NULL;
94
}
95

    
96
Rc GraphComponent::getBoundingRectangle() {
97
    double top = DBL_MAX, bottom = DBL_MIN;
98
    double left = DBL_MAX, right = DBL_MIN;
99

    
100
    for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++) {
101
        Vertex *vertex = *it;
102

    
103
        Pt pt = vertex->rc.pt;
104
        Rs rs = vertex->rc.rs;
105

    
106
        top = std::min(top, pt.y);
107
        bottom = std::max(bottom, pt.y + rs.height);
108
        left = std::min(left, pt.x);
109
        right = std::max(right, pt.x + rs.width);
110
    }
111

    
112
    return Rc(left, top, 0, right - left, bottom - top);
113
}
114

    
115
void GraphComponent::calculateSpanningTree() {
116
    Vertex *rootVertex = NULL;
117
    spanningTreeVertices.clear();
118

    
119
    for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++) {
120
        Vertex *vertex = *it;
121

    
122
        if (rootVertex == NULL || rootVertex->neighbours.size() < vertex->neighbours.size())
123
            rootVertex = vertex;
124
    }
125

    
126
    if (vertices.size() != 0)
127
        calculateSpanningTree(rootVertex);
128
}
129

    
130
void GraphComponent::calculateSpanningTree(Vertex *rootVertex) {
131
    spanningTreeRoot = rootVertex;
132

    
133
    for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++) {
134
        Vertex *vertex = *it;
135
        vertex->spanningTreeChildren.clear();
136
        vertex->spanningTreeParent = NULL;
137
        vertex->color = 0;
138
    }
139

    
140
    addToSpanningTreeParent(NULL, rootVertex);
141
    std::deque<Vertex *> vertices;
142
    vertices.push_back(rootVertex);
143
    spanningTreeVertices.push_back(rootVertex);
144

    
145
    while (vertices.size() != 0) {
146
        Vertex *vertex = vertices[0];
147
        vertices.pop_front();
148

    
149
        for (std::vector<Vertex *>::iterator it = vertex->neighbours.begin(); it != vertex->neighbours.end(); it++) {
150
            Vertex *neighbour = *it;
151

    
152
            if (!neighbour->color) {
153
                addToSpanningTreeParent(vertex, neighbour);
154

    
155
                // breadth search
156
                vertices.push_back(neighbour);
157
                spanningTreeVertices.push_back(neighbour);
158
            }
159
        }
160
    }
161
}
162

    
163
void GraphComponent::addToSpanningTreeParent(Vertex *parentVertex, Vertex *vertex) {
164
    vertex->color = 1;
165
    vertex->spanningTreeParent = parentVertex;
166

    
167
    if (parentVertex)
168
        parentVertex->spanningTreeChildren.push_back(vertex);
169
}
170

    
171
void GraphComponent::calculateConnectedSubComponents() {
172
    connectedSubComponents.clear();
173

    
174
    for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++) {
175
        Vertex *vertex = *it;
176
        vertex->color = 0;
177
    }
178

    
179
    for (std::vector<Edge *>::iterator it = edges.begin(); it != edges.end(); it++) {
180
        Edge *edge = *it;
181
        edge->color = 0;
182
    }
183

    
184
    int color = 1;
185

    
186
    for (std::vector<Vertex *>::iterator it = vertices.begin(); it != vertices.end(); it++) {
187
        Vertex *vertex = *it;
188

    
189
        if (!vertex->color) {
190
            GraphComponent *childComponent = new GraphComponent();
191
            childComponent->owner = false;
192
            connectedSubComponents.push_back(childComponent);
193

    
194
            colorizeConnectedSubComponent(childComponent, vertex, color++);
195
        }
196
    }
197
}
198

    
199
void GraphComponent::colorizeConnectedSubComponent(GraphComponent *childComponent, Vertex *vertex, int color) {
200
    vertex->color = color;
201
    vertex->connectedSubComponent = childComponent;
202
    childComponent->vertices.push_back(vertex);
203

    
204
    for (std::vector<Edge *>::iterator it = vertex->edges.begin(); it != vertex->edges.end(); it++) {
205
        Edge *edge = *it;
206

    
207
        if (!edge->color) {
208
            edge->color = color;
209
            edge->connectedSubComponent = childComponent;
210
            childComponent->edges.push_back(edge);
211
        }
212
    }
213

    
214
    for (std::vector<Vertex *>::iterator it = vertex->neighbours.begin(); it != vertex->neighbours.end(); it++) {
215
        Vertex *neighbour = *it;
216

    
217
        if (!neighbour->color)
218
            colorizeConnectedSubComponent(childComponent, neighbour, color);
219
    }
220
}