Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2013 Juniper Networks, Inc. All rights reserved.
       3             :  */
       4             : 
       5             : #include "db/db_graph.h"
       6             : 
       7             : #ifdef __clang__
       8             : #pragma clang diagnostic push
       9             : #pragma clang diagnostic ignored "-Wunused-variable"
      10             : #pragma clang diagnostic ignored "-Wunneeded-internal-declaration"
      11             : #endif
      12             : 
      13             : #include <boost/foreach.hpp>
      14             : #include <boost/scoped_ptr.hpp>
      15             : #include <boost/graph/breadth_first_search.hpp>
      16             : #include <boost/graph/filtered_graph.hpp>
      17             : 
      18             : #ifdef __clang__
      19             : #pragma clang diagnostic pop
      20             : #endif
      21             : 
      22             : #include "base/logging.h"
      23             : #include "base/time_util.h"
      24             : #include "db/db_graph_vertex.h"
      25             : #include "db/db_graph_edge.h"
      26             : 
      27             : using namespace std;
      28             : using namespace boost;
      29             : 
      30      189087 : void DBGraph::AddNode(DBGraphVertex *entry) {
      31      189087 :     entry->set_vertex(add_vertex(graph_));
      32      189087 :     DBGraphBase::VertexProperties &vertex = graph_[entry->vertex()];
      33      189087 :     vertex.entry = entry;
      34      189087 : }
      35             : 
      36      189077 : void DBGraph::RemoveNode(DBGraphVertex *entry) {
      37      189077 :     remove_vertex(entry->vertex(), graph_);
      38      189077 :     entry->VertexInvalidate();
      39      189077 : }
      40             : 
      41      159821 : DBGraph::Edge DBGraph::Link(DBGraphVertex *lhs, DBGraphVertex *rhs,
      42             :                             DBGraphEdge *edge) {
      43      159821 :     DBGraph::Edge edge_id;
      44             :     bool added;
      45      159821 :     boost::tie(edge_id, added) = add_edge(lhs->vertex(), rhs->vertex(),
      46      319642 :                                     EdgeProperties(edge->name(), edge), graph_);
      47      159821 :     assert(added);
      48      159821 :     edge->SetEdge(edge_id);
      49      319642 :     return edge_id;
      50             : }
      51             : 
      52      159813 : void DBGraph::Unlink(DBGraphEdge *edge) {
      53      159813 :     remove_edge(edge->edge_id(), graph_);
      54      159813 : }
      55             : 
      56             : template <typename GraphType>
      57             : class BFSVisitor : public default_bfs_visitor {
      58             : public:
      59             :     typedef DBGraphBase::VertexProperties Properties;
      60             : 
      61           5 :     BFSVisitor(DBGraph::VertexVisitor vertex_visit,
      62             :                DBGraph::EdgeVisitor edge_visit)
      63           5 :         : vertex_visit_(vertex_visit), edge_visit_(edge_visit) {
      64           5 :     }
      65             : 
      66           0 :     BFSVisitor(DBGraph::VertexVisitor vertex_visit,
      67             :                DBGraph::EdgeVisitor edge_visit,
      68             :                DBGraph::VertexFinish vertex_finish)
      69           0 :         : vertex_visit_(vertex_visit), edge_visit_(edge_visit),
      70           0 :           vertex_finish_(vertex_finish) {
      71           0 :     }
      72             : 
      73          21 :     void discover_vertex(DBGraph::Vertex u, const GraphType &graph) const {
      74          21 :         if (vertex_visit_) {
      75          21 :             vertex_visit_(graph[u].entry);
      76             :         }
      77          21 :     }
      78             : 
      79          21 :     void finish_vertex(DBGraph::Vertex u, const GraphType &graph) const {
      80          21 :         if (vertex_finish_) {
      81           0 :             vertex_finish_(graph[u].entry);
      82             :         }
      83          21 :     }
      84             : 
      85             :     // Edges are examined twice: once for the source and once for the target
      86             :     // node.
      87          34 :     void examine_edge(DBGraph::Edge e, const GraphType &graph) const {
      88          34 :         const DBGraphBase::EdgeProperties &properties = graph[e];
      89          34 :         if (edge_visit_) {
      90          18 :             edge_visit_(properties.edge);
      91             :         }
      92          34 :     }
      93             : 
      94             : private:
      95             :     DBGraph::VertexVisitor vertex_visit_;
      96             :     DBGraph::EdgeVisitor edge_visit_;
      97             :     DBGraph::VertexFinish vertex_finish_;
      98             : };
      99             : 
     100             : typedef std::map<DBGraph::Vertex, default_color_type> ColorMap;
     101             : 
     102           0 : void DBGraph::Visit(DBGraphVertex *start, VertexVisitor vertex_visit_fn,
     103             :                     EdgeVisitor edge_visit_fn, VertexFinish vertex_finish_fn) {
     104             :     const BFSVisitor<graph_t> vis(vertex_visit_fn, edge_visit_fn,
     105           0 :                                   vertex_finish_fn);
     106           0 :     ColorMap color_map;
     107           0 :     breadth_first_search(graph_, start->vertex(),
     108           0 :         visitor(vis).color_map(make_assoc_property_map(color_map)));
     109           0 : }
     110             : 
     111           5 : void DBGraph::Visit(DBGraphVertex *start, VertexVisitor vertex_visit_fn,
     112             :                     EdgeVisitor edge_visit_fn) {
     113          10 :     const BFSVisitor<graph_t> vis(vertex_visit_fn, edge_visit_fn);
     114           5 :     ColorMap color_map;
     115           5 :     breadth_first_search(graph_, start->vertex(),
     116          10 :         visitor(vis).color_map(make_assoc_property_map(color_map)));
     117           5 : }
     118             : 
     119             : struct DBGraph::EdgePredicate {
     120             :     EdgePredicate() : graph_(NULL), filter_(NULL) { }
     121         130 :     EdgePredicate(const DBGraph *graph, const VisitorFilter &filter)
     122         130 :         : graph_(graph), filter_(&filter) {
     123         130 :     }
     124             : 
     125         539 :     bool operator()(const DBGraphVertex *src, const DBGraphVertex *tgt,
     126             :                     const DBGraphEdge *edge) const {
     127         539 :         if (edge->IsDeleted()) {
     128           0 :             return false;
     129             :         }
     130         539 :         return filter_->EdgeFilter(src, tgt, edge);
     131             :     }
     132             : 
     133             : private:
     134             :     const DBGraph *graph_;
     135             :     const VisitorFilter *filter_;
     136             : };
     137             : 
     138             : struct DBGraph::VertexPredicate {
     139             :     VertexPredicate() : graph_(NULL), filter_(NULL) { }
     140         130 :     VertexPredicate(const DBGraph *graph, const VisitorFilter &filter)
     141         130 :         : graph_(graph), filter_(&filter) {
     142         130 :     }
     143         534 :     bool operator()(const DBGraphVertex *entry) const {
     144         534 :         if (entry->IsDeleted()) {
     145           0 :             return false;
     146             :         }
     147         534 :         return filter_->VertexFilter(entry);
     148             :     }
     149             : private:
     150             :     const DBGraph *graph_;
     151             :     const VisitorFilter *filter_;
     152             : };
     153             : 
     154         539 : DBGraphVertex *DBGraph::vertex_target(DBGraphVertex *current_vertex,
     155             :                                       DBGraphEdge *edge) {
     156         539 :     DBGraphVertex *adjacent_vertex = edge->target(this);
     157         539 :     if (adjacent_vertex == current_vertex) {
     158         245 :         adjacent_vertex = edge->source(this);
     159             :     }
     160         539 :     return adjacent_vertex;
     161             : }
     162             : 
     163             : 
     164        3414 : void DBGraph::IterateEdges(DBGraphVertex *current_vertex,
     165             :                    OutEdgeIterator &iter_begin, OutEdgeIterator &iter_end,
     166             :                    VertexVisitor vertex_visit_fn, EdgeVisitor edge_visit_fn,
     167             :                    EdgePredicate &edge_test, VertexPredicate &vertex_test,
     168             :                    ::uint64_t curr_walk, /* ::uint64_t because using namespace boost above */
     169             :                    VisitQ &visit_q,
     170             :                    bool match_name, const std::string &allowed_edge) {
     171        3953 :     for (; iter_begin != iter_end; ++iter_begin) {
     172        3081 :         const DBGraph::EdgeProperties &e_prop = get(edge_bundle, *iter_begin);
     173        3081 :         DBGraphEdge *edge = e_prop.edge;
     174        3081 :         if (match_name && e_prop.name() != allowed_edge) break;
     175         539 :         DBGraphVertex *adjacent_vertex = vertex_target(current_vertex, edge);
     176         539 :         if (edge_visit_fn) edge_visit_fn(edge);
     177         550 :         if (!edge_test(current_vertex, adjacent_vertex, edge)) continue;
     178         415 :         if (adjacent_vertex->visited(curr_walk)) continue;
     179         404 :         if (vertex_test(adjacent_vertex)) {
     180         398 :             vertex_visit_fn(adjacent_vertex);
     181         398 :             visit_q.push(adjacent_vertex);
     182             :         }
     183         404 :         adjacent_vertex->set_visited(curr_walk);
     184             :     }
     185        3414 : }
     186             : 
     187         130 : void DBGraph::Visit(DBGraphVertex *start, VertexVisitor vertex_visit_fn,
     188             :                     EdgeVisitor edge_visit_fn, const VisitorFilter &filter) {
     189             :     // uint64_t t = ClockMonotonicUsec();
     190         130 :     ::uint64_t curr_walk = get_graph_walk_num(); /* ::uint64_t because using namespace boost above */
     191         130 :     EdgePredicate edge_test(this, filter);
     192         130 :     VertexPredicate vertex_test(this, filter);
     193             : 
     194         130 :     VisitQ visit_q;
     195             : 
     196         130 :     visit_q.push(start);
     197         130 :     start->set_visited(curr_walk);
     198         130 :     if (vertex_test(start)) {
     199         130 :         vertex_visit_fn(start);
     200             :     }
     201         658 :     while (!visit_q.empty()) {
     202         528 :         DBGraphVertex *vertex = visit_q.front();
     203         528 :         visit_q.pop();
     204             :         // Get All out-edges from the node
     205         528 :         OutEdgeListType &out_edge_set = graph_.out_edge_list(vertex->vertex());
     206         528 :         if (out_edge_set.empty()) continue;
     207             : 
     208         524 :         OutEdgeListType::iterator it = out_edge_set.begin();
     209         524 :         OutEdgeListType::iterator it_end = out_edge_set.end();
     210             : 
     211             :         // Collect all allowed edges to visit
     212             :         DBGraph::VisitorFilter::AllowedEdgeRetVal allowed_edge_ret =
     213         524 :             filter.AllowedEdges(vertex);
     214             : 
     215         524 :         if (!allowed_edge_ret.first) {
     216        3898 :             for (auto allowed_edge : allowed_edge_ret.second) {
     217        3394 :                 EdgeContainer fake_container;
     218        3394 :                 fake_container.push_back(
     219        6788 :                          EdgeType(0, 0, EdgeProperties(allowed_edge, NULL)));
     220        3394 :                 StoredEdge es(vertex->vertex(), fake_container.begin());
     221             :                 // Call lower_bound on out edge list and walk on selected edges
     222        3394 :                 it = out_edge_set.lower_bound(es);
     223        3394 :                 IterateEdges(vertex, it, it_end, vertex_visit_fn, edge_visit_fn,
     224             :                 edge_test, vertex_test, curr_walk, visit_q, true, allowed_edge);
     225        3394 :             }
     226             :         } else {
     227          20 :             IterateEdges(vertex, it, it_end, vertex_visit_fn, edge_visit_fn,
     228             :                          edge_test, vertex_test, curr_walk, visit_q);
     229             :         }
     230         524 :     }
     231             :     // uint64_t end_t = ClockMonotonicUsec();
     232             :     // std::cout << "Graph Walk time(in usec) " <<  (end_t-t) << std::endl;
     233         130 : }
     234             : 
     235          10 : DBGraph::edge_iterator::edge_iterator(DBGraph *graph) : graph_(graph) {
     236          10 :     if (graph_) {
     237           4 :         boost::tie(iter_, end_) = edges(*graph_->graph());
     238             :     }
     239          10 : }
     240             : 
     241           2 : DBGraph::DBEdgeInfo DBGraph::edge_iterator::dereference() const {
     242           2 :     Vertex src = source(*iter_, *graph_->graph());
     243           2 :     Vertex tgt = target(*iter_, *graph_->graph());
     244           2 :     return boost::make_tuple(graph_->vertex_data(src), graph_->vertex_data(tgt),
     245           6 :                              graph_->edge_data(*iter_));
     246             : }
     247             : 
     248           6 : bool DBGraph::edge_iterator::equal(const edge_iterator &rhs) const {
     249           6 :     if (graph_ != NULL) {
     250           6 :         if (rhs.graph_ == NULL) {
     251           6 :             return (iter_ == end_);
     252             :         }
     253           0 :         return iter_ == rhs.iter_;
     254             :     } else {
     255           0 :         if (rhs.graph_ != NULL) {
     256           0 :             return (rhs.iter_ == rhs.end_);
     257             :         }
     258           0 :         return true;
     259             :     }
     260             : }
     261             : 
     262           4 : DBGraph::edge_iterator DBGraph::edge_list_begin() {
     263           4 :     return edge_iterator(this);
     264             : }
     265             : 
     266           6 : DBGraph::edge_iterator DBGraph::edge_list_end() {
     267           6 :     return edge_iterator(NULL);
     268             : }
     269             : 
     270           2 : DBGraph::vertex_iterator::vertex_iterator(DBGraph *graph)
     271           2 :     : graph_(graph) {
     272           2 :     if (graph_ != NULL) {
     273           1 :         boost::tie(iter_, end_) = vertices(*graph_->graph());
     274             :     }
     275           2 : }
     276             : 
     277           1 : bool DBGraph::vertex_iterator::equal(const vertex_iterator &rhs) const {
     278           1 :     if (graph_ != NULL) {
     279           1 :         if (rhs.graph_ != NULL) {
     280           0 :             return iter_ == rhs.iter_;
     281             :         } else {
     282           1 :             return (iter_ == end_);
     283             :         }
     284             :     } else {
     285           0 :         if (rhs.graph_ != NULL) {
     286           0 :             return rhs.iter_ == rhs.end_;
     287             :         } else {
     288           0 :             return true;
     289             :         }
     290             :     }
     291             : }
     292             : 
     293           1 : DBGraph::vertex_iterator DBGraph::vertex_list_begin() {
     294           1 :     return vertex_iterator(this);
     295             : }
     296             : 
     297           1 : DBGraph::vertex_iterator DBGraph::vertex_list_end() {
     298           1 :     return vertex_iterator(NULL);
     299             : }
     300             : 
     301           3 : void DBGraph::clear() {
     302           3 :     graph_.clear();
     303           3 : }
     304             : 
     305         585 : size_t DBGraph::vertex_count() const {
     306         585 :     return num_vertices(graph_);
     307             : }
     308             : 
     309         536 : size_t DBGraph::edge_count() const {
     310         536 :     return num_edges(graph_);
     311             : }
     312             : 
     313             : template <class StoredEdge>
     314      300390 : bool order_by_name<StoredEdge>::operator()(const StoredEdge& e1, const StoredEdge& e2) const {
     315      300390 :     const DBGraph::EdgeProperties &edge1 = get(edge_bundle, e1);
     316      300390 :     const DBGraph::EdgeProperties &edge2 = get(edge_bundle, e2);
     317      300390 :     return edge1.name() < edge2.name();
     318             : }