6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Places Nodes at the Positio of the merge-partner
12 * \author Gereon Bartel
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 ***************************************************************/
43 #include <ogdf/energybased/multilevelmixer/MedianPlacer.h>
49 void MedianPlacer::placeOneLevel(MultilevelGraph
&MLG
)
51 int level
= MLG
.getLevel();
52 while (MLG
.getLevel() == level
&& MLG
.getLastMerge() != 0)
59 void MedianPlacer::placeOneNode(MultilevelGraph
&MLG
)
61 node merged
= MLG
.undoLastMerge();
63 std::vector
<double> xVector
;
64 std::vector
<double> yVector
;
66 forall_adj(adj
, merged
) {
68 xVector
.push_back(MLG
.x(adj
->twinNode()));
69 yVector
.push_back(MLG
.y(adj
->twinNode()));
71 std::nth_element(xVector
.begin(), xVector
.begin()+(i
/2), xVector
.end());
72 std::nth_element(yVector
.begin(), yVector
.begin()+(i
/2), yVector
.end());
73 double x
= xVector
[i
/2];
74 double y
= yVector
[i
/2];
76 std::nth_element(xVector
.begin(), xVector
.begin()+(i
/2)-1, xVector
.end());
77 std::nth_element(yVector
.begin(), yVector
.begin()+(i
/2)-1, yVector
.end());
78 x
+= xVector
[i
/2 - 1];
79 y
+= yVector
[i
/2 - 1];
83 MLG
.x(merged
, x
+ ((m_randomOffset
)?(float)randomDouble(-1.0, 1.0):0.f
));
84 MLG
.y(merged
, y
+ ((m_randomOffset
)?(float)randomDouble(-1.0, 1.0):0.f
));