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