3 * This file is part of LyX, the document processor.
4 * Licence details can be found in the file COPYING.
6 * \author Dekel Tsur (original code)
7 * \author Richard Heck (re-implementation)
9 * Full author contact details are available in file CREDITS.
17 #include "support/debug.h"
18 #include "support/lassert.h"
27 bool Graph::bfs_init(int s
, bool clear_visited
)
35 vector
<Vertex
>::iterator it
= vertices_
.begin();
36 vector
<Vertex
>::iterator en
= vertices_
.end();
37 for (; it
!= en
; ++it
)
40 if (!vertices_
[s
].visited
) {
42 vertices_
[s
].visited
= true;
48 void Graph::clearMarks()
50 Arrows::iterator it
= arrows_
.begin();
51 Arrows::iterator
const en
= arrows_
.end();
52 for (; it
!= en
; ++it
)
58 Graph::getReachableTo(int target
, bool clear_visited
)
61 if (!bfs_init(target
, clear_visited
))
64 // Here's the logic, which is shared by the other routines.
65 // Q_ holds a list of nodes we have been able to reach (in this
66 // case, reach backwards). It is initialized to the current node
67 // by bfs_init, and then we recurse, adding the nodes we can reach
68 // from the current node as we go. That makes it a breadth-first
71 int const current
= Q_
.front();
73 if (current
!= target
|| formats
.get(target
).name() != "lyx")
74 result
.push_back(current
);
76 vector
<Arrow
*>::iterator it
= vertices_
[current
].in_arrows
.begin();
77 vector
<Arrow
*>::iterator
const end
= vertices_
[current
].in_arrows
.end();
78 for (; it
!= end
; ++it
) {
79 const int cv
= (*it
)->from
;
80 if (!vertices_
[cv
].visited
) {
81 vertices_
[cv
].visited
= true;
92 Graph::getReachable(int from
, bool only_viewable
,
96 if (!bfs_init(from
, clear_visited
))
100 int const current
= Q_
.front();
102 Format
const & format
= formats
.get(current
);
103 if (!only_viewable
|| !format
.viewer().empty())
104 result
.push_back(current
);
105 else if (format
.isChildFormat()) {
106 Format
const * const parent
=
107 formats
.getFormat(format
.parentFormat());
108 if (parent
&& !parent
->viewer().empty())
109 result
.push_back(current
);
112 vector
<Arrow
*>::const_iterator cit
=
113 vertices_
[current
].out_arrows
.begin();
114 vector
<Arrow
*>::const_iterator end
=
115 vertices_
[current
].out_arrows
.end();
116 for (; cit
!= end
; ++cit
) {
117 int const cv
= (*cit
)->to
;
118 if (!vertices_
[cv
].visited
) {
119 vertices_
[cv
].visited
= true;
129 bool Graph::isReachable(int from
, int to
)
134 if (to
< 0 || !bfs_init(from
))
137 while (!Q_
.empty()) {
138 int const current
= Q_
.front();
143 vector
<Arrow
*>::const_iterator cit
=
144 vertices_
[current
].out_arrows
.begin();
145 vector
<Arrow
*>::const_iterator end
=
146 vertices_
[current
].out_arrows
.end();
147 for (; cit
!= end
; ++cit
) {
148 int const cv
= (*cit
)->to
;
149 if (!vertices_
[cv
].visited
) {
150 vertices_
[cv
].visited
= true;
160 Graph::EdgePath
const Graph::getPath(int from
, int to
)
166 if (to
< 0 || !bfs_init(from
))
169 // In effect, the way this works is that we construct a sub-graph
170 // by starting at "from" and following the arrows outward. Instead
171 // of actually constructing a sub-graph, though, we "mark" the
172 // arrows we traverse as we go. Once we hit "to", we abort the
173 // marking process and then call getMarkedPath() to reconstruct
177 while (!Q_
.empty()) {
178 int const current
= Q_
.front();
181 vector
<Arrow
*>::const_iterator
const beg
=
182 vertices_
[current
].out_arrows
.begin();
183 vector
<Arrow
*>::const_iterator cit
= beg
;
184 vector
<Arrow
*>::const_iterator end
=
185 vertices_
[current
].out_arrows
.end();
186 for (; cit
!= end
; ++cit
) {
187 int const cv
= (*cit
)->to
;
188 if (!vertices_
[cv
].visited
) {
189 vertices_
[cv
].visited
= true;
191 (*cit
)->marked
= true;
202 getMarkedPath(from
, to
, path
);
207 // We assume we have marked the graph, as in getPath(). We also
208 // assume that we have done so in such a way as to guarantee a
209 // marked path from "from" to "to".
210 // We then start at "to" and find the arrow leading to it that
211 // has been marked. We add that to the path we are constructing,
212 // step back on that arrow, and continue the process (i.e., recurse).
213 void Graph::getMarkedPath(int from
, int to
, EdgePath
& path
) {
215 reverse(path
.begin(), path
.end());
218 // find marked in_arrow
219 vector
<Arrow
*>::const_iterator it
= vertices_
[to
].in_arrows
.begin();
220 vector
<Arrow
*>::const_iterator en
= vertices_
[to
].in_arrows
.end();
221 for (; it
!= en
; ++it
)
225 LASSERT(false, /* */);
228 int const newnode
= (*it
)->from
;
229 path
.push_back(newnode
);
230 getMarkedPath(from
, newnode
, path
);
234 void Graph::init(int size
)
236 vertices_
= vector
<Vertex
>(size
);
242 void Graph::addEdge(int from
, int to
)
244 arrows_
.push_back(Arrow(from
, to
, numedges_
));
246 Arrow
* ar
= &(arrows_
.back());
247 vertices_
[to
].in_arrows
.push_back(ar
);
248 vertices_
[from
].out_arrows
.push_back(ar
);