Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  * Copyright Contributors to the OpenSDN project
       4             :  */
       5             : 
       6             : #ifndef ctrlplane_db_graph_h
       7             : #define ctrlplane_db_graph_h
       8             : 
       9             : #include <queue>
      10             : 
      11             : #include <boost/function.hpp>
      12             : #include <boost/iterator/iterator_facade.hpp>
      13             : #include <boost/tuple/tuple.hpp>
      14             : #include "db/db_graph_base.h"
      15             : #include "db/db_graph_vertex.h"
      16             : 
      17             : class DBGraphEdge;
      18             : 
      19             : class DBGraph : public DBGraphBase {
      20             : public:
      21             :     typedef DBGraphBase::edge_descriptor Edge;
      22             :     typedef DBGraphBase::vertex_descriptor Vertex;
      23             :     typedef boost::function<void(DBGraphVertex *)> VertexVisitor;
      24             :     typedef boost::function<void(DBGraphEdge *)> EdgeVisitor;
      25             :     typedef boost::function<void(DBGraphVertex *)> VertexFinish;
      26             : 
      27             :     struct VisitorFilter {
      28             :         typedef std::set<std::string> AllowedEdgeSet;
      29             :         // bool return value indicates that all edges are allowed except
      30             :         // filterd by EdgeFilter
      31             :         typedef  std::pair<bool, AllowedEdgeSet> AllowedEdgeRetVal;
      32         186 :         virtual ~VisitorFilter() { }
      33           0 :         virtual bool VertexFilter(const DBGraphVertex *vertex) const {
      34           0 :             return true;
      35             :         }
      36           0 :         virtual bool EdgeFilter(const DBGraphVertex *source,
      37             :                                 const DBGraphVertex *target,
      38             :                                 const DBGraphEdge *edge) const {
      39           0 :             return true;
      40             :         }
      41           0 :         virtual AllowedEdgeRetVal AllowedEdges(const DBGraphVertex *vertex) const {
      42           0 :             return std::make_pair(false, std::set<std::string>());
      43             :         }
      44             :     };
      45             : 
      46             :     typedef boost::tuple<DBGraphVertex *, DBGraphVertex *, DBGraphEdge *> DBEdgeInfo;
      47             :     class edge_iterator : public boost::iterator_facade<
      48             :     edge_iterator, DBEdgeInfo, boost::forward_traversal_tag, DBEdgeInfo
      49             :     > {
      50             :     public:
      51             :         explicit edge_iterator(DBGraph *graph);
      52             :     private:
      53             :         friend class boost::iterator_core_access;
      54          45 :         void increment() {
      55          45 :             ++iter_;
      56          45 :         }
      57             :         bool equal(const edge_iterator &rhs) const;
      58             :         DBEdgeInfo dereference() const;
      59             :         DBGraph *graph_;
      60             :         DBGraphBase::edge_iterator iter_;
      61             :         DBGraphBase::edge_iterator end_;
      62             :     };
      63             : 
      64             :     class vertex_iterator : public boost::iterator_facade<
      65             :         vertex_iterator, DBGraphVertex, boost::forward_traversal_tag> {
      66             :     public:
      67             :         explicit vertex_iterator(DBGraph *graph);
      68             : 
      69             :     private:
      70             :         friend class boost::iterator_core_access;
      71         239 :         void increment() {
      72         239 :             ++iter_;
      73         239 :         }
      74             :         bool equal(const vertex_iterator &rhs) const;
      75         239 :         DBGraphVertex &dereference() const {
      76         239 :             return *graph_->vertex_data(*iter_);
      77             :         }
      78             : 
      79             :         DBGraph *graph_;
      80             :         graph_t::vertex_iterator iter_;
      81             :         graph_t::vertex_iterator end_;
      82             :     };
      83             : 
      84             :     void AddNode(DBGraphVertex *entry);
      85             : 
      86             :     void RemoveNode(DBGraphVertex *entry);
      87             : 
      88             :     Edge Link(DBGraphVertex *lhs, DBGraphVertex *rhs, DBGraphEdge *link);
      89             : 
      90             :     void Unlink(DBGraphEdge *link);
      91             : 
      92     1355515 :     const graph_t *graph() const { return &graph_; }
      93             : 
      94     2327991 :     DBGraphVertex *vertex_data(DBGraphBase::vertex_descriptor vertex) const {
      95     2327991 :         return graph_[vertex].entry;
      96             :     }
      97             : 
      98             :     const std::string edge_name(DBGraph::Edge edge) const {
      99             :         return graph_[edge].name_;
     100             :     }
     101             : 
     102      942810 :     DBGraphEdge *edge_data(DBGraph::Edge edge) const {
     103      942810 :         return graph_[edge].edge;
     104             :     }
     105             : 
     106             :     void Visit(DBGraphVertex *start, VertexVisitor vertex_visit_fn,
     107             :                EdgeVisitor edge_visit_fn);
     108             :     void Visit(DBGraphVertex *start, VertexVisitor vertex_visit_fn,
     109             :                EdgeVisitor edge_visit_fn, const VisitorFilter &filter);
     110             :     void Visit(DBGraphVertex *start, VertexVisitor vertex_visit_fn,
     111             :                EdgeVisitor edge_visit_fn, VertexFinish vertex_finish_fn);
     112             : 
     113             :     edge_iterator edge_list_begin();
     114             :     edge_iterator edge_list_end();
     115             : 
     116             :     vertex_iterator vertex_list_begin();
     117             :     vertex_iterator vertex_list_end();
     118             : 
     119             :     void clear();
     120             : 
     121             :     size_t vertex_count() const;
     122             :     size_t edge_count() const;
     123             : 
     124             : private:
     125             :     typedef std::queue<DBGraphVertex *> VisitQ;
     126             :     struct EdgePredicate;
     127             :     struct VertexPredicate;
     128             : 
     129             :     void IterateEdges(DBGraphVertex *start,
     130             :                   OutEdgeIterator &iter_begin, OutEdgeIterator &iter_end,
     131             :                   VertexVisitor vertex_visit_fn, EdgeVisitor edge_visit_fn,
     132             :                   EdgePredicate &edge_test, VertexPredicate &vertex_test,
     133             :                   uint64_t curr_walk, VisitQ &visit_queue,
     134             :                   bool match_name=false, const std::string &allowed_edge = "");
     135             : 
     136             :     DBGraphVertex *vertex_target(DBGraphVertex *current_vertex,
     137             :                                  DBGraphEdge *edge);
     138             : 
     139             :     graph_t graph_;
     140             : };
     141             : 
     142             : #endif