src/Graph.cpp

   1 /**
   2  * \file Graph.cpp
   3  * This file is part of LyX, the document processor.
   4  * Licence details can be found in the file COPYING.
   5  *
   6  * \author Dekel Tsur (original code)
   7  * \author Richard Heck (re-implementation)
   8  *
   9  * Full author contact details are available in file CREDITS.
  10  */
  11
  12 #include <config.h>
  13
  14 #include "Graph.h"
  15 #include "Format.h"
  16
  17 #include "support/debug.h"
  18 #include "support/lassert.h"
  19
  20 #include <algorithm>
  21
  22 using namespace std;
  23
  24 namespace lyx {
  25
  26
  27 bool Graph::bfs_init(int s, bool clear_visited)
  28 {
  29         if (s < 0)
  30                 return false;
  31
  32         Q_ = queue<int>();
  33
  34         if (clear_visited) {
  35                 vector<Vertex>::iterator it = vertices_.begin();
  36                 vector<Vertex>::iterator en = vertices_.end();
  37                 for (; it != en; ++it)
  38                         it->visited = false;
  39         }
  40         if (!vertices_[s].visited) {
  41                 Q_.push(s);
  42                 vertices_[s].visited = true;
  43         }
  44         return true;
  45 }
  46
  47
  48 void Graph::clearMarks()
  49 {
  50         Arrows::iterator it = arrows_.begin();
  51         Arrows::iterator const en = arrows_.end();
  52         for (; it != en; ++it)
  53                 it->marked = false;
  54 }
  55
  56
  57 vector<int> const
  58         Graph::getReachableTo(int target, bool clear_visited)
  59 {
  60         vector<int> result;
  61         if (!bfs_init(target, clear_visited))
  62                 return result;
  63
  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
  69         // search.
  70         while (!Q_.empty()) {
  71                 int const current = Q_.front();
  72                 Q_.pop();
  73                 if (current != target || formats.get(target).name() != "lyx")
  74                         result.push_back(current);
  75
  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;
  82                                 Q_.push(cv);
  83                         }
  84                 }
  85         }
  86
  87         return result;
  88 }
  89
  90
  91 vector<int> const
  92         Graph::getReachable(int from, bool only_viewable,
  93                 bool clear_visited)
  94 {
  95         vector<int> result;
  96         if (!bfs_init(from, clear_visited))
  97                 return result;
  98
  99         while (!Q_.empty()) {
 100                 int const current = Q_.front();
 101                 Q_.pop();
 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);
 110                 }
 111
 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;
 120                                 Q_.push(cv);
 121                         }
 122                 }
 123         }
 124
 125         return result;
 126 }
 127
 128
 129 bool Graph::isReachable(int from, int to)
 130 {
 131         if (from == to)
 132                 return true;
 133
 134         if (to < 0 || !bfs_init(from))
 135                 return false;
 136
 137         while (!Q_.empty()) {
 138                 int const current = Q_.front();
 139                 Q_.pop();
 140                 if (current == to)
 141                         return true;
 142
 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;
 151                                 Q_.push(cv);
 152                         }
 153                 }
 154         }
 155
 156         return false;
 157 }
 158
 159
 160 Graph::EdgePath const Graph::getPath(int from, int to)
 161 {
 162         EdgePath path;
 163         if (from == to)
 164                 return path;
 165
 166         if (to < 0 || !bfs_init(from))
 167                 return path;
 168
 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
 174         // the marked path.
 175         bool found = false;
 176         clearMarks();
 177         while (!Q_.empty()) {
 178                 int const current = Q_.front();
 179                 Q_.pop();
 180
 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;
 190                                 Q_.push(cv);
 191                                 (*cit)->marked = true;
 192                         }
 193                         if (cv == to) {
 194                                 found = true;
 195                                 break;
 196                         }
 197                 }
 198         }
 199         if (!found)
 200                 return path;
 201
 202         getMarkedPath(from, to, path);
 203         return path;
 204 }
 205
 206
 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) {
 214         if (from == to) {
 215                 reverse(path.begin(), path.end());
 216                 return;
 217         }
 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)
 222                 if ((*it)->marked)
 223                         break;
 224         if (it == en) {
 225                 LASSERT(false, /* */);
 226                 return;
 227         }
 228         int const newnode = (*it)->from;
 229         path.push_back(newnode);
 230         getMarkedPath(from, newnode, path);
 231 }
 232
 233
 234 void Graph::init(int size)
 235 {
 236         vertices_ = vector<Vertex>(size);
 237         arrows_.clear();
 238         numedges_ = 0;
 239 }
 240
 241
 242 void Graph::addEdge(int from, int to)
 243 {
 244         arrows_.push_back(Arrow(from, to, numedges_));
 245         numedges_++;
 246         Arrow * ar = &(arrows_.back());
 247         vertices_[to].in_arrows.push_back(ar);
 248         vertices_[from].out_arrows.push_back(ar);
 249 }
 250
 251
 252 } // namespace lyx