1 /** \file 2 * \brief Declares the class LeftistOrdering... 3 * 4 * ... that computes a leftist canonical ordering as described by Badent et al. in More Canonical Ordering 5 * 6 * \author Martin Gronemann 7 * 8 * \par License: 9 * This file is part of the Open Graph Drawing Framework (OGDF). 10 * 11 * \par 12 * Copyright (C)<br> 13 * See README.md in the OGDF root directory for details. 14 * 15 * \par 16 * This program is free software; you can redistribute it and/or 17 * modify it under the terms of the GNU General Public License 18 * Version 2 or 3 as published by the Free Software Foundation; 19 * see the file LICENSE.txt included in the packaging of this file 20 * for details. 21 * 22 * \par 23 * This program is distributed in the hope that it will be useful, 24 * but WITHOUT ANY WARRANTY; without even the implied warranty of 25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 26 * GNU General Public License for more details. 27 * 28 * \par 29 * You should have received a copy of the GNU General Public 30 * License along with this program; if not, see 31 * http://www.gnu.org/copyleft/gpl.html 32 */ 33 34 #pragma once 35 36 #include <ogdf/planarlayout/ShellingOrderModule.h> 37 #include <ogdf/basic/AdjEntryArray.h> 38 39 namespace ogdf { 40 41 // context class for the leftist canonical ordering algorithm 42 class LeftistOrdering 43 { 44 protected: 45 46 // struct for a candidate aka belt item 47 struct Candidate 48 { CandidateCandidate49 Candidate() : stopper(nullptr) {}; 50 51 // the edges in the belt item 52 List<adjEntry> chain; 53 54 // a possible stopper of the candidate 55 node stopper; 56 }; 57 58 public: 59 // computes the leftist canonical order. Requires that G is simple, triconnected and embedded. 60 // adj_v1n is the adjEntry at v_1 looking towards v_n, the outerface is choosen such that v_2 is the cyclic pred 61 // of v_n. the result is saved in result, a list of list of nodes, first set is v_1, v_2, last one is v_n. 62 bool call(const Graph& G, adjEntry adj_v1n, List<List<node> >& result); 63 64 private: 65 // the leftmost feasible candidate function from the paper 66 bool leftmostFeasibleCandidate(List<node>& result); 67 68 // this is used to check a candidate for a singleton copy 69 bool isSingletonWith(const Candidate& c,node v) const; 70 71 // update belt function from the paper 72 void updateBelt(); 73 74 // belt extension function from the paper 75 void beltExtension(List<Candidate>& extension); 76 77 // returns true if v is forbidde forbidden(node v)78 bool forbidden(node v) const 79 { 80 // too many cut faces? 81 return m_cutFaces[v] > m_cutEdges[v] + 1; 82 } 83 84 // returns true if v is singular singular(node v)85 bool singular(node v) const 86 { 87 // not more cutfaces then cut edges plus one ? 88 return m_cutFaces[v] > 2 && m_cutFaces[v] == m_cutEdges[v] + 1; 89 } 90 91 // the belt 92 List<Candidate> m_belt; 93 94 // the curr candidate in the belt 95 List<Candidate>::iterator m_currCandidateIt; 96 97 // number of cutfaces incident to a vertex 98 NodeArray<int> m_cutFaces; 99 100 // number of cutedges incident to a vertex 101 NodeArray<int> m_cutEdges; 102 103 // flag for marking directed edges 104 AdjEntryArray<bool> m_marked; 105 106 public: 107 // this is a custom class to have a more convienent way to access a canonical ordering 108 // used somewhere 109 class Partitioning 110 { 111 public: Partitioning()112 Partitioning() { } Partitioning(const Graph & G,const List<List<node>> & lco)113 Partitioning(const Graph& G, const List<List<node> >& lco) { buildFromResult(G, lco); } 114 115 void buildFromResult(const Graph& G, const List<List<node> >& lco); 116 117 // returns the adjEntry to the left node in G_k-1 left(int k)118 adjEntry left(int k) const 119 { 120 if (m_ears[k][0]) 121 return m_ears[k][0]->twin(); 122 else 123 return nullptr; 124 } 125 126 // returns the adjEntry to the left node in G_k-1 right(int k)127 adjEntry right(int k) const 128 { 129 return m_ears[k][m_ears[k].size()-1]; 130 } 131 132 // returns the edge from v_i to v_i+1 in the k-th partition getChainAdj(int k,int i)133 adjEntry getChainAdj(int k, int i) const 134 { 135 return m_ears[k][i+1]; 136 } 137 getPathAdj(int k,int i)138 adjEntry getPathAdj(int k, int i) const 139 { 140 return m_ears[k][i]; 141 } 142 getNode(int k,int i)143 node getNode(int k, int i) const 144 { 145 return m_ears[k][i+1]->theNode(); 146 } 147 148 // returns the number of all partitions numPartitions()149 int numPartitions() const 150 { 151 return m_ears.size(); 152 } 153 154 // returns the number of nodes in partition k numNodes(int k)155 int numNodes(int k) const 156 { 157 return m_ears[k].size() - 1; 158 } 159 pathLength(int k)160 int pathLength(int k) const 161 { 162 return m_ears[k].size(); 163 } 164 isSingleton(int k)165 bool isSingleton(int k) const 166 { 167 return numNodes(k)==1; 168 } 169 170 private: 171 // keeps for every partition the path from left, v_1, ... v_k, right 172 Array< Array<adjEntry> > m_ears; 173 }; 174 call(const Graph & G,adjEntry adj_v1n,Partitioning & partition)175 bool call(const Graph& G, adjEntry adj_v1n, Partitioning& partition) 176 { 177 // the simple result 178 List<List<node> > result; 179 // compute it 180 if (!call(G, adj_v1n, result)) 181 return false; 182 183 // generate the comfortable partitioning 184 partition.buildFromResult(G, result); 185 186 // success hopefully.. 187 return true; 188 } 189 }; 190 191 } 192