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