src/Graph.h

   1 // -*- C++ -*-
   2 /**
   3  * \file Graph.h
   4  * This file is part of LyX, the document processor.
   5  * Licence details can be found in the file COPYING.
   6  *
   7  * \author Dekel Tsur
   8  *
   9  * Full author contact details are available in file CREDITS.
  10  */
  11
  12 #ifndef GRAPH_H
  13 #define GRAPH_H
  14
  15 #include <queue>
  16 #include <vector>
  17
  18
  19 namespace lyx {
  20
  21
  22 /// Represents a directed graph, possibly with multiple edges
  23 /// connecting the vertices.
  24 class Graph {
  25 public:
  26         Graph() : numedges_(0) {}
  27         ///
  28         typedef std::vector<int> EdgePath;
  29         /// \return a vector of the vertices from which "to" can be reached
  30         std::vector<int> const getReachableTo(int to, bool clear_visited);
  31         /// \return a vector of the vertices that can be reached from "from"
  32         std::vector<int> const
  33                 getReachable(int from, bool only_viewable, bool clear_visited);
  34         /// Can "from" be reached from "to"?
  35         bool isReachable(int from, int to);
  36         /// Find a path from "from" to "to".
  37         EdgePath const getPath(int from, int to);
  38         /// Called repeatedly to build the graph.
  39         void addEdge(int from, int to);
  40         /// Reset the internal data structures.
  41         void init(int size);
  42
  43 private:
  44         ///
  45         bool bfs_init(int, bool clear_visited = true);
  46
  47         ///
  48         struct Arrow {
  49                 ///
  50                 Arrow(int v, int e): vertex(v), edge(e) {}
  51                 ///
  52                 int vertex;
  53                 ///
  54                 int edge;
  55         };
  56         ///
  57         struct Vertex {
  58                 /// vertices that point at this one
  59                 std::vector<Arrow> in_arrows;
  60                 /// paths out from here
  61                 std::vector<Arrow> out_arrows;
  62                 ///
  63                 bool visited;
  64         };
  65         ///
  66         std::vector<Vertex> vertices_;
  67         ///
  68         std::queue<int> Q_;
  69
  70         int numedges_;
  71
  72 };
  73
  74
  75
  76 } // namespace lyx
  77
  78 #endif //GRAPH_H