6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
10 * \brief Implementation of crossings matrix.
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/CrossingsMatrix.h>
48 //-------------------------------------------------------------------
50 //-------------------------------------------------------------------
52 CrossingsMatrix::CrossingsMatrix(const Hierarchy
&H
)
55 for (int i
= 0; i
< H
.size(); i
++)
57 int len
= H
[i
].size();
63 matrix
.init(0, max_len
- 1, 0, max_len
- 1);
68 void CrossingsMatrix::init(Level
&L
)
70 const Hierarchy
&H
= L
.hierarchy();
72 for (int i
= 0; i
< L
.size(); i
++)
75 for (int j
= 0; j
< L
.size(); j
++)
79 for (int i
= 0; i
< L
.size(); i
++)
82 const Array
<node
> &L_adj_i
= L
.adjNodes(v
);
84 for(int k
= 0; k
< L_adj_i
.size(); k
++)
86 int pos_adj_k
= H
.pos(L_adj_i
[k
]);
87 for (int j
= i
+ 1; j
< L
.size(); j
++)
89 const Array
<node
> &L_adj_j
= L
.adjNodes(L
[j
]);
91 for (int l
= 0; l
< L_adj_j
.size(); l
++)
93 int pos_adj_l
= H
.pos(L_adj_j
[l
]);
94 matrix(i
,j
) += (pos_adj_k
> pos_adj_l
);
95 matrix(j
,i
) += (pos_adj_l
> pos_adj_k
);
103 void CrossingsMatrix::init(Level
&L
, const EdgeArray
<unsigned int> *edgeSubGraph
)
105 OGDF_ASSERT(edgeSubGraph
!= 0);
108 const Hierarchy
&H
= L
.hierarchy();
109 const GraphCopy
&HC(H
);
111 // calculate max number of graphs in edgeSubGraph
114 forall_edges(d
, HC
.original()) {
115 for (int i
= 31; i
> max
; i
--)
117 if((*edgeSubGraph
)[d
] & (1 << i
))
122 // calculation differs from ordinary init since we need the edges and not only the nodes
123 for (int k
= 0; k
<= max
; k
++) {
124 for (int i
= 0; i
< L
.size(); i
++)
128 // H.direction == 1 if direction == upward
130 forall_adj_edges(e
,v
) {
131 if ((e
->source() == v
) && ((*edgeSubGraph
)[HC
.original(e
)] & (1 << k
))) {
132 int pos_adj_e
= H
.pos(e
->target());
133 for (int j
= i
+1; j
< L
.size(); j
++) {
136 forall_adj_edges(f
,w
) {
137 if ((f
->source() == w
) && ((*edgeSubGraph
)[HC
.original(f
)] & (1 << k
)))
139 int pos_adj_f
= H
.pos(f
->target());
140 matrix(i
,j
) += m_bigM
* (pos_adj_e
> pos_adj_f
);
141 matrix(j
,i
) += m_bigM
* (pos_adj_f
> pos_adj_e
);
149 forall_adj_edges(e
,v
) {
150 if ((e
->target() == v
) && ((*edgeSubGraph
)[HC
.original(e
)] & (1 << k
))) {
151 int pos_adj_e
= H
.pos(e
->source());
152 for (int j
= i
+1; j
< L
.size(); j
++) {
155 forall_adj_edges(f
,w
) {
156 if ((f
->target() == w
) && ((*edgeSubGraph
)[HC
.original(f
)] & (1 << k
)))
158 int pos_adj_f
= H
.pos(f
->source());
159 matrix(i
,j
) += m_bigM
* (pos_adj_e
> pos_adj_f
);
160 matrix(j
,i
) += m_bigM
* (pos_adj_f
> pos_adj_e
);
172 } // end namespace ogdf