6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of a constraint class for the Branch&Cut algorithm
11 * for the Maximum C-Planar SubGraph problem.
13 * These constraint do not necessarily belong to the ILP formulation, but
14 * have the purpose to strengthen the LP-relaxations in the case of very dense
15 * Graphs, by restricting the maximum number of edges that can occur in any optimal
16 * solution according to Euler's formula for planar Graphs: |E| <= 3|V|-6
18 * \author Mathias Jansen
22 * This file is part of the Open Graph Drawing Framework (OGDF).
26 * See README.txt in the root directory of the OGDF installation for details.
29 * This program is free software; you can redistribute it and/or
30 * modify it under the terms of the GNU General Public License
31 * Version 2 or 3 as published by the Free Software Foundation;
32 * see the file LICENSE.txt included in the packaging of this file
36 * This program is distributed in the hope that it will be useful,
37 * but WITHOUT ANY WARRANTY; without even the implied warranty of
38 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
39 * GNU General Public License for more details.
42 * You should have received a copy of the GNU General Public
43 * License along with this program; if not, write to the Free
44 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
45 * Boston, MA 02110-1301, USA.
47 * \see http://www.gnu.org/copyleft/gpl.html
48 ***************************************************************/
50 #ifndef OGDF_CLUSTER_MAX_PLANAR_EDGES_H
51 #define OGDF_CLUSTER_MAX_PLANAR_EDGES_H
53 #include <ogdf/internal/cluster/Cluster_EdgeVar.h>
54 #include <ogdf/internal/cluster/basics.h>
56 #include <abacus/constraint.h>
61 class MaxPlanarEdgesConstraint
: public ABA_CONSTRAINT
{
64 friend class CPlanarSub
;
68 MaxPlanarEdgesConstraint(ABA_MASTER
*master
, int edgeBound
, List
<nodePair
> &edges
);
69 MaxPlanarEdgesConstraint(ABA_MASTER
*master
, int edgeBound
);
72 virtual ~MaxPlanarEdgesConstraint();
74 //computes and returns the coefficient for the given variable
75 virtual double coeff(ABA_VARIABLE
*v
);
78 List
<nodePair
> m_edges
;