1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
|
/*
* $Revision: 3188 $
*
* last checkin:
* $Author: gutwenger $
* $Date: 2013-01-10 09:53:32 +0100 (Thu, 10 Jan 2013) $
***************************************************************/
/** \file
* \brief Declaration of ClusterPlanRep class, allowing cluster
* boundary insertion and shortest path edge insertion
*
* \author Karsten Klein
*
* \par License:
* This file is part of the Open Graph Drawing Framework (OGDF).
*
* \par
* Copyright (C)<br>
* See README.txt in the root directory of the OGDF installation for details.
*
* \par
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* Version 2 or 3 as published by the Free Software Foundation;
* see the file LICENSE.txt included in the packaging of this file
* for details.
*
* \par
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* \par
* You should have received a copy of the GNU General Public
* License along with this program; if not, write to the Free
* Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
* \see http://www.gnu.org/copyleft/gpl.html
***************************************************************/
#ifdef _MSC_VER
#pragma once
#endif
#ifndef OGDF_CLUSTER_PLAN_REP_H
#define OGDF_CLUSTER_PLAN_REP_H
#include <ogdf/planarity/PlanRep.h>
#include <ogdf/cluster/ClusterGraphAttributes.h>
#include <ogdf/cluster/ClusterGraph.h>
#include <ogdf/cluster/ClusterArray.h>
#include <ogdf/basic/HashArray.h>
namespace ogdf {
class OGDF_EXPORT ClusterPlanRep : public PlanRep
{
public:
ClusterPlanRep(
const ClusterGraphAttributes &acGraph,
const ClusterGraph &clusterGraph);
virtual ~ClusterPlanRep() { }
void initCC(int i);
//edge on the cluster boundary, adjSource
void setClusterBoundary(edge e) {
setEdgeTypeOf(e, edgeTypeOf(e) | clusterPattern());
}
bool isClusterBoundary(edge e) {
return ((edgeTypeOf(e) & clusterPattern()) == clusterPattern());
}
const ClusterGraph &getClusterGraph() const {
return *m_pClusterGraph;
}
/** re-inserts edge eOrig by "crossing" the edges in crossedEdges;
* splits each edge in crossedEdges
* Precond.: eOrig is an edge in the original graph,
* the edges in crossedEdges are in this graph,
* cluster boundaries are modelled as edge paths
* \param eOrig: Original edge to be inserted
* \param crossedEdges: Edges that are crossed by this insertion
* \param E: The embedding in which the edge is inserted
*/
void insertEdgePathEmbedded(
edge eOrig,
CombinatorialEmbedding &E,
const SList<adjEntry> &crossedEdges);
void ModelBoundaries();
//rootadj is set by ModelBoundaries
adjEntry externalAdj() { return m_rootAdj; }
//*************************************************************************
//structural alterations
// Expands nodes with degree > 4 and merge nodes for generalizations
virtual void expand(bool lowDegreeExpand = false);
virtual void expandLowDegreeVertices(OrthoRep &OR);
//splits edge e, updates clustercage lists if necessary and returns new edge
virtual edge split(edge e)
{
edge eNew = PlanRep::split(e);
//update edge to cluster info
m_edgeClusterID[eNew] = m_edgeClusterID[e];
m_nodeClusterID[eNew->source()] = m_edgeClusterID[e];
return eNew;
}//split
//returns cluster of edge e
//edges only have unique numbers if clusters are already modelled
//we derive the edge cluster from the endnode cluster information
cluster clusterOfEdge(edge e)
{
OGDF_ASSERT(m_clusterOfIndex.isDefined(ClusterID(e->source())))
OGDF_ASSERT(m_clusterOfIndex.isDefined(ClusterID(e->target())))
OGDF_ASSERT(
(ClusterID(e->source()) == ClusterID(e->target())) ||
(clusterOfIndex(ClusterID(e->source())) ==
clusterOfIndex(ClusterID(e->target()))->parent()) ||
(clusterOfIndex(ClusterID(e->target())) ==
clusterOfIndex(ClusterID(e->source()))->parent()) ||
(clusterOfIndex(ClusterID(e->target()))->parent() ==
clusterOfIndex(ClusterID(e->source()))->parent())
)
if (ClusterID(e->source()) == ClusterID(e->target()))
return clusterOfIndex(ClusterID(e->target()));
if (clusterOfIndex(ClusterID(e->source())) ==
clusterOfIndex(ClusterID(e->target()))->parent())
return clusterOfIndex(ClusterID(e->source()));
if (clusterOfIndex(ClusterID(e->target())) ==
clusterOfIndex(ClusterID(e->source()))->parent())
return clusterOfIndex(ClusterID(e->target()));
if (clusterOfIndex(ClusterID(e->target()))->parent() ==
clusterOfIndex(ClusterID(e->source()))->parent())
return clusterOfIndex(ClusterID(e->source()))->parent();
OGDF_THROW(AlgorithmFailureException);
//return 0;
}//clusterOfEdge
inline int ClusterID(node v) const {return m_nodeClusterID[v];}
inline int ClusterID(edge e) const {return m_edgeClusterID[e];}
cluster clusterOfIndex(int i) {return m_clusterOfIndex[i];}
inline cluster clusterOfDummy(node v)
{
OGDF_ASSERT(!original(v))
OGDF_ASSERT(ClusterID(v) != -1)
return clusterOfIndex(ClusterID(v));
}
//output functions
void writeGML(const char *fileName, const Layout &drawing);
void writeGML(const char *fileName);
void writeGML(ostream &os, const Layout &drawing);
protected:
//insert boundaries for all given clusters
void convertClusterGraph(cluster act,
AdjEntryArray<edge>& currentEdge,
AdjEntryArray<int>& outEdge);
//insert edges to represent the cluster boundary
void insertBoundary(cluster C,
AdjEntryArray<edge>& currentEdge,
AdjEntryArray<int>& outEdge,
bool clusterIsLeaf);
//reinsert edges to planarize the graph after convertClusterGraph
void reinsertEdge(edge e);
private:
const ClusterGraph *m_pClusterGraph;
edgeType clusterPattern() { return etcSecCluster << etoSecondary; }
adjEntry m_rootAdj; //connects cluster on highest level with non cluster or
//same level
//******************
EdgeArray<int> m_edgeClusterID;
NodeArray<int> m_nodeClusterID;
//we maintain an array of index to cluster mappings (CG is const)
//cluster numbers don't need to be consecutive
HashArray<int, cluster> m_clusterOfIndex;
};
}//namespace
#endif
|
