1 /** \file
2  * \brief Declaration of Hierarchy class.
3  *
4  * \author Carsten Gutwenger
5  *
6  * \par License:
7  * This file is part of the Open Graph Drawing Framework (OGDF).
8  *
9  * \par
10  * Copyright (C)<br>
11  * See README.md in the OGDF root directory for details.
12  *
13  * \par
14  * This program is free software; you can redistribute it and/or
15  * modify it under the terms of the GNU General Public License
16  * Version 2 or 3 as published by the Free Software Foundation;
17  * see the file LICENSE.txt included in the packaging of this file
18  * for details.
19  *
20  * \par
21  * This program is distributed in the hope that it will be useful,
22  * but WITHOUT ANY WARRANTY; without even the implied warranty of
23  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
24  * GNU General Public License for more details.
25  *
26  * \par
27  * You should have received a copy of the GNU General Public
28  * License along with this program; if not, see
29  * http://www.gnu.org/copyleft/gpl.html
30  */
31 
32 #pragma once
33 
34 #include <ogdf/basic/EdgeArray.h>
35 #include <ogdf/basic/GraphCopy.h>
36 
37 
38 namespace ogdf {
39 
40 //! Representation of proper hierarchies used by Sugiyama-layout.
41 /**
42  * \see Level, SugiyamaLayout
43  */
44 class OGDF_EXPORT Hierarchy {
45 
46 	friend class LayerBasedUPRLayout;
47 
48 	GraphCopy m_GC; //!< The graph copy representing the topology of the proper hierarchy.
49 	NodeArray<int> m_rank; //!< The rank (level) of a node.
50 	Array<int> m_size;
51 
52 public:
53 	//! Creates an empty hierarchy.
Hierarchy()54 	Hierarchy() { }
55 	//! Creates an hierarchy of graph \p G with node ranks \p rank.
56 	Hierarchy(const Graph &G, const NodeArray<int> &rank);
57 
58 	// destruction
~Hierarchy()59 	~Hierarchy() { }
60 
61 	void createEmpty(const Graph &G);
62 	void initByNodes(const List<node> &nodes,
63 		EdgeArray<edge> &eCopy,
64 		const NodeArray<int> &rank);
65 
66 	//! Conversion to const GraphCopy reference.
67 	operator const GraphCopy &() const { return m_GC; }
68 
69 	//! Returns the rank (level) of node \p v.
rank(node v)70 	int rank(node v) const { return m_rank[v]; }
71 
maxRank()72 	int maxRank() const { return m_size.high(); }
73 
size(int i)74 	int size(int i) const { return m_size[i]; }
75 
isLongEdgeDummy(node v)76 	bool isLongEdgeDummy(node v) const {
77 		return m_GC.isDummy(v) && v->outdeg() == 1;
78 	}
79 
80 private:
81 	void doInit(const NodeArray<int> &rank);
82 };
83 
84 }
85