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