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 class Graph {
  23 public:
  24         Graph() : numedges_(0) {};
  25         ///
  26         typedef std::vector<int> EdgePath;
  27         ///
  28         std::vector<int> const
  29         getReachableTo(int, bool clear_visited);
  30         ///
  31         std::vector<int> const
  32         getReachable(int, bool only_viewable,
  33                      bool clear_visited);
  34         ///
  35         bool isReachable(int, int);
  36         ///
  37         EdgePath const getPath(int, int);
  38         ///
  39         void addEdge(int s, int t);
  40         ///
  41         void init(int size);
  42
  43 private:
  44         ///
  45         int bfs_init(int, bool clear_visited = true);
  46
  47         ///
  48         class Vertex {
  49         public:
  50                 std::vector<int> in_vertices;
  51                 std::vector<int> out_vertices;
  52                 std::vector<int> out_edges;
  53         };
  54         ///
  55         static
  56         std::vector<Vertex> vertices_;
  57         ///
  58         std::vector<bool> visited_;
  59         ///
  60         std::queue<int> Q_;
  61
  62         int numedges_;
  63
  64 };
  65
  66
  67
  68 } // namespace lyx
  69
  70 #endif //GRAPH_H