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::clearPaths()
  49 {
  50         vector<Vertex>::iterator it = vertices_.begin();
  51         vector<Vertex>::iterator en = vertices_.end();
  52         for (; it != en; ++it)
  53                 it->path.clear();
  54 }
  55
  56
  57 vector<int> const
  58         Graph::getReachableTo(int target, bool clear_visited)
  59 {
  60         Mutex::Locker lock(&mutex_);
  61
  62         vector<int> result;
  63         if (!bfs_init(target, clear_visited))
  64                 return result;
  65
  66         // Here's the logic, which is shared by the other routines.
  67         // Q_ holds a list of nodes we have been able to reach (in this
  68         // case, reach backwards). It is initialized to the current node
  69         // by bfs_init, and then we recurse, adding the nodes we can reach
  70         // from the current node as we go. That makes it a breadth-first
  71         // search.
  72         while (!Q_.empty()) {
  73                 int const current = Q_.front();
  74                 Q_.pop();
  75                 if (current != target || formats.get(target).name() != "lyx")
  76                         result.push_back(current);
  77
  78                 vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
  79                 vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
  80                 for (; it != end; ++it) {
  81                         const int cv = (*it)->from;
  82                         if (!vertices_[cv].visited) {
  83                                 vertices_[cv].visited = true;
  84                                 Q_.push(cv);
  85                         }
  86                 }
  87         }
  88
  89         return result;
  90 }
  91
  92
  93 vector<int> const
  94         Graph::getReachable(int from, bool only_viewable,
  95                 bool clear_visited)
  96 {
  97         Mutex::Locker lock(&mutex_);
  98
  99         vector<int> result;
 100         if (!bfs_init(from, clear_visited))
 101                 return result;
 102
 103         while (!Q_.empty()) {
 104                 int const current = Q_.front();
 105                 Q_.pop();
 106                 Format const & format = formats.get(current);
 107                 if (!only_viewable || !format.viewer().empty())
 108                         result.push_back(current);
 109                 else if (format.isChildFormat()) {
 110                         Format const * const parent =
 111                                 formats.getFormat(format.parentFormat());
 112                         if (parent && !parent->viewer().empty())
 113                                 result.push_back(current);
 114                 }
 115
 116                 vector<Arrow *>::const_iterator cit =
 117                         vertices_[current].out_arrows.begin();
 118                 vector<Arrow *>::const_iterator end =
 119                         vertices_[current].out_arrows.end();
 120                 for (; cit != end; ++cit) {
 121                         int const cv = (*cit)->to;
 122                         if (!vertices_[cv].visited) {
 123                                 vertices_[cv].visited = true;
 124                                 Q_.push(cv);
 125                         }
 126                 }
 127         }
 128
 129         return result;
 130 }
 131
 132
 133 bool Graph::isReachable(int from, int to)
 134 {
 135         Mutex::Locker lock(&mutex_);
 136
 137         if (from == to)
 138                 return true;
 139
 140         if (to < 0 || !bfs_init(from))
 141                 return false;
 142
 143         while (!Q_.empty()) {
 144                 int const current = Q_.front();
 145                 Q_.pop();
 146                 if (current == to)
 147                         return true;
 148
 149                 vector<Arrow *>::const_iterator cit =
 150                         vertices_[current].out_arrows.begin();
 151                 vector<Arrow *>::const_iterator end =
 152                         vertices_[current].out_arrows.end();
 153                 for (; cit != end; ++cit) {
 154                         int const cv = (*cit)->to;
 155                         if (!vertices_[cv].visited) {
 156                                 vertices_[cv].visited = true;
 157                                 Q_.push(cv);
 158                         }
 159                 }
 160         }
 161
 162         return false;
 163 }
 164
 165
 166 Graph::EdgePath const Graph::getPath(int from, int to)
 167 {
 168         Mutex::Locker lock(&mutex_);
 169
 170         if (from == to)
 171                 return EdgePath();
 172
 173         if (to < 0 || !bfs_init(from))
 174                 return EdgePath();
 175
 176         clearPaths();
 177         while (!Q_.empty()) {
 178                 int const current = Q_.front();
 179                 Q_.pop();
 180
 181                 vector<Arrow *>::const_iterator cit =
 182                         vertices_[current].out_arrows.begin();
 183                 vector<Arrow *>::const_iterator end =
 184                         vertices_[current].out_arrows.end();
 185                 for (; cit != end; ++cit) {
 186                         int const cv = (*cit)->to;
 187                         if (!vertices_[cv].visited) {
 188                                 vertices_[cv].visited = true;
 189                                 Q_.push(cv);
 190                                 // NOTE If we wanted to collect all the paths, then
 191                                 // we just need to collect them here and not worry
 192                                 // about "visited".
 193                                 EdgePath lastpath = vertices_[(*cit)->from].path;
 194                                 lastpath.push_back((*cit)->id);
 195                                 vertices_[cv].path = lastpath;
 196                         }
 197                         if (cv == to) {
 198                                 return vertices_[cv].path;
 199                         }
 200                 }
 201         }
 202         // failure
 203         return EdgePath();
 204 }
 205
 206
 207 void Graph::init(int size)
 208 {
 209         Mutex::Locker lock(&mutex_);
 210
 211         vertices_ = vector<Vertex>(size);
 212         arrows_.clear();
 213         numedges_ = 0;
 214 }
 215
 216
 217 void Graph::addEdge(int from, int to)
 218 {
 219         Mutex::Locker lock(&mutex_);
 220
 221         arrows_.push_back(Arrow(from, to, numedges_));
 222         numedges_++;
 223         Arrow * ar = &(arrows_.back());
 224         vertices_[to].in_arrows.push_back(ar);
 225         vertices_[from].out_arrows.push_back(ar);
 226 }
 227
 228
 229 // At present, we do not need this debugging code, but
 230 // I am going to leave it here in case we need it again.
 231 #if 0
 232 void Graph::dumpGraph() const
 233 {
 234         vector<Vertex>::const_iterator it = vertices_.begin();
 235         vector<Vertex>::const_iterator en = vertices_.end();
 236         for (; it != en; ++it) {
 237                 LYXERR0("Next vertex...");
 238                 LYXERR0("In arrows...");
 239                 std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
 240                 std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
 241                 for (; iit != ien; ++iit)
 242                         LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
 243                 LYXERR0("Out arrows...");
 244                 iit = it->out_arrows.begin();
 245                 ien = it->out_arrows.end();
 246                 for (; iit != ien; ++iit)
 247                         LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
 248         }
 249 }
 250 #endif
 251
 252
 253 } // namespace lyx