1 /** \file
2  * \brief Preprocessor Layout simplifies Graphs for use in other Algorithms
3  *
4  * \author Gereon Bartel
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 <memory>
35 #include <ogdf/energybased/multilevel_mixer/MultilevelLayoutModule.h>
36 
37 namespace ogdf {
38 
39 /** \brief The PreprocessorLayout removes multi-edges and self-loops.
40  *
41  * @ingroup graph-drawing
42  *
43  * To draw a graph using the ModularMultilevelMixer or other layouts the
44  * graph must be simple, i.e., contain neither multi-edges nor self-loops.
45  * Edges that conflict with these rules are deleted in the PreprocessorLayout.
46  * A secondary layout is then called that can work on the graph in required form.
47  * After the layout has been computed, the edges are inserted back into the
48  * graph, as they may have been relevant for the user.
49  */
50 class OGDF_EXPORT PreprocessorLayout : public MultilevelLayoutModule
51 {
52 private:
53 	/** \brief Deleted Edges are stored in EdgeData
54 	 *
55 	 * EdgeData stores the deleted edges to allow restauration of the original
56 	 * graph after the layout has been computed.
57 	 */
58 	struct EdgeData
59 	{
EdgeDataEdgeData60 		EdgeData(int edgeInd, int sourceInd, int targetInd, double edgeWeight)
61 			:edgeIndex(edgeInd), sourceIndex(sourceInd), targetIndex(targetInd), weight(edgeWeight)
62 		{ }
63 
64 		int edgeIndex;
65 		int sourceIndex;
66 		int targetIndex;
67 		double weight;
68 	};
69 
70 	std::unique_ptr<LayoutModule> m_secondaryLayout;
71 	std::vector<EdgeData> m_deletedEdges;
72 	bool m_randomize;
73 
74 	void call(Graph &G, MultilevelGraph &MLG);
75 
76 public:
77 
78 	//! Constructor
79 	PreprocessorLayout();
80 
81 	//! Destructor
~PreprocessorLayout()82 	~PreprocessorLayout() { }
83 
84 
85 	using MultilevelLayoutModule::call;
86 
87 	//! Calculates a drawing for the Graph \p MLG.
88 	virtual void call(MultilevelGraph &MLG) override;
89 
90 	//! Calculates a drawing for the Graph \p GA.
91 	virtual void call(GraphAttributes &GA) override;
92 
93 	//! Sets the secondary layout.
setLayoutModule(LayoutModule * layout)94 	void setLayoutModule(LayoutModule *layout) {
95 		m_secondaryLayout.reset(layout);
96 	}
97 
98 	//! Defines whether the positions of the node are randomized before the secondary layout call.
setRandomizePositions(bool on)99 	void setRandomizePositions(bool on) {
100 		m_randomize = on;
101 	}
102 };
103 
104 }
105