ext/OGDF/src/layered/CrossingsMatrix.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of crossings matrix.
  11  *
  12  * \author Andrea Wagner
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  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
  26  * for details.
  27  *
  28  * \par
  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.
  33  *
  34  * \par
  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.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #include <ogdf/layered/CrossingsMatrix.h>
  45
  46 namespace ogdf
  47 {
  48 //-------------------------------------------------------------------
  49 //                        CrossingMatrix
  50 //-------------------------------------------------------------------
  51
  52 CrossingsMatrix::CrossingsMatrix(const Hierarchy &H)
  53 {
  54         int max_len = 0;
  55         for (int i = 0; i < H.size(); i++)
  56         {
  57                 int len = H[i].size();
  58                 if (len > max_len)
  59                         max_len = len;
  60         }
  61
  62         map.init(max_len);
  63         matrix.init(0, max_len - 1, 0, max_len - 1);
  64         m_bigM = 10000;
  65 }
  66
  67
  68 void CrossingsMatrix::init(Level &L)
  69 {
  70         const Hierarchy &H = L.hierarchy();
  71
  72         for (int i = 0; i < L.size(); i++)
  73         {
  74                 map[i] = i;
  75                 for (int j = 0; j < L.size(); j++)
  76                         matrix(i,j) = 0;
  77         }
  78
  79         for (int i = 0; i < L.size(); i++)
  80         {
  81                 node v = L[i];
  82                 const Array<node> &L_adj_i = L.adjNodes(v);
  83
  84                 for(int k = 0; k < L_adj_i.size(); k++)
  85                 {
  86                         int pos_adj_k = H.pos(L_adj_i[k]);
  87                         for (int j = i + 1; j < L.size(); j++)
  88                         {
  89                                 const Array<node> &L_adj_j = L.adjNodes(L[j]);
  90
  91                                 for (int l = 0; l < L_adj_j.size(); l++)
  92                                 {
  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);
  96                                 }
  97                         }
  98                 }
  99         }
 100 }
 101
 102
 103 void CrossingsMatrix::init(Level &L, const EdgeArray<unsigned int> *edgeSubGraph)
 104 {
 105         OGDF_ASSERT(edgeSubGraph != 0);
 106         init(L);
 107
 108         const Hierarchy &H = L.hierarchy();
 109         const GraphCopy &HC(H);
 110
 111         // calculate max number of graphs in edgeSubGraph
 112         edge d;
 113         int max = 0;
 114         forall_edges(d, HC.original()) {
 115                 for (int i = 31; i > max; i--)
 116                 {
 117                         if((*edgeSubGraph)[d] & (1 << i))
 118                                 max = i;
 119                 }
 120         }
 121
 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++)
 125                 {
 126                         node v = L[i];
 127                         edge e;
 128                         // H.direction == 1 if direction == upward
 129                         if (H.direction()) {
 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++) {
 134                                                         node w = L[j];
 135                                                         edge f;
 136                                                         forall_adj_edges(f,w) {
 137                                                                 if ((f->source() == w) && ((*edgeSubGraph)[HC.original(f)] & (1 << k)))
 138                                                                 {
 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);
 142                                                                 }
 143                                                         }
 144                                                 }
 145                                         }
 146                                 }
 147                         }
 148                         else {
 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++) {
 153                                                         node w = L[j];
 154                                                         edge f;
 155                                                         forall_adj_edges(f,w) {
 156                                                                 if ((f->target() == w) && ((*edgeSubGraph)[HC.original(f)] & (1 << k)))
 157                                                                 {
 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);
 161                                                                 }
 162                                                         }
 163                                                 }
 164                                         }
 165                                 }
 166                         }
 167                 }
 168         }
 169 }
 170
 171
 172 } // end namespace ogdf