6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of Tutte's Algorithm
12 * \author David Alberts \and Andrea Wagner
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
45 #include <ogdf/basic/Math.h>
46 #include <ogdf/energybased/CoinTutteLayout.h>
47 #include <ogdf/basic/GraphCopyAttributes.h>
48 #include <ogdf/basic/extended_graph_alg.h>
52 // solves a system of linear equations with a linear solver for optimization problems.
53 // I'm sorry but there is no Gauss-Algorithm (or some numerical stuff) in OGDF...
56 const CoinPackedMatrix
&Matrix
,
57 const Array
<double> &rightHandSide
,
62 OsiSolverInterface
*osi
= CoinManager::createCorrectOsiSolverInterface();
64 // constructs a dummy optimization problem.
65 // The given system of equations is used as constraint.
66 osi
->setObjSense(-1); // maximize...
67 Array
<double> obj(0,cols
-1,1); // ...the sum of variables
68 Array
<double> lowerBound(0,cols
-1,-1*(osi
->getInfinity()));
69 Array
<double> upperBound(0,cols
-1,osi
->getInfinity());
71 // loads the problem to Coin-Osi
72 osi
->loadProblem(Matrix
, &lowerBound
[0], &upperBound
[0], &obj
[0], &rightHandSide
[0], &rightHandSide
[0]);
74 // solves the linear program
77 // gets the solution and returns true if it is optimal
78 const double *sol
= osi
->getColSolution();
79 for(i
=0; i
<cols
; i
++) x
[i
] = sol
[i
];
81 if(osi
->isProvenOptimal()) {
91 TutteLayout::TutteLayout()
93 m_bbox
= DRect (0.0, 0.0, 250.0, 250.0);
98 // sets the positions of the nodes in a largest face of G in the form
99 // of a regular k-gon. The corresponding nodes and their positions are
100 // stored in nodes and pos, respectively.
101 void TutteLayout::setFixedNodes(
107 // compute faces of a copy of G
110 // compute a planar embedding if \a G is planar
111 if(isPlanar(G
)) planarEmbed(GC
);
112 //FIXME this stuff above seems wrong!!
114 CombinatorialEmbedding
E(GC
);
117 // search for largest face
118 face maxFace
= E
.maximalFace();
120 // delete possible old entries in nodes and pos
125 NodeArray
<bool> addMe(GC
,true);
129 forall_face_adj(adj
,maxFace
) {
130 maxNodes
.pushBack(adj
->theNode());
133 forall_nonconst_listiterators(node
, it
, maxNodes
) {
141 double step
= 2.0 * Math::pi
/ (double)(nodes
.size());
143 forall_listiterators(node
, it
, nodes
) {
144 pos
.pushBack(DPoint(radius
* cos(alpha
), radius
* sin(alpha
)));
149 // Overload setFixedNodes for given nodes
150 void TutteLayout::setFixedNodes(
153 const List
<node
>& givenNodes
,
159 // delete possible old entries in nodes and pos
165 forall_listiterators(node
, it
, givenNodes
) {
167 node theCopy
= GC
.copy(theOrig
);
168 nodes
.pushBack(theCopy
);
171 double step
= 2.0 * Math::pi
/ (double)(nodes
.size());
173 forall_listiterators(node
, it
, nodes
) {
174 pos
.pushBack(DPoint(radius
* cos(alpha
), radius
* sin(alpha
)));
179 void TutteLayout::call(GraphAttributes
&AG
, const List
<node
> &givenNodes
)
181 const Graph
&G
= AG
.constGraph();
183 List
<node
> fixedNodes
;
184 List
<DPoint
> positions
;
187 sqrt((m_bbox
.width()) * (m_bbox
.width())
188 + (m_bbox
.height()) * (m_bbox
.height()));
190 // handle graphs with less than two nodes
191 switch (G
.numberOfNodes()) {
195 node v
= G
.firstNode();
197 DPoint
center(0.5 * m_bbox
.width(),0.5 * m_bbox
.height());
198 center
= center
+ m_bbox
.p1();
200 AG
.x(v
) = center
.m_x
;
201 AG
.y(v
) = center
.m_y
;
206 // increase radius to have no overlap on the outer circle
207 node v
= G
.firstNode();
209 double r
= diam
/2.8284271;
210 int n
= G
.numberOfNodes();
211 double nodeDiam
= 2.0*sqrt((AG
.width(v
)) * (AG
.width(v
))
212 + (AG
.height(v
)) * (AG
.height(v
)));
214 if(r
<nodeDiam
/(2*sin(2*Math::pi
/n
))) {
215 r
=nodeDiam
/(2*sin(2*Math::pi
/n
));
216 m_bbox
= DRect (0.0, 0.0, 2*r
, 2*r
);
219 setFixedNodes(G
,fixedNodes
,givenNodes
,positions
,r
);
221 doCall(AG
,fixedNodes
,positions
);
224 void TutteLayout::call(GraphAttributes
&AG
)
226 const Graph
&G
= AG
.constGraph();
228 List
<node
> fixedNodes
;
229 List
<DPoint
> positions
;
232 sqrt((m_bbox
.width()) * (m_bbox
.width())
233 + (m_bbox
.height()) * (m_bbox
.height()));
235 // handle graphs with less than two nodes
236 switch (G
.numberOfNodes()) {
240 node v
= G
.firstNode();
242 DPoint
center(0.5 * m_bbox
.width(),0.5 * m_bbox
.height());
243 center
= center
+ m_bbox
.p1();
245 AG
.x(v
) = center
.m_x
;
246 AG
.y(v
) = center
.m_y
;
251 // increase radius to have no overlap on the outer circle
252 node v
= G
.firstNode();
254 double r
= diam
/2.8284271;
255 int n
= G
.numberOfNodes();
256 double nodeDiam
= 2.0*sqrt((AG
.width(v
)) * (AG
.width(v
))
257 + (AG
.height(v
)) * (AG
.height(v
)));
259 if(r
<nodeDiam
/(2*sin(2*Math::pi
/n
))) {
260 r
=nodeDiam
/(2*sin(2*Math::pi
/n
));
261 m_bbox
= DRect (0.0, 0.0, 2*r
, 2*r
);
264 setFixedNodes(G
,fixedNodes
,positions
,r
);
266 doCall(AG
,fixedNodes
,positions
);
271 // does the actual computation. fixedNodes and fixedPositions
272 // contain the nodes with fixed positions.
273 bool TutteLayout::doCall(
275 const List
<node
> &fixedNodes
,
276 List
<DPoint
> &fixedPositions
)
281 const Graph
&G
= AG
.constGraph();
283 GraphCopyAttributes
AGC(GC
, AG
);
285 // mark fixed nodes and set their positions in a
286 NodeArray
<bool> fixed(GC
,false);
287 forall_listiterators(node
, it
, fixedNodes
) {
289 DPoint p
= fixedPositions
.popFrontRet(); // slightly dirty...
290 fixedPositions
.pushBack(p
); // ...
296 if(fixedNodes
.size() == G
.numberOfNodes()) {
298 AG
.x(GC
.original(v
)) = AGC
.x(v
);
299 AG
.y(GC
.original(v
)) = AGC
.y(v
);
303 // all nodes have fixed positions - nothing left to do
305 // collect other nodes
306 List
<node
> otherNodes
;
307 forall_nodes(v
,GC
) if(!fixed
[v
]) otherNodes
.pushBack(v
);
309 NodeArray
<int> ind(GC
); // position of v in otherNodes and A
313 forall_listiterators(node
, it
, otherNodes
) ind
[*it
] = i
++;
315 int n
= otherNodes
.size(); // #other nodes
316 Array
<double> coord(n
); // coordinates (first x then y)
317 Array
<double> rhs(n
); // right hand side
318 double oneOverD
= 0.0;
320 CoinPackedMatrix
A(false,0,0); // equations
321 A
.setDimensions(n
,n
);
323 // initialize non-zero entries in matrix A
324 forall_listiterators(node
, it
, otherNodes
) {
325 oneOverD
= (double)(1.0/((*it
)->degree()));
326 forall_adj_edges(e
,*it
) {
327 // get second node of e
328 w
= (*it
== e
->source()) ? e
->target() : e
->source();
330 A
.modifyCoefficient(ind
[*it
],ind
[w
],oneOverD
);
333 A
.modifyCoefficient(ind
[*it
],ind
[*it
],-1);
336 // compute right hand side for x coordinates
337 forall_listiterators(node
, it
, otherNodes
) {
339 oneOverD
= (double)(1.0/((*it
)->degree()));
340 forall_adj_edges(e
,*it
) {
341 // get second node of e
342 w
= (*it
== e
->source()) ? e
->target() : e
->source();
343 if(fixed
[w
]) rhs
[ind
[*it
]] -= (oneOverD
*AGC
.x(w
));
347 // compute x coordinates
348 if(!(solveLP(n
, A
, rhs
, coord
))) return false;
349 forall_listiterators(node
, it
, otherNodes
) AGC
.x(*it
) = coord
[ind
[*it
]];
351 // compute right hand side for y coordinates
352 forall_listiterators(node
, it
, otherNodes
) {
354 oneOverD
= (double)(1.0/((*it
)->degree()));
355 forall_adj_edges(e
,*it
) {
356 // get second node of e
357 w
= (*it
== e
->source()) ? e
->target() : e
->source();
358 if(fixed
[w
]) rhs
[ind
[*it
]] -= (oneOverD
*AGC
.y(w
));
362 // compute y coordinates
363 if(!(solveLP(n
, A
, rhs
, coord
))) return false;
364 forall_listiterators(node
, it
, otherNodes
) AGC
.y(*it
) = coord
[ind
[*it
]];
366 // translate coordinates, such that the center lies in
367 // the center of the bounding box
368 DPoint
center(0.5 * m_bbox
.width(),0.5 * m_bbox
.height());
370 forall_nodes (v
, GC
) {
371 AGC
.x(v
) += center
.m_x
;
372 AGC
.y(v
) += center
.m_y
;
376 AG
.x(GC
.original(v
)) = AGC
.x(v
);
377 AG
.y(GC
.original(v
)) = AGC
.y(v
);
382 } // end namespace ogdf