1 /** \file
2 * \brief Implementation in-/out-points management.
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
33 #include <ogdf/planarlayout/mixed_model_layout/IOPoints.h>
34
35
36 namespace ogdf {
37
38
searchRealForward(ListConstIterator<InOutPoint> it) const39 ListConstIterator<InOutPoint> IOPoints::searchRealForward(
40 ListConstIterator<InOutPoint> it) const
41 {
42 while (it.valid() && marked((*it).m_adj))
43 ++it;
44
45 return it;
46 }
47
searchRealBackward(ListConstIterator<InOutPoint> it) const48 ListConstIterator<InOutPoint> IOPoints::searchRealBackward(
49 ListConstIterator<InOutPoint> it) const
50 {
51 while (it.valid() && marked((*it).m_adj))
52 --it;
53
54 return it;
55 }
56
57
restoreDeg1Nodes(PlanRep & PG,ArrayBuffer<PlanRep::Deg1RestoreInfo> & S)58 void IOPoints::restoreDeg1Nodes(PlanRep &PG, ArrayBuffer<PlanRep::Deg1RestoreInfo> &S)
59 {
60 List<node> deg1s;
61
62 PG.restoreDeg1Nodes(S,deg1s);
63
64 for(node v : deg1s) {
65 adjEntry adj = v->firstAdj();
66 m_mark[adj] = m_mark[adj->twin()] = true;
67 }
68 }
69
70
switchBeginIn(node v)71 adjEntry IOPoints::switchBeginIn(node v)
72 {
73 List<InOutPoint> &Lin = m_in [v];
74 List<InOutPoint> &Lout = m_out[v];
75
76 ListConstIterator<InOutPoint> it;
77 adjEntry adj;
78
79 while ((it = Lin.begin()).valid() && marked(adj = (*it).m_adj))
80 m_pointOf[adj] = &(*Lout.pushFront(Lin.popFrontRet()));
81
82 return it.valid() ? adj : nullptr;
83 }
84
85
switchEndIn(node v)86 adjEntry IOPoints::switchEndIn(node v)
87 {
88 List<InOutPoint> &Lin = m_in [v];
89 List<InOutPoint> &Lout = m_out[v];
90
91 ListConstReverseIterator<InOutPoint> it;
92 adjEntry adj;
93
94 while ((it = Lin.rbegin()).valid() && marked(adj = (*it).m_adj))
95 m_pointOf[adj] = &(*Lout.pushBack(Lin.popBackRet()));
96
97 return it.valid() ? adj : nullptr;
98 }
99
100
switchBeginOut(node v)101 void IOPoints::switchBeginOut(node v)
102 {
103 List<InOutPoint> &Lin = m_in [v];
104 List<InOutPoint> &Lout = m_out[v];
105
106 adjEntry adj = (*Lout.begin()).m_adj;
107 m_pointOf[adj] = &(*Lin.pushFront(Lout.popFrontRet()));
108 }
109
110
switchEndOut(node v)111 void IOPoints::switchEndOut(node v)
112 {
113 List<InOutPoint> &Lin = m_in [v];
114 List<InOutPoint> &Lout = m_out[v];
115
116 adjEntry adj = (*Lout.rbegin()).m_adj;
117 m_pointOf[adj] = &(*Lin.pushBack(Lout.popBackRet()));
118 }
119
120
numDeg1(node v,int & xl,int & xr,bool doubleCount) const121 void IOPoints::numDeg1(node v, int &xl, int &xr,
122 bool doubleCount) const
123 {
124 const List<InOutPoint> &L = m_out[v];
125 ListConstIterator<InOutPoint> it;
126
127 xl = xr = 0;
128 for (it = L.begin(); it.valid() && marked((*it).m_adj); ++it)
129 ++xl;
130
131 if (doubleCount || it.valid()) // avoid double counting if all are marked
132 for (ListConstReverseIterator<InOutPoint> revIt = L.rbegin(); revIt.valid() && marked((*revIt).m_adj); ++revIt)
133 ++xr;
134 }
135
middleNeighbor(node z1) const136 InOutPoint IOPoints::middleNeighbor(node z1) const
137 {
138 const List<InOutPoint> &L = m_in[z1];
139
140 ListConstIterator<InOutPoint> it, itFound;
141 int i, pos = (L.size()-1)/2;
142
143 for (it = L.begin().succ(), i = 1; i <= pos || !itFound.valid(); ++it, ++i)
144 if (!marked((*it).m_adj))
145 itFound = it;
146
147 return *itFound;
148 }
149
150 }
151