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