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