Math/interface/GraphWalker.h

0001 #ifndef DATA_FORMATS_MATH_GRAPH_WALKER_H
0002 #define DATA_FORMATS_MATH_GRAPH_WALKER_H
0003
0004 #include "DataFormats/Math/interface/Graph.h"
0005 #include <queue>
0006 #include <vector>
0007
0008 namespace math {
0009
0010   /** a walker for an acyclic directed multigraph */
0011   template <class N, class E>
0012   class GraphWalker {
0013   public:
0014     using index_type = typename math::Graph<N, E>::index_type;
0015     using index_result = typename math::Graph<N, E>::index_result;
0016     using edge_type = typename math::Graph<N, E>::edge_type;
0017     using edge_list = typename math::Graph<N, E>::edge_list;
0018     using edge_iterator = typename math::Graph<N, E>::edge_iterator;
0019     using const_edge_iterator = typename math::Graph<N, E>::const_edge_iterator;
0020
0021     // only a const-edge_range!
0022     using edge_range = std::pair<const_edge_iterator, const_edge_iterator>;
0023
0024     using stack_type = std::vector<edge_range>;
0025     using bfs_type = std::queue<edge_type>;
0026
0027     using result_type = bool;
0028     using value_type = typename math::Graph<N, E>::value_type;
0029
0030   public:
0031     //! creates a walker rooted by the first candidate root found in the underlying Graph
0032     GraphWalker(const Graph<N, E> &);
0033
0034     //! creates a walker rooted by the node given
0035     GraphWalker(const Graph<N, E> &, const N &);
0036
0037     GraphWalker() = delete;
0038     // operations
0039
0040     result_type firstChild();
0041
0042     result_type nextSibling();
0043
0044     result_type parent();
0045
0046     result_type next();
0047
0048     inline value_type current() const;
0049
0050     result_type next_bfs();
0051     value_type current_bfs() const;
0052
0053     void reset();
0054
0055     const stack_type &stack() const { return stack_; }
0056
0057   protected:
0058     // stack_.back().first corresponds to index of the current node!
0059     stack_type stack_;  // hierarchical stack used in navigation
0060     bfs_type queue_;    // breath first search queue
0061     edge_list root_;    // root of the walker
0062     const Graph<N, E> &graph_;
0063   };
0064
0065   template <class N, class E>
0066   GraphWalker<N, E>::GraphWalker(const Graph<N, E> &g) : graph_(g) {  // complexity = (no nodes) * (no edges)
0067     graph_.findRoots(root_);
0068     stack_.emplace_back(edge_range(root_.begin(), root_.end()));
0069     if (!root_.empty()) {
0070       queue_.push(root_[0]);
0071     }
0072   }
0073
0074   template <class N, class E>
0075   GraphWalker<N, E>::GraphWalker(const Graph<N, E> &g, const N &root) : graph_(g) {
0076     index_result rr = graph_.nodeIndex(root);
0077     if (!rr.second)  // no such root node, no walker can be created!
0078       throw root;
0079
0080     root_.emplace_back(edge_type(rr.first, 0));
0081     stack_.emplace_back(edge_range(root_.begin(), root_.end()));
0082     queue_.push(root_[0]);
0083   }
0084
0085   template <class N, class E>
0086   typename GraphWalker<N, E>::value_type GraphWalker<N, E>::current() const {
0087     const edge_range &er = stack_.back();
0088     return value_type(graph_.nodeData(er.first->first), graph_.edgeData(er.first->second));
0089   }
0090
0091   template <class N, class E>
0092   typename GraphWalker<N, E>::value_type GraphWalker<N, E>::current_bfs() const {
0093     const edge_type &e = queue_.front();
0094     return value_type(graph_.nodeData(e.first), graph_.edgeData(e.second));
0095   }
0096
0097   template <class N, class E>
0098   void GraphWalker<N, E>::reset() {
0099     stack_.clear();
0100     stack_.emplace_back(edge_range(root_.begin(), root_.end()));
0101     queue_.clear();
0102     if (root_.size()) {
0103       queue_.push(root_[0]);
0104     }
0105   }
0106
0107   template <class N, class E>
0108   typename GraphWalker<N, E>::result_type GraphWalker<N, E>::firstChild() {
0109     result_type result = false;
0110     const edge_range &adjEdges = graph_.edges(stack_.back().first->first);
0111     if (adjEdges.first != adjEdges.second) {
0112       stack_.emplace_back(adjEdges);
0113       result = true;
0114     }
0115     return result;
0116   }
0117
0118   template <class N, class E>
0119   typename GraphWalker<N, E>::result_type GraphWalker<N, E>::nextSibling() {
0120     result_type result = false;
0121     edge_range &siblings = stack_.back();
0122     if (siblings.first != (siblings.second - 1)) {
0123       ++siblings.first;
0124       result = true;
0125     }
0126     return result;
0127   }
0128
0129   template <class N, class E>
0130   typename GraphWalker<N, E>::result_type GraphWalker<N, E>::parent() {
0131     result_type result = false;
0132     if (stack_.size() > 1) {
0133       stack_.pop_back();
0134       result = true;
0135     }
0136     return result;
0137   }
0138
0139   template <class N, class E>
0140   typename GraphWalker<N, E>::result_type GraphWalker<N, E>::next() {
0141     result_type result = false;
0142     if (firstChild()) {
0143       result = true;
0144     } else if (stack_.size() > 1 && nextSibling()) {
0145       result = true;
0146     } else {
0147       while (parent()) {
0148         if (stack_.size() > 1 && nextSibling()) {
0149           result = true;
0150           break;
0151         }
0152       }
0153     }
0154     return result;
0155   }
0156
0157   template <class N, class E>
0158   typename GraphWalker<N, E>::result_type GraphWalker<N, E>::next_bfs() {
0159     result_type result(false);
0160     if (!queue_.empty()) {
0161       const edge_type &e = queue_.front();
0162       const edge_range &er = graph_.edges(e.first);
0163       const_edge_iterator it(er.first), ed(er.second);
0164       for (; it != ed; ++it) {
0165         queue_.push(*it);
0166       }
0167       queue_.pop();
0168       if (!queue_.empty()) {
0169         result = true;
0170       }
0171     }
0172     return result;
0173   }
0174
0175 }  // namespace math
0176
0177 #endif