Line data    Source code

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