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