6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of split heuristic.
12 * \author 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 ***************************************************************/
44 #include <ogdf/layered/SplitHeuristic.h>
45 #include <ogdf/layered/CrossingsMatrix.h>
49 //-------------------------------------------------------------------
51 //-------------------------------------------------------------------
53 void SplitHeuristic::init (const Hierarchy
&H
)
55 m_cm
= new CrossingsMatrix(H
);
58 void SplitHeuristic::cleanup()
64 void SplitHeuristic::call(Level
&L
)
67 buffer
= Array
<node
>(L
.size());
69 recCall(L
, 0, L
.size() - 1);
71 buffer
= Array
<node
>(-1);
75 void SplitHeuristic::call(Level
&L
, const EdgeArray
<unsigned int> *edgeSubGraph
)
77 // only difference to call is the different calculation of the crossingsmatrix
78 m_cm
->init(L
, edgeSubGraph
);
79 buffer
= Array
<node
>(L
.size());
81 recCall(L
, 0, L
.size() - 1);
83 buffer
= Array
<node
>(-1);
86 void SplitHeuristic::recCall(Level
&L
, int low
, int high
)
88 if (high
<= low
) return;
90 const Hierarchy
&H
= L
.hierarchy();
91 CrossingsMatrix
&crossings
= *m_cm
;
92 int up
= high
, down
= low
;
94 // chooses L[low] as pivot
96 for (i
= low
+1; i
<= high
; i
++)
98 if (crossings(i
,low
) < crossings(low
,i
))
99 buffer
[down
++] = L
[i
];
102 // use two for-loops in order to keep the number of swaps low
103 for (i
= high
; i
>= low
+1; i
--)
105 if (crossings(i
,low
) >= crossings(low
,i
))
109 buffer
[down
] = L
[low
];
111 for (i
= low
; i
< high
; i
++)
113 int j
= H
.pos(buffer
[i
]);
121 recCall(L
,low
,down
-1);
122 recCall(L
,up
+1,high
);
125 } // end namespace ogdf