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