src/graph.C

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