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