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 (original code)
   8  * \author Richard Heck (re-implementation)
   9  *
  10  * Full author contact details are available in file CREDITS.
  11  */
  12
  13 #ifndef GRAPH_H
  14 #define GRAPH_H
  15
  16
  17 #include <list>
  18 #include <queue>
  19 #include <vector>
  20
  21
  22 namespace lyx {
  23
  24
  25 /// Represents a directed graph, possibly with multiple edges
  26 /// connecting the vertices.
  27 class Graph {
  28 public:
  29         Graph() : numedges_(0) {}
  30         ///
  31         typedef std::vector<int> EdgePath;
  32         /// \return a vector of the vertices from which "to" can be reached
  33         EdgePath const getReachableTo(int to, bool clear_visited);
  34         /// \return a vector of the reachable vertices, avoiding "exclude"
  35         EdgePath const getReachable(int from, bool only_viewable,
  36                 bool clear_visited, int exclude);
  37         /// \return a vector of the reachable vertices, avoiding all "excludes"
  38         EdgePath const getReachable(int from, bool only_viewable,
  39                 bool clear_visited, std::vector<int> excludes);
  40         /// can "from" be reached from "to"?
  41         bool isReachable(int from, int to);
  42         /// find a path from "from" to "to". always returns one of the
  43         /// shortest such paths.
  44         EdgePath const getPath(int from, int to);
  45         /// called repeatedly to build the graph
  46         void addEdge(int from, int to);
  47         /// reset the internal data structures
  48         void init(int size);
  49
  50 private:
  51         ///
  52         bool bfs_init(int, bool clear_visited, std::queue<int> & Q);
  53         /// these represent the arrows connecting the nodes of the graph.
  54         /// this is the basic representation of the graph: as a bunch of
  55         /// arrows.
  56         struct Arrow {
  57                 ///
  58                 Arrow(int f, int t, int i):
  59                         from(f), to(t), id(i) {}
  60                 /// the vertex at the tail of the arrow
  61                 int from;
  62                 /// the vertex at the head
  63                 int to;
  64                 /// an id for this arrow, e.g., for use in describing paths
  65                 /// through the graph
  66                 int id;
  67         };
  68         /// a container for the arrows
  69         /// we use a list because we want pointers to the arrows,
  70         /// and a vector might invalidate them
  71         typedef std::list<Arrow> Arrows;
  72         Arrows arrows_;
  73         /// Represents a vertex of the graph. Note that we could recover
  74         /// the in_arrows and out_arrows from the Arrows, so these are in
  75         /// effect a kind of cache.
  76         struct Vertex {
  77                 /// arrows that point at this one
  78                 std::vector<Arrow *> in_arrows;
  79                 /// arrows out from here
  80                 std::vector<Arrow *> out_arrows;
  81                 /// used in the search routines
  82                 bool visited;
  83         };
  84         /// a container for the vertices
  85         /// the index into the vector functions as the identifier by which
  86         /// these are referenced in the Arrow struct
  87         /// the code making use of the Graph must keep track of the relation
  88         /// between these indices and the objects they represent. (in the case
  89         /// of Format, this is easy, since the Format objects already have ints
  90         /// as identifiers.)
  91         std::vector<Vertex> vertices_;
  92
  93         /// a counter that we use to assign id's to the arrows
  94         /// FIXME This technique assumes a correspondence between the
  95         /// ids of the arrows and ids associated with Converters that
  96         /// seems kind of fragile. Perhaps a better solution would be
  97         /// to pass the ids as we create the arrows.
  98         int numedges_;
  99 };
 100
 101
 102
 103 } // namespace lyx
 104
 105 #endif //GRAPH_H