ext/OGDF/src/cluster/Cluster_ChunkConnection.cpp

   1 /*
   2  * $Revision: 2549 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-04 23:09:19 +0200 (Mi, 04. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief implementation of initial cut-constraint class for the Branch&Cut algorithm
  11  * for the Maximum C-Planar SubGraph problem.
  12  *
  13  * A feasible ILP solution has to imply a completely connected, planar Sub-Clustergraph.
  14  * For each cluster that is not connected, additional connection edges have to be inserted
  15  * between the chunks of the cluster, to obtain c-connectivity.
  16  * Thus, initial constraints are added that guarantee this behaviour, if the number of chunks
  17  * is at most 3. If some cluster consists of more than 3 chunks, additional constraints
  18  * have to be separated during the algorithm.
  19  *
  20  * \author Mathias Jansen
  21  *
  22  *
  23  * \par License:
  24  * This file is part of the Open Graph Drawing Framework (OGDF).
  25  *
  26  * \par
  27  * Copyright (C)<br>
  28  * See README.txt in the root directory of the OGDF installation for details.
  29  *
  30  * \par
  31  * This program is free software; you can redistribute it and/or
  32  * modify it under the terms of the GNU General Public License
  33  * Version 2 or 3 as published by the Free Software Foundation;
  34  * see the file LICENSE.txt included in the packaging of this file
  35  * for details.
  36  *
  37  * \par
  38  * This program is distributed in the hope that it will be useful,
  39  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  40  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  41  * GNU General Public License for more details.
  42  *
  43  * \par
  44  * You should have received a copy of the GNU General Public
  45  * License along with this program; if not, write to the Free
  46  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  47  * Boston, MA 02110-1301, USA.
  48  *
  49  * \see  http://www.gnu.org/copyleft/gpl.html
  50  ***************************************************************/
  51
  52 #ifdef USE_ABACUS
  53
  54 #include <ogdf/internal/cluster/Cluster_ChunkConnection.h>
  55
  56 using namespace ogdf;
  57
  58 ChunkConnection::ChunkConnection(ABA_MASTER *master, const ArrayBuffer<node>& chunk, const ArrayBuffer<node>& cochunk) :
  59         BaseConstraint(master, 0, ABA_CSENSE::Greater, 1.0, false, false, true)
  60 {
  61         chunk.compactMemcpy(m_chunk);
  62         cochunk.compactMemcpy(m_cochunk);
  63 }
  64
  65
  66 ChunkConnection::~ChunkConnection() {}
  67
  68
  69 int ChunkConnection::coeff(node n1, node n2) {
  70         //TODO: speedup
  71         int i,j;
  72         forall_arrayindices(i,m_chunk) {
  73                 if(m_chunk[i] == n1) {
  74                         forall_arrayindices(j,m_cochunk) {
  75                                 if(m_cochunk[j] == n2) {
  76                                         return 1;
  77                                 }
  78                         }
  79                         return 0;
  80                 } else if(m_chunk[i] == n2) {
  81                         forall_arrayindices(j,m_cochunk) {
  82                                 if(m_cochunk[j] == n1) {
  83                                         return 1;
  84                                 }
  85                         }
  86                         return 0;
  87                 }
  88         }
  89         return 0;
  90 }
  91
  92 #endif // USE_ABACUS