GraphWalker.h

Go to the documentation of this file.

#ifndef DATA_FORMATS_MATH_GRAPH_WALKER_H
#define DATA_FORMATS_MATH_GRAPH_WALKER_H

#include "DataFormats/Math/interface/Graph.h"
#include <queue>
#include <vector>

namespace math {

  template <class N, class E>
  class GraphWalker {
  public:
    using index_type = typename math::Graph<N, E>::index_type;
    using index_result = typename math::Graph<N, E>::index_result;
    using edge_type = typename math::Graph<N, E>::edge_type;
    using edge_list = typename math::Graph<N, E>::edge_list;
    using edge_iterator = typename math::Graph<N, E>::edge_iterator;
    using const_edge_iterator = typename math::Graph<N, E>::const_edge_iterator;

    // only a const-edge_range!
    using edge_range = std::pair<const_edge_iterator, const_edge_iterator>;

    using stack_type = std::vector<edge_range>;
    using bfs_type = std::queue<edge_type>;

    using result_type = bool;
    using value_type = typename math::Graph<N, E>::value_type;

  public:
    GraphWalker(const Graph<N, E> &);

    GraphWalker(const Graph<N, E> &, const N &);

    GraphWalker() = delete;
    // operations

    result_type firstChild();

    result_type nextSibling();

    result_type parent();

    result_type next();

    inline value_type current() const;

    result_type next_bfs();
    value_type current_bfs() const;

    void reset();

    const stack_type &stack() const { return stack_; }

  protected:
    // stack_.back().first corresponds to index of the current node!
    stack_type stack_;  // hierarchical stack used in navigation
    bfs_type queue_;    // breath first search queue
    edge_list root_;    // root of the walker
    const Graph<N, E> &graph_;
  };

  template <class N, class E>
  GraphWalker<N, E>::GraphWalker(const Graph<N, E> &g) : graph_(g) {  // complexity = (no nodes) * (no edges)
    graph_.findRoots(root_);
    stack_.emplace_back(edge_range(root_.begin(), root_.end()));
    if (!root_.empty()) {
      queue_.push(root_[0]);
    }
  }

  template <class N, class E>
  GraphWalker<N, E>::GraphWalker(const Graph<N, E> &g, const N &root) : graph_(g) {
    index_result rr = graph_.nodeIndex(root);
    if (!rr.second)  // no such root node, no walker can be created!
      throw root;

    root_.emplace_back(edge_type(rr.first, 0));
    stack_.emplace_back(edge_range(root_.begin(), root_.end()));
    queue_.push(root_[0]);
  }

  template <class N, class E>
  typename GraphWalker<N, E>::value_type GraphWalker<N, E>::current() const {
    const edge_range &er = stack_.back();
    return value_type(graph_.nodeData(er.first->first), graph_.edgeData(er.first->second));
  }

  template <class N, class E>
  typename GraphWalker<N, E>::value_type GraphWalker<N, E>::current_bfs() const {
    const edge_type &e = queue_.front();
    return value_type(graph_.nodeData(e.first), graph_.edgeData(e.second));
  }

  template <class N, class E>
  void GraphWalker<N, E>::reset() {
    stack_.clear();
    stack_.emplace_back(edge_range(root_.begin(), root_.end()));
    queue_.clear();
    if (root_.size()) {
      queue_.push(root_[0]);
    }
  }

  template <class N, class E>
  typename GraphWalker<N, E>::result_type GraphWalker<N, E>::firstChild() {
    result_type result = false;
    const edge_range &adjEdges = graph_.edges(stack_.back().first->first);
    if (adjEdges.first != adjEdges.second) {
      stack_.emplace_back(adjEdges);
      result = true;
    }
    return result;
  }

  template <class N, class E>
  typename GraphWalker<N, E>::result_type GraphWalker<N, E>::nextSibling() {
    result_type result = false;
    edge_range &siblings = stack_.back();
    if (siblings.first != (siblings.second - 1)) {
      ++siblings.first;
      result = true;
    }
    return result;
  }

  template <class N, class E>
  typename GraphWalker<N, E>::result_type GraphWalker<N, E>::parent() {
    result_type result = false;
    if (stack_.size() > 1) {
      stack_.pop_back();
      result = true;
    }
    return result;
  }

  template <class N, class E>
  typename GraphWalker<N, E>::result_type GraphWalker<N, E>::next() {
    result_type result = false;
    if (firstChild()) {
      result = true;
    } else if (stack_.size() > 1 && nextSibling()) {
      result = true;
    } else {
      while (parent()) {
        if (stack_.size() > 1 && nextSibling()) {
          result = true;
          break;
        }
      }
    }
    return result;
  }

  template <class N, class E>
  typename GraphWalker<N, E>::result_type GraphWalker<N, E>::next_bfs() {
    result_type result(false);
    if (!queue_.empty()) {
      const edge_type &e = queue_.front();
      const edge_range &er = graph_.edges(e.first);
      const_edge_iterator it(er.first), ed(er.second);
      for (; it != ed; ++it) {
        queue_.push(*it);
      }
      queue_.pop();
      if (!queue_.empty()) {
        result = true;
      }
    }
    return result;
  }

}  // namespace math

#endif