src/graph.h

   1 // -*- C++ -*-
   2
   3 #ifndef GRAPH_H
   4 #define GRAPH_H
   5
   6 /**
   7  * \file graph.h
   8  * This file is part of LyX, the document processor.
   9  * Licence details can be found in the file COPYING.
  10  *
  11  * \author Dekel Tsur
  12  *
  13  * Full author contact details are available in file CREDITS
  14  */
  15
  16 #include "LString.h"
  17
  18 #include <queue>
  19 #include <vector>
  20
  21 class Graph {
  22 public:
  23         Graph() : numedges_(0) {};
  24         ///
  25         typedef std::vector<int> EdgePath;
  26         ///
  27         std::vector<int> const
  28         getReachableTo(int, bool clear_visited);
  29         ///
  30         std::vector<int> const
  31         getReachable(int, bool only_viewable,
  32                      bool clear_visited);
  33         ///
  34         bool isReachable(int, int);
  35         ///
  36         EdgePath const getPath(int, int);
  37         ///
  38         void addEdge(int s, int t);
  39         ///
  40         void init(int size);
  41
  42 private:
  43         ///
  44         int bfs_init(int, bool clear_visited = true);
  45
  46         ///
  47         struct Vertex {
  48                 std::vector<int> in_vertices;
  49                 std::vector<int> out_vertices;
  50                 std::vector<int> out_edges;
  51         };
  52         ///
  53         static
  54         std::vector<Vertex> vertices_;
  55         ///
  56         std::vector<bool> visited_;
  57         ///
  58         std::queue<int> Q_;
  59
  60         int numedges_;
  61
  62 };
  63
  64
  65 #endif //GRAPH_H