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         while (!Q_.empty()) {
  48                 int const current = Q_.front();
  49                 Q_.pop();
  50                 if (current != target || formats.get(target).name() != "lyx") {
  51                         result.push_back(current);
  52                 }
  53
  54                 vector<int>::iterator it = vertices_[current].in_vertices.begin();
  55                 vector<int>::iterator end = vertices_[current].in_vertices.end();
  56                 for (; it != end; ++it) {
  57                         if (!visited_[*it]) {
  58                                 visited_[*it] = true;
  59                                 Q_.push(*it);
  60                         }
  61                 }
  62         }
  63
  64         return result;
  65 }
  66
  67
  68 vector<int> const
  69 Graph::getReachable(int from, bool only_viewable,
  70                     bool clear_visited)
  71 {
  72         vector<int> result;
  73         if (!bfs_init(from, clear_visited))
  74                 return result;
  75
  76         while (!Q_.empty()) {
  77                 int const i = Q_.front();
  78                 Q_.pop();
  79                 Format const & format = formats.get(i);
  80                 if (!only_viewable || !format.viewer().empty())
  81                         result.push_back(i);
  82                 else if (format.isChildFormat()) {
  83                         Format const * const parent =
  84                                 formats.getFormat(format.parentFormat());
  85                         if (parent && !parent->viewer().empty())
  86                                 result.push_back(i);
  87                 }
  88
  89                 vector<int>::const_iterator cit =
  90                         vertices_[i].out_vertices.begin();
  91                 vector<int>::const_iterator end =
  92                         vertices_[i].out_vertices.end();
  93                 for (; cit != end; ++cit)
  94                         if (!visited_[*cit]) {
  95                                 visited_[*cit] = true;
  96                                 Q_.push(*cit);
  97                         }
  98         }
  99
 100         return result;
 101 }
 102
 103
 104 bool Graph::isReachable(int from, int to)
 105 {
 106         if (from == to)
 107                 return true;
 108
 109         if (to < 0 || !bfs_init(from))
 110                 return false;
 111
 112         while (!Q_.empty()) {
 113                 int const current = Q_.front();
 114                 Q_.pop();
 115                 if (current == to)
 116                         return true;
 117
 118                 vector<int>::const_iterator cit =
 119                         vertices_[current].out_vertices.begin();
 120                 vector<int>::const_iterator end =
 121                         vertices_[current].out_vertices.end();
 122                 for (; cit != end; ++cit) {
 123                         if (!visited_[*cit]) {
 124                                 visited_[*cit] = true;
 125                                 Q_.push(*cit);
 126                         }
 127                 }
 128         }
 129
 130         return false;
 131 }
 132
 133
 134 Graph::EdgePath const Graph::getPath(int from, int to)
 135 {
 136         EdgePath path;
 137         if (from == to)
 138                 return path;
 139
 140         if (to < 0 || !bfs_init(from))
 141                 return path;
 142
 143         vector<int> prev_edge(formats.size());
 144         vector<int> prev_vertex(formats.size());
 145
 146         bool found = false;
 147         while (!Q_.empty()) {
 148                 int const current = Q_.front();
 149                 Q_.pop();
 150                 if (current == to) {
 151                         found = true;
 152                         break;
 153                 }
 154
 155                 vector<int>::const_iterator const beg =
 156                         vertices_[current].out_vertices.begin();
 157                 vector<int>::const_iterator cit = beg;
 158                 vector<int>::const_iterator end =
 159                         vertices_[current].out_vertices.end();
 160                 for (; cit != end; ++cit)
 161                         if (!visited_[*cit]) {
 162                                 int const j = *cit;
 163                                 visited_[j] = true;
 164                                 Q_.push(j);
 165                                 int const k = cit - beg;
 166                                 prev_edge[j] = vertices_[current].out_edges[k];
 167                                 prev_vertex[j] = current;
 168                         }
 169         }
 170         if (!found)
 171                 return path;
 172
 173         while (to != from) {
 174                 path.push_back(prev_edge[to]);
 175                 to = prev_vertex[to];
 176         }
 177         reverse(path.begin(), path.end());
 178         return path;
 179 }
 180
 181
 182 void Graph::init(int size)
 183 {
 184         vertices_ = vector<Vertex>(size);
 185         visited_.resize(size);
 186         numedges_ = 0;
 187 }
 188
 189
 190 void Graph::addEdge(int from, int to)
 191 {
 192         vertices_[to].in_vertices.push_back(from);
 193         vertices_[from].out_vertices.push_back(to);
 194         vertices_[from].out_edges.push_back(numedges_++);
 195 }
 196
 197
 198 vector<Graph::Vertex> Graph::vertices_;
 199
 200
 201 } // namespace lyx