Graph.h

Go to the documentation of this file.

#ifndef DATA_FORMATS_MATH_GRAPH_H
#define DATA_FORMATS_MATH_GRAPH_H

#include <iostream>
#include <map>
#include <vector>

// Adjecencylist Graph
namespace math {

  // N,E must be concepts of default constructable, assignable, copyable, operator<
  template <class N, class E>
  class Graph {
  public:
    using index_type = std::vector<double>::size_type;
    // (node-index target, edge)
    using edge_type = std::pair<index_type, index_type>;
    // (std::vector of edge_types for the adj_list)
    using edge_list = std::vector<edge_type>;
    // (node-index -> edge_list) the adjacency-list
    using adj_list = std::vector<edge_list>;

    class const_iterator {
      friend class Graph<N, E>;

    public:
      using index_type = Graph::index_type;
      using adj_list = Graph::adj_list;
      using edge_list = Graph::edge_list;

      struct value_type {
        friend class Graph<N, E>::const_iterator;
        value_type(const Graph &g, index_type a, index_type e) : gr_(g), a_(a), e_(e) {}

        const N &from(void) const { return gr_.nodeData(a_); }
        const N &to(void) const { return gr_.nodeData(gr_.adjl_[a_][e_].first); }
        const E &edge(void) const { return gr_.edgeData(gr_.adjl_[a_][e_].second); }

      private:
        const Graph &gr_;
        index_type a_, e_;
      };

      using reference = value_type &;
      using pointer = value_type *;

      bool operator==(const const_iterator &i) const {
        return ((vt_.a_ == i.vt_.a_) && (vt_.e_ == i.vt_.e_)) ? true : false;
      }

      bool operator!=(const const_iterator &i) const {
        return ((vt_.a_ == i.vt_.a_) && (vt_.e_ == i.vt_.e_)) ? false : true;
      }

      void operator++() {
        while (vt_.gr_.size() > vt_.a_) {
          index_type i = vt_.gr_.adjl_[vt_.a_].size();
          if (i > vt_.e_ + 1) {
            ++vt_.e_;
            return;
          }
          vt_.e_ = 0;
          ++vt_.a_;
          while (vt_.gr_.size() > vt_.a_) {
            if (!vt_.gr_.adjl_[vt_.a_].empty()) {
              return;
            }
            ++vt_.a_;
          }
        }
      }

      const value_type &operator*() const { return vt_; }

      const value_type *operator->() const { return &vt_; }

    private:
      explicit const_iterator(const Graph &g) : vt_(g, 0, 0) {}

      const_iterator(const Graph &g, index_type ait, index_type eit) : vt_(g, ait, eit) {}

      value_type vt_;

      bool operator<(const const_iterator &i) const { return (vt_.a_ < i.vt_.a_) && (vt_.e_ < i.vt_.e_); }

      bool operator>(const const_iterator &i) const { return (vt_.a_ > i.vt_.a_) && (vt_.e_ > i.vt_.e_); }
    };

    // Graphtypes

    struct value_type {
      value_type(const N &n, const E &e) : first(n), second(e) {}
      const N &first;
      const E &second;
      N firstToValue() const { return first; }
      E secondToValue() const { return second; }
    };

    // (node-index -> node)
    using node_list = std::vector<N>;
    using edge_store = std::vector<E>;

    // (node-index -> edge_list) the adjacency-list
    using adj_iterator = adj_list::iterator;
    using const_adj_iterator = adj_list::const_iterator;

    // assigns a node-index to the node
    using indexer_type = std::map<N, index_type>;
    using indexer_iterator = typename indexer_type::iterator;
    using const_indexer_iterator = typename indexer_type::const_iterator;

    // supported iterators and ranges
    using edge_iterator = edge_list::iterator;
    using const_edge_iterator = edge_list::const_iterator;
    using edge_range = std::pair<edge_iterator, edge_iterator>;
    using const_edge_range = std::pair<const_edge_iterator, const_edge_iterator>;
    using index_result = std::pair<index_type, bool>;

  public:
    // creation, deletion
    Graph() : edges_(1) {}
    ~Graph() {}

    // operations

    // O(log(n)), n...number of nodes
    index_type addNode(const N &);
    // O(log(n*e)), n,e...number of nodes,edges
    void addEdge(const N &from, const N &to, const E &edge);

    // O(1)
    //index_type addNode(const node_type &);
    // O(log(e))
    //index_type addEdge(const node_type & from, const node_type & to, const E & e);

    inline index_result nodeIndex(const N &) const;

    //index_type edgeIndex(const E &) const;

    // indexed edge_ranges, O(1) operation
    inline edge_range edges(index_type nodeIndex);
    inline const_edge_range edges(index_type nodeIndex) const;

    // indexed edge_ranges, O(log(n)) operation, n...number of nodes
    inline edge_range edges(const N &);
    inline const_edge_range edges(const N &) const;

    inline const N &nodeData(const edge_type &) const;
    inline const N &nodeData(index_type) const;
    inline const N &nodeData(const const_adj_iterator &) const;

    // replace oldNode by newNode O(log(n))
    bool replace(const N &oldNode, const N &newNode);

    //replace oldEdge by newEdge
    bool replaceEdge(const E &ldEdge, const E &newEdge);

    const E &edgeData(index_type i) const { return edges_[i]; }
    // const N & nodeData(const adj_iterator &) const;
    // index of a node (O(log(n))

    void clear();
    // access to the linear-iterator
    const_iterator begin_iter() const { return const_iterator(*this); }

    const_iterator end_iter() const { return const_iterator(*this, adjl_.size(), 0); }

    size_t edge_size() const { return edges_.size(); }

    // access to the adjacency-list
    adj_iterator begin() { return adjl_.begin(); }
    const_adj_iterator begin() const { return adjl_.begin(); }
    adj_iterator end() { return adjl_.end(); }
    const_adj_iterator end() const { return adjl_.end(); }
    auto size() const -> adj_list::size_type { return adjl_.size(); }

    // finds all roots of the Graph and puts them into the edge_list
    void findRoots(edge_list &) const;

    // inverts the directed Graph, i.e. edge(A,B) -> edge(B,A)
    void invert(Graph &g) const;

    void swap(Graph<N, E> &);

    // Data
  private:
    // adjacency list
    adj_list adjl_;

    // std::mapping of index to node
    node_list nodes_;

    // std::mapping of indes to edge
    edge_store edges_;

    // indexer for N and E
    indexer_type indexer_;  // eIndexer_;

    // dummy
    edge_list emptyEdges_;
  };

  template <class N, class E>
  typename Graph<N, E>::index_type Graph<N, E>::addNode(const N &node) {
    index_type idx = indexer_.size();  //  +1;
    std::pair<indexer_iterator, bool> result = indexer_.insert(typename indexer_type::value_type(node, idx));

    if (result.second) {  // new index!
      nodes_.emplace_back(node);
      adjl_.emplace_back(edge_list());
    } else {
      idx = result.first->second;
    }
    return idx;
  }

  template <class N, class E>
  typename Graph<N, E>::index_result Graph<N, E>::nodeIndex(const N &node) const {
    typename indexer_type::const_iterator result = indexer_.find(node);
    index_type idx = 0;
    bool flag = false;
    if (result != indexer_.end()) {
      flag = true;
      idx = result->second;
    }
    return index_result(idx, flag);
  }

  template <class N, class E>
  void Graph<N, E>::addEdge(const N &from, const N &to, const E &edge) {
    index_type iFrom = addNode(from);
    index_type iTo = addNode(to);

    adjl_[iFrom].emplace_back(edge_type(iTo, edges_.size()));
    edges_.emplace_back(edge);
  }

  template <class N, class E>
  typename Graph<N, E>::edge_range Graph<N, E>::edges(index_type nodeIndex) {
    edge_list &edges = adjl_[nodeIndex];
    return edge_range(edges.begin(), edges.end());
  }

  template <class N, class E>
  typename Graph<N, E>::const_edge_range Graph<N, E>::edges(index_type nodeIndex) const {
    const edge_list &edges = adjl_[nodeIndex];
    return const_edge_range(edges.begin(), edges.end());
  }

  template <class N, class E>
  typename Graph<N, E>::edge_range Graph<N, E>::edges(const N &node) {
    index_result idxResult = nodeIndex(node);
    edge_range result(emptyEdges_.begin(), emptyEdges_.end());
    if (idxResult.second) {
      result = edges(idxResult.first);
    }
    return result;
  }

  template <class N, class E>
  typename Graph<N, E>::const_edge_range Graph<N, E>::edges(const N &node) const {
    index_result idxResult = nodeIndex(node);
    const_edge_range result(emptyEdges_.begin(), emptyEdges_.end());
    if (idxResult.second) {
      result = edges(idxResult.first);
    }
    return result;
  }

  template <class N, class E>
  const N &Graph<N, E>::nodeData(const edge_type &edge) const {
    return nodes_[edge.first];
  }

  template <class N, class E>
  const N &Graph<N, E>::nodeData(index_type i) const {
    return nodes_[i];
  }

  template <class N, class E>
  const N &Graph<N, E>::nodeData(const const_adj_iterator &it) const {
    return nodes_[it - adjl_.begin()];
  }

  template <class N, class E>
  void Graph<N, E>::findRoots(edge_list &result) const {
    result.clear();

    const_adj_iterator it = begin();
    const_adj_iterator ed = end();
    std::vector<bool> rootCandidate(size(), true);

    for (; it != ed; ++it) {
      const edge_list &el = *it;
      for (auto const &el_it : el) {
        rootCandidate[el_it.first] = false;
      }
    }
    std::vector<bool>::size_type v_sz = 0;
    std::vector<bool>::size_type v_ed = rootCandidate.size();
    for (; v_sz < v_ed; ++v_sz) {
      if (rootCandidate[v_sz]) {
        result.emplace_back(edge_type(v_sz, 0));
      }
    }
  }

  template <class N, class E>
  bool Graph<N, E>::replace(const N &oldNode, const N &newNode) {
    typename indexer_type::iterator it = indexer_.find(oldNode);
    if (it != indexer_.end()) {
      index_type oldIndex = it->second;
      nodes_[oldIndex] = newNode;
      indexer_[newNode] = oldIndex;
      indexer_.erase(it);
    } else
      throw(oldNode);
    return true;
  }

  template <class N, class E>
  bool Graph<N, E>::replaceEdge(const E &oldEdge, const E &newEdge) {
    typename edge_store::size_type it = 0;
    typename edge_store::size_type ed = edges_.size();
    bool result = false;
    for (; it < ed; ++it) {
      if (edges_[it] == oldEdge) {
        result = true;
        edges_[it] = newEdge;
        break;
      }
    }
    return result;
  }

  template <class N, class E>
  void Graph<N, E>::clear() {
    adjl_.clear();
    nodes_.clear();
    edges_.clear();
    indexer_.clear();
  }

  template <class N, class E>
  void Graph<N, E>::invert(Graph<N, E> &g) const {
    adj_list::size_type it = 0;
    adj_list::size_type ed = adjl_.size();
    // loop over adjacency-list of this Graph
    for (; it < ed; ++it) {
      const edge_list &el = adjl_[it];
      edge_list::size_type eit = 0;
      edge_list::size_type eed = el.size();
      // loop over edges of current node
      for (; eit < eed; ++eit) {
        const edge_type &e = el[eit];
        g.addEdge(nodeData(e.first), nodeData(it), edgeData(e.second));
      }
    }
  }

  template <class N, class E>
  void Graph<N, E>::swap(Graph<N, E> &g) {
    adjl_.swap(g.adjl_);
    nodes_.swap(g.nodes_);
    edges_.swap(g.edges_);
    indexer_.swap(g.indexer_);
    emptyEdges_.swap(g.emptyEdges_);
  }

  template <typename T>
  std::ostream &operator<<(std::ostream &o, const std::vector<std::vector<std::pair<T, T> > > v) {
    typedef typename std::vector<std::vector<std::pair<T, T> > > v_t;
    typedef typename std::vector<std::pair<T, T> > i_t;

    typename v_t::const_iterator it(v.begin()), ed(v.end());
    for (; it != ed; ++it) {
      typename i_t::const_iterator iit(it->begin()), ied(it->end());
      for (; iit != ied; ++iit) {
        o << iit->first << ':' << iit->second << std::endl;
      }
    }
    return o;
  }

}  // namespace math

#endif