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