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