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