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
  19 namespace lyx {
  20
  21 using std::vector;
  22 using std::reverse;
  23 using std::fill;
  24
  25
  26 int Graph::bfs_init(int s, bool clear_visited)
  27 {
  28         if (s < 0)
  29                 return s;
  30
  31         Q_ = std::queue<int>();
  32
  33         if (clear_visited)
  34                 fill(visited_.begin(), visited_.end(), false);
  35         if (visited_[s] == false) {
  36                 Q_.push(s);
  37                 visited_[s] = true;
  38         }
  39         return s;
  40 }
  41
  42
  43 vector<int> const
  44 Graph::getReachableTo(int target, bool clear_visited)
  45 {
  46         vector<int> result;
  47         int const s = bfs_init(target, clear_visited);
  48         if (s < 0)
  49                 return result;
  50
  51         while (!Q_.empty()) {
  52                 int const i = Q_.front();
  53                 Q_.pop();
  54                 if (i != s || formats.get(target).name() != "lyx") {
  55                         result.push_back(i);
  56                 }
  57
  58                 vector<int>::iterator it = vertices_[i].in_vertices.begin();
  59                 vector<int>::iterator end = vertices_[i].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) < 0)
  78                 return result;
  79
  80         while (!Q_.empty()) {
  81                 int const i = Q_.front();
  82                 Q_.pop();
  83                 Format const & format = formats.get(i);
  84                 if (!only_viewable || !format.viewer().empty())
  85                         result.push_back(i);
  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(i);
  91                 }
  92
  93                 vector<int>::const_iterator cit =
  94                         vertices_[i].out_vertices.begin();
  95                 vector<int>::const_iterator end =
  96                         vertices_[i].out_vertices.end();
  97                 for (; cit != end; ++cit)
  98                         if (!visited_[*cit]) {
  99                                 visited_[*cit] = true;
 100                                 Q_.push(*cit);
 101                         }
 102         }
 103
 104         return result;
 105 }
 106
 107
 108 bool Graph::isReachable(int from, int to)
 109 {
 110         if (from == to)
 111                 return true;
 112
 113         int const s = bfs_init(from);
 114         if (s < 0 || to < 0)
 115                 return false;
 116
 117         while (!Q_.empty()) {
 118                 int const i = Q_.front();
 119                 Q_.pop();
 120                 if (i == to)
 121                         return true;
 122
 123                 vector<int>::const_iterator cit =
 124                         vertices_[i].out_vertices.begin();
 125                 vector<int>::const_iterator end =
 126                         vertices_[i].out_vertices.end();
 127                 for (; cit != end; ++cit) {
 128                         if (!visited_[*cit]) {
 129                                 visited_[*cit] = true;
 130                                 Q_.push(*cit);
 131                         }
 132                 }
 133         }
 134
 135         return false;
 136 }
 137
 138
 139 Graph::EdgePath const
 140 Graph::getPath(int from, int t)
 141 {
 142         EdgePath path;
 143         if (from == t)
 144                 return path;
 145
 146         int const s = bfs_init(from);
 147         if (s < 0 || t < 0)
 148                 return path;
 149
 150         vector<int> prev_edge(formats.size());
 151         vector<int> prev_vertex(formats.size());
 152
 153         bool found = false;
 154         while (!Q_.empty()) {
 155                 int const i = Q_.front();
 156                 Q_.pop();
 157                 if (i == t) {
 158                         found = true;
 159                         break;
 160                 }
 161
 162                 vector<int>::const_iterator beg =
 163                         vertices_[i].out_vertices.begin();
 164                 vector<int>::const_iterator cit = beg;
 165                 vector<int>::const_iterator end =
 166                         vertices_[i].out_vertices.end();
 167                 for (; cit != end; ++cit)
 168                         if (!visited_[*cit]) {
 169                                 int const j = *cit;
 170                                 visited_[j] = true;
 171                                 Q_.push(j);
 172                                 int const k = cit - beg;
 173                                 prev_edge[j] = vertices_[i].out_edges[k];
 174                                 prev_vertex[j] = i;
 175                         }
 176         }
 177         if (!found)
 178                 return path;
 179
 180         while (t != s) {
 181                 path.push_back(prev_edge[t]);
 182                 t = prev_vertex[t];
 183         }
 184         reverse(path.begin(), path.end());
 185         return path;
 186 }
 187
 188 void Graph::init(int size)
 189 {
 190         vertices_ = vector<Vertex>(size);
 191         visited_.resize(size);
 192         numedges_ = 0;
 193 }
 194
 195 void Graph::addEdge(int s, int t)
 196 {
 197         vertices_[t].in_vertices.push_back(s);
 198         vertices_[s].out_vertices.push_back(t);
 199         vertices_[s].out_edges.push_back(numedges_++);
 200 }
 201
 202 vector<Graph::Vertex> Graph::vertices_;
 203
 204
 205 } // namespace lyx