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