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
   7  *
   8  * Full author contact details are available in file CREDITS.
   9  */
  10
  11 #include <config.h>
  12
  13 #include "Graph.h"
  14 #include "Format.h"
  15
  16 #include <algorithm>
  17
  18 using namespace std;
  19
  20 namespace lyx {
  21
  22
  23 bool Graph::bfs_init(int s, bool clear_visited)
  24 {
  25         if (s < 0)
  26                 return false;
  27
  28         Q_ = queue<int>();
  29
  30         if (clear_visited) {
  31                 vector<Vertex>::iterator it = vertices_.begin();
  32                 vector<Vertex>::iterator en = vertices_.end();
  33                 for (; it != en; ++it)
  34                         it->visited = false;
  35         }
  36         if (!vertices_[s].visited) {
  37                 Q_.push(s);
  38                 vertices_[s].visited = true;
  39         }
  40         return true;
  41 }
  42
  43
  44 vector<int> const
  45         Graph::getReachableTo(int target, bool clear_visited)
  46 {
  47         vector<int> result;
  48         if (!bfs_init(target, clear_visited))
  49                 return result;
  50
  51         // Here's the logic, which is shared by the other routines.
  52         // Q_ holds a list of nodes we have been able to reach (in this
  53         // case, reach backwards). It is initialized to the current node
  54         // by bfs_init, and then we recurse, adding the nodes we can reach
  55         // from the current node as we go. That makes it a breadth-first
  56         // search.
  57         while (!Q_.empty()) {
  58                 int const current = Q_.front();
  59                 Q_.pop();
  60                 if (current != target || formats.get(target).name() != "lyx")
  61                         result.push_back(current);
  62
  63                 vector<Arrow>::iterator it = vertices_[current].in_arrows.begin();
  64                 vector<Arrow>::iterator const end = vertices_[current].in_arrows.end();
  65                 for (; it != end; ++it) {
  66                         const int cv = it->vertex;
  67                         if (!vertices_[cv].visited) {
  68                                 vertices_[cv].visited = true;
  69                                 Q_.push(cv);
  70                         }
  71                 }
  72         }
  73
  74         return result;
  75 }
  76
  77
  78 vector<int> const
  79         Graph::getReachable(int from, bool only_viewable,
  80                 bool clear_visited)
  81 {
  82         vector<int> result;
  83         if (!bfs_init(from, clear_visited))
  84                 return result;
  85
  86         while (!Q_.empty()) {
  87                 int const current = Q_.front();
  88                 Q_.pop();
  89                 Format const & format = formats.get(current);
  90                 if (!only_viewable || !format.viewer().empty())
  91                         result.push_back(current);
  92                 else if (format.isChildFormat()) {
  93                         Format const * const parent =
  94                                 formats.getFormat(format.parentFormat());
  95                         if (parent && !parent->viewer().empty())
  96                                 result.push_back(current);
  97                 }
  98
  99                 vector<Arrow>::const_iterator cit =
 100                         vertices_[current].out_arrows.begin();
 101                 vector<Arrow>::const_iterator end =
 102                         vertices_[current].out_arrows.end();
 103                 for (; cit != end; ++cit) {
 104                         int const cv = cit->vertex;
 105                         if (!vertices_[cv].visited) {
 106                                 vertices_[cv].visited = true;
 107                                 Q_.push(cv);
 108                         }
 109                 }
 110         }
 111
 112         return result;
 113 }
 114
 115
 116 bool Graph::isReachable(int from, int to)
 117 {
 118         if (from == to)
 119                 return true;
 120
 121         if (to < 0 || !bfs_init(from))
 122                 return false;
 123
 124         while (!Q_.empty()) {
 125                 int const current = Q_.front();
 126                 Q_.pop();
 127                 if (current == to)
 128                         return true;
 129
 130                 vector<Arrow>::const_iterator cit =
 131                         vertices_[current].out_arrows.begin();
 132                 vector<Arrow>::const_iterator end =
 133                         vertices_[current].out_arrows.end();
 134                 for (; cit != end; ++cit) {
 135                         int const cv = cit->vertex;
 136                         if (!vertices_[cv].visited) {
 137                                 vertices_[cv].visited = true;
 138                                 Q_.push(cv);
 139                         }
 140                 }
 141         }
 142
 143         return false;
 144 }
 145
 146
 147 Graph::EdgePath const Graph::getPath(int from, int to)
 148 {
 149         EdgePath path;
 150         if (from == to)
 151                 return path;
 152
 153         if (to < 0 || !bfs_init(from))
 154                 return path;
 155
 156         // pair<vertex, edge>
 157         vector<pair<int, int> > prev(vertices_.size());
 158
 159         bool found = false;
 160         while (!Q_.empty()) {
 161                 int const current = Q_.front();
 162                 Q_.pop();
 163
 164                 vector<Arrow>::const_iterator const beg =
 165                         vertices_[current].out_arrows.begin();
 166                 vector<Arrow>::const_iterator cit = beg;
 167                 vector<Arrow>::const_iterator end =
 168                         vertices_[current].out_arrows.end();
 169                 for (; cit != end; ++cit) {
 170                         int const cv = cit->vertex;
 171                         if (!vertices_[cv].visited) {
 172                                 vertices_[cv].visited = true;
 173                                 Q_.push(cv);
 174                                 // FIXME This will not do for finding multiple paths.
 175                                 // Perhaps we need a vector, or a set. We'll also want
 176                                 // to add this info, even if the node is visited, so
 177                                 // outside this conditional.
 178                                 prev[cv] = pair<int, int>(current, cit->edge);
 179                         }
 180                         if (cv == to) {
 181                                 found = true;
 182                                 break;
 183                         }
 184                 }
 185         }
 186         if (!found)
 187                 return path;
 188
 189         while (to != from) {
 190                 path.push_back(prev[to].second);
 191                 to = prev[to].first;
 192         }
 193         reverse(path.begin(), path.end());
 194         return path;
 195 }
 196
 197
 198 void Graph::init(int size)
 199 {
 200         vertices_ = vector<Vertex>(size);
 201         numedges_ = 0;
 202 }
 203
 204
 205 void Graph::addEdge(int from, int to)
 206 {
 207         vertices_[to].in_arrows.push_back(Arrow(from, numedges_));
 208         vertices_[from].out_arrows.push_back(Arrow(to, numedges_));
 209         ++numedges_;
 210 }
 211
 212
 213 } // namespace lyx