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