6 * $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
7 ***************************************************************/
10 * \brief Declaration of class GalaxyMultilevelBuilder.
12 * \author Martin Gronemann
15 * This file is part of the Open Graph Drawing Framework (OGDF).
19 * See README.txt in the root directory of the OGDF installation for details.
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
47 #ifndef OGDF_GALAXY_MULTILEVEL_H
48 #define OGDF_GALAXY_MULTILEVEL_H
50 #include <ogdf/basic/GraphAttributes.h>
51 #include <ogdf/basic/tuples.h>
52 #include <ogdf/basic/simple_graph_alg.h>
53 #include "ArrayGraph.h"
54 #include "FastUtils.h"
59 class GalaxyMultilevel
62 typedef List
<Tuple2
< node
, int > > NearSunList
;
77 GalaxyMultilevel(Graph
* pGraph
)
79 m_pFinerMultiLevel
= 0;
80 m_pCoarserMultiLevel
= 0;
82 m_pNodeInfo
= new NodeArray
<LevelNodeInfo
>(*m_pGraph
);
83 m_pEdgeInfo
= new EdgeArray
<LevelEdgeInfo
>(*m_pGraph
);
85 forall_nodes(v
, *m_pGraph
)
87 (*m_pNodeInfo
)[v
].mass
= 1.0;
92 GalaxyMultilevel(GalaxyMultilevel
* prev
)
94 m_pCoarserMultiLevel
= 0;
95 m_pFinerMultiLevel
= prev
;
96 m_pFinerMultiLevel
->m_pCoarserMultiLevel
= this;
99 levelNumber
= prev
->levelNumber
+ 1;
102 ~GalaxyMultilevel() { }
104 GalaxyMultilevel
* m_pFinerMultiLevel
;
105 GalaxyMultilevel
* m_pCoarserMultiLevel
;
107 NodeArray
<LevelNodeInfo
>* m_pNodeInfo
;
108 EdgeArray
<LevelEdgeInfo
>* m_pEdgeInfo
;
113 class GalaxyMultilevelBuilder
116 struct LevelNodeState
121 float edgeLengthFromSun
;
129 GalaxyMultilevel
* build(GalaxyMultilevel
* pMultiLevel
);
132 void computeSystemMass();
133 void sortNodesBySystemMass();
134 void createResult(GalaxyMultilevel
* pMultiLevelResult
);
135 void labelSystem(node u
, node v
, int d
, float df
);
138 Graph
* m_pGraphResult
;
139 List
<node
> m_sunNodeList
;
140 List
<edge
> m_interSystemEdges
;
141 NodeArray
<GalaxyMultilevel::LevelNodeInfo
>* m_pNodeInfo
;
142 EdgeArray
<GalaxyMultilevel::LevelEdgeInfo
>* m_pEdgeInfo
;
143 NodeArray
<GalaxyMultilevel::LevelNodeInfo
>* m_pNodeInfoResult
;
144 EdgeArray
<GalaxyMultilevel::LevelEdgeInfo
>* m_pEdgeInfoResult
;
145 NodeArray
<LevelNodeState
> m_nodeState
;
146 NodeOrderInfo
* m_nodeMassOrder
;
147 RandomNodeSet
* m_pRandomSet
;
152 class NodeMassComparer
155 NodeMassComparer(const NodeArray
< GalaxyMultilevelBuilder::LevelNodeState
>& nodeState
) : m_nodeState(nodeState
) { }
157 // used for std::sort
158 inline bool operator()(const GalaxyMultilevelBuilder::NodeOrderInfo
& a
, const GalaxyMultilevelBuilder::NodeOrderInfo
& b
) const
160 return m_nodeState
[a
.theNode
].sysMass
< m_nodeState
[b
.theNode
].sysMass
;
164 const NodeArray
< GalaxyMultilevelBuilder::LevelNodeState
>& m_nodeState
;
167 } // end of namespace ogdf