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 initailized 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.
  56         while (!Q_.empty()) {
  57                 int const current = Q_.front();
  58                 Q_.pop();
  59                 if (current != target || formats.get(target).name() != "lyx")
  60                         result.push_back(current);
  61
  62                 vector<int>::iterator it = vertices_[current].in_vertices.begin();
  63                 vector<int>::iterator end = vertices_[current].in_vertices.end();
  64                 for (; it != end; ++it) {
  65                         if (!vertices_[*it].visited) {
  66                                 vertices_[*it].visited = true;
  67                                 Q_.push(*it);
  68                         }
  69                 }
  70         }
  71
  72         return result;
  73 }
  74
  75
  76 vector<int> const
  77         Graph::getReachable(int from, bool only_viewable,
  78                 bool clear_visited)
  79 {
  80         vector<int> result;
  81         if (!bfs_init(from, clear_visited))
  82                 return result;
  83
  84         while (!Q_.empty()) {
  85                 int const current = Q_.front();
  86                 Q_.pop();
  87                 Format const & format = formats.get(current);
  88                 if (!only_viewable || !format.viewer().empty())
  89                         result.push_back(current);
  90                 else if (format.isChildFormat()) {
  91                         Format const * const parent =
  92                                 formats.getFormat(format.parentFormat());
  93                         if (parent && !parent->viewer().empty())
  94                                 result.push_back(current);
  95                 }
  96
  97                 vector<OutEdge>::const_iterator cit =
  98                         vertices_[current].out_arrows.begin();
  99                 vector<OutEdge>::const_iterator end =
 100                         vertices_[current].out_arrows.end();
 101                 for (; cit != end; ++cit) {
 102                         int const cv = cit->vertex;
 103                         if (!vertices_[cv].visited) {
 104                                 vertices_[cv].visited = true;
 105                                 Q_.push(cv);
 106                         }
 107                 }
 108         }
 109
 110         return result;
 111 }
 112
 113
 114 bool Graph::isReachable(int from, int to)
 115 {
 116         if (from == to)
 117                 return true;
 118
 119         if (to < 0 || !bfs_init(from))
 120                 return false;
 121
 122         while (!Q_.empty()) {
 123                 int const current = Q_.front();
 124                 Q_.pop();
 125                 if (current == to)
 126                         return true;
 127
 128                 vector<OutEdge>::const_iterator cit =
 129                         vertices_[current].out_arrows.begin();
 130                 vector<OutEdge>::const_iterator end =
 131                         vertices_[current].out_arrows.end();
 132                 for (; cit != end; ++cit) {
 133                         int const cv = cit->vertex;
 134                         if (!vertices_[cv].visited) {
 135                                 vertices_[cv].visited = true;
 136                                 Q_.push(cv);
 137                         }
 138                 }
 139         }
 140
 141         return false;
 142 }
 143
 144
 145 Graph::EdgePath const Graph::getPath(int from, int to)
 146 {
 147         EdgePath path;
 148         if (from == to)
 149                 return path;
 150
 151         if (to < 0 || !bfs_init(from))
 152                 return path;
 153
 154         // pair<vertex, edge>
 155         vector<pair<int, int> > prev(vertices_.size());
 156
 157         bool found = false;
 158         while (!Q_.empty()) {
 159                 int const current = Q_.front();
 160                 Q_.pop();
 161
 162                 vector<OutEdge>::const_iterator const beg =
 163                         vertices_[current].out_arrows.begin();
 164                 vector<OutEdge>::const_iterator cit = beg;
 165                 vector<OutEdge>::const_iterator end =
 166                         vertices_[current].out_arrows.end();
 167                 for (; cit != end; ++cit) {
 168                         int const cv = cit->vertex;
 169                         if (!vertices_[cv].visited) {
 170                                 vertices_[cv].visited = true;
 171                                 Q_.push(cv);
 172                                 // FIXME This will not do for finding multiple paths.
 173                                 // Perhaps we need a vector, or a set. We'll also want
 174                                 // to add this info, even if the node is visited, so
 175                                 // outside this conditional.
 176                                 prev[cv] = pair<int, int>(current, cit->edge);
 177                         }
 178                         if (cv == to) {
 179                                 found = true;
 180                                 break;
 181                         }
 182                 }
 183         }
 184         if (!found)
 185                 return path;
 186
 187         while (to != from) {
 188                 path.push_back(prev[to].second);
 189                 to = prev[to].first;
 190         }
 191         reverse(path.begin(), path.end());
 192         return path;
 193 }
 194
 195
 196 void Graph::init(int size)
 197 {
 198         vertices_ = vector<Vertex>(size);
 199         numedges_ = 0;
 200 }
 201
 202
 203 void Graph::addEdge(int from, int to)
 204 {
 205         vertices_[to].in_vertices.push_back(from);
 206         vertices_[from].out_arrows.push_back(OutEdge(to, numedges_++));
 207 }
 208
 209
 210 } // namespace lyx