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 bool Graph::bfs_init(int s, bool clear_visited)
  24 {
  25         if (s < 0)
  26                 return false;
  27
  28         Q_ = queue<int>();
  29
  30         if (clear_visited) {
  31                 vector<Vertex>::iterator it = vertices_.begin();
  32                 vector<Vertex>::iterator en = vertices_.end();
  33                 for (; it != en; ++it)
  34                         it->visited = false;
  35         }
  36         if (!vertices_[s].visited) {
  37                 Q_.push(s);
  38                 vertices_[s].visited = true;
  39         }
  40         return true;
  41 }
  42
  43
  44 vector<int> const
  45         Graph::getReachableTo(int target, bool clear_visited)
  46 {
  47         vector<int> result;
  48         if (!bfs_init(target, clear_visited))
  49                 return result;
  50
  51         // Here's the logic, which is shared by the other routines.
  52         // Q_ holds a list of nodes we have been able to reach (in this
  53         // case, reach backwards). It is initailized to the current node
  54         // by bfs_init, and then we recurse, adding the nodes we can reach
  55         // from the current node as we go. That makes it a breadth-first
  56         // search.
  57         while (!Q_.empty()) {
  58                 int const current = Q_.front();
  59                 Q_.pop();
  60                 if (current != target || formats.get(target).name() != "lyx")
  61                         result.push_back(current);
  62
  63                 vector<int>::iterator it = vertices_[current].in_vertices.begin();
  64                 vector<int>::iterator end = vertices_[current].in_vertices.end();
  65                 for (; it != end; ++it) {
  66                         if (!vertices_[*it].visited) {
  67                                 vertices_[*it].visited = true;
  68                                 Q_.push(*it);
  69                         }
  70                 }
  71         }
  72
  73         return result;
  74 }
  75
  76
  77 vector<int> const
  78         Graph::getReachable(int from, bool only_viewable,
  79                 bool clear_visited)
  80 {
  81         vector<int> result;
  82         if (!bfs_init(from, clear_visited))
  83                 return result;
  84
  85         while (!Q_.empty()) {
  86                 int const current = Q_.front();
  87                 Q_.pop();
  88                 Format const & format = formats.get(current);
  89                 if (!only_viewable || !format.viewer().empty())
  90                         result.push_back(current);
  91                 else if (format.isChildFormat()) {
  92                         Format const * const parent =
  93                                 formats.getFormat(format.parentFormat());
  94                         if (parent && !parent->viewer().empty())
  95                                 result.push_back(current);
  96                 }
  97
  98                 vector<OutEdge>::const_iterator cit =
  99                         vertices_[current].out_arrows.begin();
 100                 vector<OutEdge>::const_iterator end =
 101                         vertices_[current].out_arrows.end();
 102                 for (; cit != end; ++cit) {
 103                         int const cv = cit->vertex;
 104                         if (!vertices_[cv].visited) {
 105                                 vertices_[cv].visited = true;
 106                                 Q_.push(cv);
 107                         }
 108                 }
 109         }
 110
 111         return result;
 112 }
 113
 114
 115 bool Graph::isReachable(int from, int to)
 116 {
 117         if (from == to)
 118                 return true;
 119
 120         if (to < 0 || !bfs_init(from))
 121                 return false;
 122
 123         while (!Q_.empty()) {
 124                 int const current = Q_.front();
 125                 Q_.pop();
 126                 if (current == to)
 127                         return true;
 128
 129                 vector<OutEdge>::const_iterator cit =
 130                         vertices_[current].out_arrows.begin();
 131                 vector<OutEdge>::const_iterator end =
 132                         vertices_[current].out_arrows.end();
 133                 for (; cit != end; ++cit) {
 134                         int const cv = cit->vertex;
 135                         if (!vertices_[cv].visited) {
 136                                 vertices_[cv].visited = true;
 137                                 Q_.push(cv);
 138                         }
 139                 }
 140         }
 141
 142         return false;
 143 }
 144
 145
 146 Graph::EdgePath const Graph::getPath(int from, int to)
 147 {
 148         EdgePath path;
 149         if (from == to)
 150                 return path;
 151
 152         if (to < 0 || !bfs_init(from))
 153                 return path;
 154
 155         // pair<vertex, edge>
 156         vector<pair<int, int> > prev(vertices_.size());
 157
 158         bool found = false;
 159         while (!Q_.empty()) {
 160                 int const current = Q_.front();
 161                 Q_.pop();
 162
 163                 vector<OutEdge>::const_iterator const beg =
 164                         vertices_[current].out_arrows.begin();
 165                 vector<OutEdge>::const_iterator cit = beg;
 166                 vector<OutEdge>::const_iterator end =
 167                         vertices_[current].out_arrows.end();
 168                 for (; cit != end; ++cit) {
 169                         int const cv = cit->vertex;
 170                         if (!vertices_[cv].visited) {
 171                                 vertices_[cv].visited = true;
 172                                 Q_.push(cv);
 173                                 // FIXME This will not do for finding multiple paths.
 174                                 // Perhaps we need a vector, or a set. We'll also want
 175                                 // to add this info, even if the node is visited, so
 176                                 // outside this conditional.
 177                                 prev[cv] = pair<int, int>(current, cit->edge);
 178                         }
 179                         if (cv == to) {
 180                                 found = true;
 181                                 break;
 182                         }
 183                 }
 184         }
 185         if (!found)
 186                 return path;
 187
 188         while (to != from) {
 189                 path.push_back(prev[to].second);
 190                 to = prev[to].first;
 191         }
 192         reverse(path.begin(), path.end());
 193         return path;
 194 }
 195
 196
 197 void Graph::init(int size)
 198 {
 199         vertices_ = vector<Vertex>(size);
 200         numedges_ = 0;
 201 }
 202
 203
 204 void Graph::addEdge(int from, int to)
 205 {
 206         vertices_[to].in_vertices.push_back(from);
 207         vertices_[from].out_arrows.push_back(OutEdge(to, numedges_++));
 208 }
 209
 210
 211 } // namespace lyx