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