1/** \file
2 * \brief Declaration of coffman graham ranking algorithm for Sugiyama
3 * algorithm.
4 *
5 * \author Till Schäfer
6 *
7 * \par License:
8 * This file is part of the Open Graph Drawing Framework (OGDF).
9 *
10 * \par
11 * Copyright (C)<br>
12 * See README.md in the OGDF root directory for details.
13 *
14 * \par
15 * This program is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU General Public License
17 * Version 2 or 3 as published by the Free Software Foundation;
18 * see the file LICENSE.txt included in the packaging of this file
19 * for details.
20 *
21 * \par
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
26 *
27 * \par
28 * You should have received a copy of the GNU General Public
29 * License along with this program; if not, see
30 * http://www.gnu.org/copyleft/gpl.html
31 */
32
33#pragma once
34
35#include <ogdf/module/RankingModule.h>
36#include <ogdf/module/AcyclicSubgraphModule.h>
37#include <ogdf/basic/NodeArray.h>
38#include <memory>
39#include <ogdf/basic/tuples.h>
40
41namespace ogdf {
42
43//! The coffman graham ranking algorithm.
44/**
45 * @ingroup gd-ranking
46 *
47 * The class CoffmanGrahamRanking implements a node ranking algorithmn based on
48 * the coffman graham scheduling algorithm, which can be used as first phase
49 * in SugiyamaLayout. The aim of the algorithm is to ensure that the height of
50 * the ranking (the number of layers) is kept small.
51 */
52class OGDF_EXPORT CoffmanGrahamRanking : public RankingModule {
53
54public:
55 //! Creates an instance of coffman graham ranking.
56 CoffmanGrahamRanking();
57
58
59 /**
60 * @name Algorithm call
61 * @{
62 */
63
64 //! Computes a node ranking of \p G in \p rank.
65 virtual void call(const Graph &G, NodeArray<int> &rank) override;
66
67
68 /** @}
69 * @name Module options
70 * @{
71 */
72
73 //! Sets the module for the computation of the acyclic subgraph.
74 void setSubgraph(AcyclicSubgraphModule *pSubgraph) {
75 m_subgraph.reset(pSubgraph);
76 }
77
78 //! @}
79
80 //! Get for the with
81 int width() const {
82 return m_w;
83 }
84
85 //! Set for the with
86 void width (int w) {
87 m_w = w;
88 }
89
90
91private:
92 // CoffmanGraham data structures
93 class _int_set {
94 int* m_array;
95 int m_length;
96 int m_index;
97 public:
98 _int_set() : m_array(nullptr), m_length(0), m_index(0) { }
99 explicit _int_set(int len) : m_array(nullptr), m_length(len), m_index(len) {
100 if (len > 0)
101 m_array = new int[m_length];
102 }
103 ~_int_set() { delete[] m_array; }
104
105 void init(int len) {
106 delete m_array;
107 if ((m_length = len) == 0)
108 m_array = nullptr;
109 else
110 m_array = new int[m_length];
111 m_index = len;
112 }
113
114 int length() const {
115 return m_length;
116 }
117
118 int operator[](int i) const {
119 return m_array[i];
120 }
121
122 void insert(int x) {
123 m_array[--m_index] = x;
124 }
125
126 bool ready() const {
127 return m_index == 0;
128 }
129 };
130
131 // CoffmanGraham members
132 std::unique_ptr<AcyclicSubgraphModule> m_subgraph;
133 int m_w;
134 NodeArray<_int_set> m_s;
135
136 // dfs members
137 NodeArray<int> m_mark;
138
139 // CoffmanGraham funktions
140 void insert (node u, List<Tuple2<node,int> > &ready_nodes);
141 void insert (node u, List<node> &ready, const NodeArray<int> &pi);
142
143 // dfs funktions
144 void removeTransitiveEdges (Graph& G);
145 void dfs(node v);
146};
147
148}
149