dgraph_edge_list.hpp

00001 /*
00002 This file is part of GraphLab.
00003 
00004 GraphLab is free software: you can redistribute it and/or modify
00005 it under the terms of the GNU Lesser General Public License as 
00006 published by the Free Software Foundation, either version 3 of 
00007 the License, or (at your option) any later version.
00008 
00009 GraphLab is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 GNU Lesser General Public License for more details.
00013 
00014 You should have received a copy of the GNU Lesser General Public 
00015 License along with GraphLab.  If not, see <http://www.gnu.org/licenses/>.
00016 */
00017 
00018 #ifndef GRAPHLAB_DISTRIBUTED_DGRAPH_EDGE_LIST_HPP
00019 #define GRAPHLAB_DISTRIBUTED_DGRAPH_EDGE_LIST_HPP
00020 #include <vector>
00021 #include <algorithm>
00022 #include <boost/function.hpp>
00023 #include <boost/bind.hpp>
00024 #include <boost/iterator/transform_iterator.hpp>
00025 #include <boost/unordered_map.hpp>
00026 #include <graphlab/graph/graph.hpp>
00027 
00028 #include <graphlab/macros_def.hpp>
00029 namespace graphlab {
00030 
00031 namespace dgraph_elist_impl {
00032   
00033 edge_id_t eid_identity(edge_id_t eid);
00034 
00035 }
00036 
00037 
00038   /** This class defines a set of edges */
00039 class dgraph_edge_list {
00040 public:
00041   typedef boost::function<edge_id_t (edge_id_t)> TransformType;
00042   typedef boost::transform_iterator<TransformType, const edge_id_t*> iterator;
00043   typedef boost::transform_iterator<TransformType, const edge_id_t*> const_iterator;
00044   typedef edge_id_t value_type;
00045 private:
00046   // this class can wrap two methods of describing an edge list
00047   // method 1: a regular edge_list which requires some conversion
00048   // method 2: a vector
00049 
00050   // method 1:
00051   edge_list elist;
00052   // method 2:
00053   std::vector<edge_id_t> edgeidvec;
00054   size_t numel;
00055   bool useelist;
00056   
00057 public:
00058 
00059 
00060   // an edge list which wraps a regular elist. Method 1.
00061   inline dgraph_edge_list(edge_list elist)
00062                               :elist(elist), numel(elist.size()), useelist(true){ }
00063 
00064   // an edge list which wraps a vector. Method 2.
00065   inline dgraph_edge_list(const std::vector<edge_id_t> &edgeidvec) :
00066                           edgeidvec(edgeidvec), numel(edgeidvec.size()), useelist(false) { }
00067 
00068   /** \brief Get the size of the edge list */
00069   inline size_t size() const { return numel; }
00070 
00071   /** \brief Get the ith edge in the edge list */
00072   inline edge_id_t operator[](size_t i) const {
00073     assert(i < size());
00074     return *(begin() + i);
00075   }
00076 
00077   /** \brief Returns a pointer to the start of the edge list */
00078   inline iterator begin() const {
00079     if (useelist) {
00080       return boost::make_transform_iterator(elist.begin(),
00081                                             dgraph_elist_impl::eid_identity);
00082 
00083     }
00084     else {
00085       return boost::make_transform_iterator(&(edgeidvec[0]),
00086                                       dgraph_elist_impl::eid_identity);
00087     }
00088   }
00089 
00090   /** \brief Returns a pointer to the end of the edge list */
00091   inline iterator end() const {
00092     if (useelist) {
00093       return boost::make_transform_iterator(elist.end(),
00094                                              dgraph_elist_impl::eid_identity);
00095 
00096     }
00097     else {
00098       return boost::make_transform_iterator(&(edgeidvec[edgeidvec.size()]),
00099                                              dgraph_elist_impl::eid_identity);
00100 
00101     }
00102   }
00103 
00104   /** \brief Fill a vector with edge id list */
00105   inline void fill_vector(std::vector<edge_id_t>& lvalue) const {
00106     lvalue.clear();
00107     foreach(edge_id_t eid, *this) lvalue.push_back(eid);
00108   }
00109 
00110   /** \brief test if the edge list is empty */
00111   inline bool empty() const { return size() == 0; }
00112 };
00113 
00114 }
00115 #include <graphlab/macros_undef.hpp>
00116 #endif
00117