6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class NonPlanarCore which represents the
11 * non-planar core reduction for biconnected graphs.
13 * \author Carsten Gutwenger
16 * This file is part of the Open Graph Drawing Framework (OGDF).
20 * See README.txt in the root directory of the OGDF installation for details.
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
50 #ifndef OGDF_NON_PLANAR_CORE_H
51 #define OGDF_NON_PLANAR_CORE_H
54 #include <ogdf/basic/Graph.h>
55 #include <ogdf/basic/NodeArray.h>
56 #include <ogdf/basic/EdgeArray.h>
61 class OGDF_EXPORT SPQRTree
;
62 class OGDF_EXPORT Skeleton
;
65 //---------------------------------------------------------
67 //---------------------------------------------------------
68 class OGDF_EXPORT NonPlanarCore
71 NonPlanarCore(const Graph
&G
);
73 const Graph
&core() const { return m_graph
; }
74 const Graph
&originalGraph() const { return *m_pOriginal
; }
76 node
original(node v
) const { return m_orig
[v
]; }
78 bool isVirtual(edge e
) const { return m_real
[e
] == 0; }
79 edge
realEdge(edge e
) const { return m_real
[e
]; }
81 const EdgeArray
<int> &cost() const { return m_cost
; }
82 int cost(edge e
) const { return m_cost
[e
]; }
83 const List
<edge
> &mincut(edge e
) const { return m_mincut
[e
]; }
86 void markCore(const SPQRTree
&T
, NodeArray
<bool> &mark
);
87 void traversingPath(Skeleton
&S
, edge eS
, List
<edge
> &path
, NodeArray
<node
> &mapV
);
90 const Graph
*m_pOriginal
;
92 NodeArray
<node
> m_orig
; // corresp. original node
93 EdgeArray
<edge
> m_real
; // corresp. original edge (0 if virtual)
94 EdgeArray
<List
<edge
> > m_mincut
; // traversing path for an edge in the core
95 EdgeArray
<int> m_cost
;
96 }; // class NonPlanarCore
99 } // end namespace ogdf