ext/OGDF/ogdf/layered/OptimalRanking.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of optimal ranking algorithm for Sugiyama
  11  *        algorithm.
  12  *
  13  * \author Carsten Gutwenger
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  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
  27  * for details.
  28  *
  29  * \par
  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.
  34  *
  35  * \par
  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.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49 #ifndef OGDF_OPTIMAL_RANKING_H
  50 #define OGDF_OPTIMAL_RANKING_H
  51
  52
  53
  54 #include <ogdf/module/RankingModule.h>
  55 #include <ogdf/module/AcyclicSubgraphModule.h>
  56 #include <ogdf/basic/ModuleOption.h>
  57 #include <ogdf/basic/NodeArray.h>
  58
  59
  60 namespace ogdf {
  61
  62 //! The optimal ranking algorithm.
  63 /**
  64  * The class OptimalRanking implements the LP-based algorithm for computing
  65  * a node ranking with minimal edge lengths, which can be used as first phase
  66  * in SugiyamaLayout.
  67  *
  68  * <H3>Optional parameters</H3>
  69  * The following options affect the crossing minimization step
  70  * of the algorithm:
  71  *
  72  * <table>
  73  *   <tr>
  74  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  75  *   </tr><tr>
  76  *     <td><i>separateMultiEdges</i><td>bool<td>true
  77  *     <td>If set to true, multi-edges will span at least two layers.
  78  *   </tr>
  79  * </table>
  80  *
  81  * <H3>%Module options</H3>
  82  *
  83  * <table>
  84  *   <tr>
  85  *     <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i>
  86  *   </tr><tr>
  87  *     <td><i>subgraph</i><td>AcyclicSubgraphModule<td>DfsAcyclicSubgraph
  88  *     <td>The module for the computation of the acyclic subgraph.
  89  *   </tr>
  90  * </table>
  91  */
  92 class OGDF_EXPORT OptimalRanking : public RankingModule {
  93
  94         ModuleOption<AcyclicSubgraphModule> m_subgraph; // option for acyclic sugraph
  95         bool m_separateMultiEdges;
  96
  97 public:
  98         //! Creates an instance of optimal ranking.
  99         OptimalRanking();
 100
 101
 102         /**
 103          *  @name Algorithm call
 104          *  @{
 105          */
 106
 107         //! Computes a node ranking of \a G in \a rank.
 108         void call(const Graph &G, NodeArray<int> &rank);
 109
 110         //! Computes a node ranking of \a G with given minimal edge length in \a rank.
 111         /**
 112          * @param G is the input graph.
 113          * @param length specifies the minimal length of each edge.
 114          * @param rank is assigned the rank (layer) of each node.
 115          */
 116         void call(const Graph &G, const EdgeArray<int> &length, NodeArray<int> &rank);
 117
 118         //! Computes a cost-minimal node ranking of \a G for given edge costs and minimal edge lengths in \a rank.
 119         /**
 120          * @param G is the input graph.
 121          * @param length specifies the minimal length of each edge.
 122          * @param cost specifies the cost of each edge.
 123          * @param rank is assigned the rank (layer) of each node.
 124          */
 125         void call(
 126                 const Graph &G,
 127                 const EdgeArray<int> &length,
 128                 const EdgeArray<int> &cost,
 129                 NodeArray<int> &rank);
 130
 131
 132         /** @}
 133          *  @name Optional parameters
 134          *  @{
 135          */
 136
 137         //! Returns the current setting of option separateMultiEdges.
 138         /**
 139          * If set to true, multi-edges will span at least two layers. Since
 140          * each such edge will have at least one dummy node, the edges will
 141          * automaticall be separated in a Sugiyama drawing.
 142          */
 143         bool separateMultiEdges() const { return m_separateMultiEdges; }
 144
 145         //! Sets the option separateMultiEdges to \a b.
 146         void separateMultiEdges(bool b) { m_separateMultiEdges = b; }
 147
 148
 149         /** @}
 150          *  @name Module options
 151          *  @{
 152          */
 153
 154         //! Sets the module for the computation of the acyclic subgraph.
 155         void setSubgraph(AcyclicSubgraphModule *pSubgraph) {
 156                 m_subgraph.set(pSubgraph);
 157         }
 158
 159         //! @}
 160
 161 private:
 162         //! Implements the algorithm call.
 163         void doCall(const Graph& G,
 164                 NodeArray<int> &rank,
 165                 EdgeArray<bool> &reversed,
 166                 const EdgeArray<int> &length,
 167                 const EdgeArray<int> &cost);
 168 };
 169
 170
 171 } // end namespace ogdf
 172
 173
 174 #endif