Math/interface/Graph.h

0001 #ifndef DATA_FORMATS_MATH_GRAPH_H
0002 #define DATA_FORMATS_MATH_GRAPH_H
0003
0004 #include <iostream>
0005 #include <map>
0006 #include <vector>
0007
0008 // Adjecencylist Graph
0009 namespace math {
0010
0011   // N,E must be concepts of default constructable, assignable, copyable, operator<
0012   template <class N, class E>
0013   class Graph {
0014   public:
0015     using index_type = std::vector<double>::size_type;
0016     // (node-index target, edge)
0017     using edge_type = std::pair<index_type, index_type>;
0018     // (std::vector of edge_types for the adj_list)
0019     using edge_list = std::vector<edge_type>;
0020     // (node-index -> edge_list) the adjacency-list
0021     using adj_list = std::vector<edge_list>;
0022
0023     class const_iterator {
0024       friend class Graph<N, E>;
0025
0026     public:
0027       using index_type = Graph::index_type;
0028       using adj_list = Graph::adj_list;
0029       using edge_list = Graph::edge_list;
0030
0031       struct value_type {
0032         friend class Graph<N, E>::const_iterator;
0033         value_type(const Graph &g, index_type a, index_type e) : gr_(g), a_(a), e_(e) {}
0034
0035         const N &from(void) const { return gr_.nodeData(a_); }
0036         const N &to(void) const { return gr_.nodeData(gr_.adjl_[a_][e_].first); }
0037         const E &edge(void) const { return gr_.edgeData(gr_.adjl_[a_][e_].second); }
0038
0039       private:
0040         const Graph &gr_;
0041         index_type a_, e_;
0042       };
0043
0044       using reference = value_type &;
0045       using pointer = value_type *;
0046
0047       bool operator==(const const_iterator &i) const {
0048         return ((vt_.a_ == i.vt_.a_) && (vt_.e_ == i.vt_.e_)) ? true : false;
0049       }
0050
0051       bool operator!=(const const_iterator &i) const {
0052         return ((vt_.a_ == i.vt_.a_) && (vt_.e_ == i.vt_.e_)) ? false : true;
0053       }
0054
0055       void operator++() {
0056         while (vt_.gr_.size() > vt_.a_) {
0057           index_type i = vt_.gr_.adjl_[vt_.a_].size();
0058           if (i > vt_.e_ + 1) {
0059             ++vt_.e_;
0060             return;
0061           }
0062           vt_.e_ = 0;
0063           ++vt_.a_;
0064           while (vt_.gr_.size() > vt_.a_) {
0065             if (!vt_.gr_.adjl_[vt_.a_].empty()) {
0066               return;
0067             }
0068             ++vt_.a_;
0069           }
0070         }
0071       }
0072
0073       const value_type &operator*() const { return vt_; }
0074
0075       const value_type *operator->() const { return &vt_; }
0076
0077     private:
0078       explicit const_iterator(const Graph &g) : vt_(g, 0, 0) {}
0079
0080       const_iterator(const Graph &g, index_type ait, index_type eit) : vt_(g, ait, eit) {}
0081
0082       value_type vt_;
0083
0084       bool operator<(const const_iterator &i) const { return (vt_.a_ < i.vt_.a_) && (vt_.e_ < i.vt_.e_); }
0085
0086       bool operator>(const const_iterator &i) const { return (vt_.a_ > i.vt_.a_) && (vt_.e_ > i.vt_.e_); }
0087     };
0088
0089     // Graphtypes
0090
0091     struct value_type {
0092       value_type(const N &n, const E &e) : first(n), second(e) {}
0093       const N &first;
0094       const E &second;
0095       N firstToValue() const { return first; }
0096       E secondToValue() const { return second; }
0097     };
0098
0099     // (node-index -> node)
0100     using node_list = std::vector<N>;
0101     using edge_store = std::vector<E>;
0102
0103     // (node-index -> edge_list) the adjacency-list
0104     using adj_iterator = adj_list::iterator;
0105     using const_adj_iterator = adj_list::const_iterator;
0106
0107     // assigns a node-index to the node
0108     using indexer_type = std::map<N, index_type>;
0109     using indexer_iterator = typename indexer_type::iterator;
0110     using const_indexer_iterator = typename indexer_type::const_iterator;
0111
0112     // supported iterators and ranges
0113     using edge_iterator = edge_list::iterator;
0114     using const_edge_iterator = edge_list::const_iterator;
0115     using edge_range = std::pair<edge_iterator, edge_iterator>;
0116     using const_edge_range = std::pair<const_edge_iterator, const_edge_iterator>;
0117     using index_result = std::pair<index_type, bool>;
0118
0119   public:
0120     // creation, deletion
0121     Graph() : edges_(1) {}
0122     ~Graph() {}
0123
0124     // operations
0125
0126     // O(log(n)), n...number of nodes
0127     index_type addNode(const N &);
0128     // O(log(n*e)), n,e...number of nodes,edges
0129     void addEdge(const N &from, const N &to, const E &edge);
0130
0131     // O(1)
0132     //index_type addNode(const node_type &);
0133     // O(log(e))
0134     //index_type addEdge(const node_type & from, const node_type & to, const E & e);
0135
0136     inline index_result nodeIndex(const N &) const;
0137
0138     //index_type edgeIndex(const E &) const;
0139
0140     // indexed edge_ranges, O(1) operation
0141     inline edge_range edges(index_type nodeIndex);
0142     inline const_edge_range edges(index_type nodeIndex) const;
0143
0144     // indexed edge_ranges, O(log(n)) operation, n...number of nodes
0145     inline edge_range edges(const N &);
0146     inline const_edge_range edges(const N &) const;
0147
0148     inline const N &nodeData(const edge_type &) const;
0149     inline const N &nodeData(index_type) const;
0150     inline const N &nodeData(const const_adj_iterator &) const;
0151
0152     // replace oldNode by newNode O(log(n))
0153     bool replace(const N &oldNode, const N &newNode);
0154
0155     //replace oldEdge by newEdge
0156     bool replaceEdge(const E &ldEdge, const E &newEdge);
0157
0158     const E &edgeData(index_type i) const { return edges_[i]; }
0159     // const N & nodeData(const adj_iterator &) const;
0160     // index of a node (O(log(n))
0161
0162     //! it clear everything!
0163     void clear();
0164     // access to the linear-iterator
0165     const_iterator begin_iter() const { return const_iterator(*this); }
0166
0167     const_iterator end_iter() const { return const_iterator(*this, adjl_.size(), 0); }
0168
0169     size_t edge_size() const { return edges_.size(); }
0170
0171     // access to the adjacency-list
0172     adj_iterator begin() { return adjl_.begin(); }
0173     const_adj_iterator begin() const { return adjl_.begin(); }
0174     adj_iterator end() { return adjl_.end(); }
0175     const_adj_iterator end() const { return adjl_.end(); }
0176     auto size() const -> adj_list::size_type { return adjl_.size(); }
0177
0178     // finds all roots of the Graph and puts them into the edge_list
0179     void findRoots(edge_list &) const;
0180
0181     // inverts the directed Graph, i.e. edge(A,B) -> edge(B,A)
0182     void invert(Graph &g) const;
0183
0184     void swap(Graph<N, E> &);
0185
0186     // Data
0187   private:
0188     // adjacency list
0189     adj_list adjl_;
0190
0191     // std::mapping of index to node
0192     node_list nodes_;
0193
0194     // std::mapping of indes to edge
0195     edge_store edges_;
0196
0197     // indexer for N and E
0198     indexer_type indexer_;  // eIndexer_;
0199
0200     // dummy
0201     edge_list emptyEdges_;
0202   };
0203
0204   template <class N, class E>
0205   typename Graph<N, E>::index_type Graph<N, E>::addNode(const N &node) {
0206     index_type idx = indexer_.size();  //  +1;
0207     std::pair<indexer_iterator, bool> result = indexer_.insert(typename indexer_type::value_type(node, idx));
0208
0209     if (result.second) {  // new index!
0210       nodes_.emplace_back(node);
0211       adjl_.emplace_back(edge_list());
0212     } else {
0213       idx = result.first->second;
0214     }
0215     return idx;
0216   }
0217
0218   template <class N, class E>
0219   typename Graph<N, E>::index_result Graph<N, E>::nodeIndex(const N &node) const {
0220     typename indexer_type::const_iterator result = indexer_.find(node);
0221     index_type idx = 0;
0222     bool flag = false;
0223     if (result != indexer_.end()) {
0224       flag = true;
0225       idx = result->second;
0226     }
0227     return index_result(idx, flag);
0228   }
0229
0230   template <class N, class E>
0231   void Graph<N, E>::addEdge(const N &from, const N &to, const E &edge) {
0232     index_type iFrom = addNode(from);
0233     index_type iTo = addNode(to);
0234
0235     adjl_[iFrom].emplace_back(edge_type(iTo, edges_.size()));
0236     edges_.emplace_back(edge);
0237   }
0238
0239   template <class N, class E>
0240   typename Graph<N, E>::edge_range Graph<N, E>::edges(index_type nodeIndex) {
0241     edge_list &edges = adjl_[nodeIndex];
0242     return edge_range(edges.begin(), edges.end());
0243   }
0244
0245   template <class N, class E>
0246   typename Graph<N, E>::const_edge_range Graph<N, E>::edges(index_type nodeIndex) const {
0247     const edge_list &edges = adjl_[nodeIndex];
0248     return const_edge_range(edges.begin(), edges.end());
0249   }
0250
0251   template <class N, class E>
0252   typename Graph<N, E>::edge_range Graph<N, E>::edges(const N &node) {
0253     index_result idxResult = nodeIndex(node);
0254     edge_range result(emptyEdges_.begin(), emptyEdges_.end());
0255     if (idxResult.second) {
0256       result = edges(idxResult.first);
0257     }
0258     return result;
0259   }
0260
0261   template <class N, class E>
0262   typename Graph<N, E>::const_edge_range Graph<N, E>::edges(const N &node) const {
0263     index_result idxResult = nodeIndex(node);
0264     const_edge_range result(emptyEdges_.begin(), emptyEdges_.end());
0265     if (idxResult.second) {
0266       result = edges(idxResult.first);
0267     }
0268     return result;
0269   }
0270
0271   template <class N, class E>
0272   const N &Graph<N, E>::nodeData(const edge_type &edge) const {
0273     return nodes_[edge.first];
0274   }
0275
0276   template <class N, class E>
0277   const N &Graph<N, E>::nodeData(index_type i) const {
0278     return nodes_[i];
0279   }
0280
0281   template <class N, class E>
0282   const N &Graph<N, E>::nodeData(const const_adj_iterator &it) const {
0283     return nodes_[it - adjl_.begin()];
0284   }
0285
0286   template <class N, class E>
0287   void Graph<N, E>::findRoots(edge_list &result) const {
0288     result.clear();
0289
0290     const_adj_iterator it = begin();
0291     const_adj_iterator ed = end();
0292     std::vector<bool> rootCandidate(size(), true);
0293
0294     for (; it != ed; ++it) {
0295       const edge_list &el = *it;
0296       for (auto const &el_it : el) {
0297         rootCandidate[el_it.first] = false;
0298       }
0299     }
0300     std::vector<bool>::size_type v_sz = 0;
0301     std::vector<bool>::size_type v_ed = rootCandidate.size();
0302     for (; v_sz < v_ed; ++v_sz) {
0303       if (rootCandidate[v_sz]) {
0304         result.emplace_back(edge_type(v_sz, 0));
0305       }
0306     }
0307   }
0308
0309   template <class N, class E>
0310   bool Graph<N, E>::replace(const N &oldNode, const N &newNode) {
0311     typename indexer_type::iterator it = indexer_.find(oldNode);
0312     if (it != indexer_.end()) {
0313       index_type oldIndex = it->second;
0314       nodes_[oldIndex] = newNode;
0315       indexer_[newNode] = oldIndex;
0316       indexer_.erase(it);
0317     } else
0318       throw(oldNode);
0319     return true;
0320   }
0321
0322   template <class N, class E>
0323   bool Graph<N, E>::replaceEdge(const E &oldEdge, const E &newEdge) {
0324     typename edge_store::size_type it = 0;
0325     typename edge_store::size_type ed = edges_.size();
0326     bool result = false;
0327     for (; it < ed; ++it) {
0328       if (edges_[it] == oldEdge) {
0329         result = true;
0330         edges_[it] = newEdge;
0331         break;
0332       }
0333     }
0334     return result;
0335   }
0336
0337   template <class N, class E>
0338   void Graph<N, E>::clear() {
0339     adjl_.clear();
0340     nodes_.clear();
0341     edges_.clear();
0342     indexer_.clear();
0343   }
0344
0345   template <class N, class E>
0346   void Graph<N, E>::invert(Graph<N, E> &g) const {
0347     adj_list::size_type it = 0;
0348     adj_list::size_type ed = adjl_.size();
0349     // loop over adjacency-list of this Graph
0350     for (; it < ed; ++it) {
0351       const edge_list &el = adjl_[it];
0352       edge_list::size_type eit = 0;
0353       edge_list::size_type eed = el.size();
0354       // loop over edges of current node
0355       for (; eit < eed; ++eit) {
0356         const edge_type &e = el[eit];
0357         g.addEdge(nodeData(e.first), nodeData(it), edgeData(e.second));
0358       }
0359     }
0360   }
0361
0362   template <class N, class E>
0363   void Graph<N, E>::swap(Graph<N, E> &g) {
0364     adjl_.swap(g.adjl_);
0365     nodes_.swap(g.nodes_);
0366     edges_.swap(g.edges_);
0367     indexer_.swap(g.indexer_);
0368     emptyEdges_.swap(g.emptyEdges_);
0369   }
0370
0371   template <typename T>
0372   std::ostream &operator<<(std::ostream &o, const std::vector<std::vector<std::pair<T, T> > > v) {
0373     typedef typename std::vector<std::vector<std::pair<T, T> > > v_t;
0374     typedef typename std::vector<std::pair<T, T> > i_t;
0375
0376     typename v_t::const_iterator it(v.begin()), ed(v.end());
0377     for (; it != ed; ++it) {
0378       typename i_t::const_iterator iit(it->begin()), ied(it->end());
0379       for (; iit != ied; ++iit) {
0380         o << iit->first << ':' << iit->second << std::endl;
0381       }
0382     }
0383     return o;
0384   }
0385
0386 }  // namespace math
0387
0388 #endif