23 #ifndef GRAPHLAB_LOCAL_GRAPH_HPP
24 #define GRAPHLAB_LOCAL_GRAPH_HPP
40 #include <boost/bind.hpp>
41 #include <boost/unordered_set.hpp>
42 #include <boost/type_traits.hpp>
43 #include <boost/typeof/typeof.hpp>
44 #include <boost/iterator/transform_iterator.hpp>
46 #include <graphlab/graph/graph_basic_types.hpp>
49 #include <graphlab/logger/assertions.hpp>
51 #include <graphlab/serialization/iarchive.hpp>
52 #include <graphlab/serialization/oarchive.hpp>
54 #include <graphlab/util/random.hpp>
55 #include <graphlab/graph/graph_storage.hpp>
56 #include <graphlab/macros_def.hpp>
63 template<
typename VertexData,
typename EdgeData>
66 template<
typename VertexData,
typename EdgeData>
72 typedef graph_storage<VertexData, EdgeData> gstore_type;
76 typedef VertexData vertex_data_type;
79 typedef EdgeData edge_data_type;
81 typedef typename gstore_type::edge_info edge_info;
86 friend class json_parser<VertexData, EdgeData>;
91 struct edge_list_type;
97 local_graph& lgraph_ref;
98 typename gstore_type::edge_type e;
99 edge_type(local_graph& lgraph_ref,
100 typename gstore_type::edge_type e) :
101 lgraph_ref(lgraph_ref),e(e) { }
104 const edge_data_type&
data()
const {
105 return lgraph_ref.gstore.edge_data(e);
109 return lgraph_ref.gstore.edge_data(e);
121 edge_id_type
id()
const {
122 return lgraph_ref.gstore.edge_id(e);
130 local_graph& lgraph_ref;
132 vertex_type(local_graph& lgraph_ref,
lvid_type vid):lgraph_ref(lgraph_ref),vid(vid) { }
135 const vertex_data_type&
data()
const {
136 return lgraph_ref.vertex_data(vid);
140 return lgraph_ref.vertex_data(vid);
144 return lgraph_ref.num_in_edges(vid);
148 return lgraph_ref.num_out_edges(vid);
156 return edge_list_type(lgraph_ref, lgraph_ref.gstore.in_edges(vid));
160 return edge_list_type(lgraph_ref, lgraph_ref.gstore.out_edges(vid));
164 struct make_edge_type_functor {
165 typedef typename gstore_type::edge_type argument_type;
166 typedef edge_type result_type;
167 local_graph& lgraph_ref;
168 make_edge_type_functor(local_graph& lgraph_ref):lgraph_ref(lgraph_ref) { }
169 result_type operator() (
const argument_type et)
const {
170 return edge_type(lgraph_ref, et);
175 struct edge_list_type {
176 make_edge_type_functor me_functor;
177 typename gstore_type::edge_list elist;
178 typedef boost::transform_iterator<make_edge_type_functor, typename gstore_type::edge_list::iterator> iterator;
179 typedef iterator const_iterator;
181 edge_list_type(local_graph& lgraph_ref,
typename gstore_type::edge_list elist): me_functor(lgraph_ref), elist(elist) { }
183 size_t size()
const {
return elist.size(); }
188 boost::make_transform_iterator(elist.begin(), me_functor); }
190 iterator
end()
const {
return
191 boost::make_transform_iterator(elist.end(), me_functor); }
192 bool empty()
const {
return elist.empty(); }
203 local_graph() : finalized(false) { }
206 local_graph(
size_t nverts) :
225 void clear_reserve() {
228 std::vector<VertexData>().swap(vertices);
229 gstore.clear_reserve();
242 if(finalized)
return;
244 gstore.finalize(vertices.size(), edges_tmp);
246 <<
" secs" << std::endl;
251 size_t num_vertices()
const {
252 return vertices.size();
256 size_t local_vertices()
const {
257 return vertices.size();
261 size_t num_edges()
const {
263 return gstore.edge_size();
265 return edges_tmp.size();
272 return gstore.find(source, target);
276 edge_type reverse_edge(
const edge_type& edge)
const {
277 return gstore.find(edge.target(), edge.source());
287 const VertexData& vdata = VertexData() ) {
291 if(vid >= vertices.size()) {
293 if(vid >= vertices.capacity()) {
294 const size_t new_size = std::max(2 * vertices.capacity(),
296 vertices.reserve(new_size);
298 vertices.resize(vid+1);
300 vertices[vid] = vdata;
303 void reserve(
size_t num_vertices) {
304 ASSERT_GE(num_vertices, vertices.size());
305 vertices.reserve(num_vertices);
312 void resize(
size_t num_vertices ) {
313 ASSERT_GE(num_vertices, vertices.size());
314 vertices.resize(num_vertices);
317 void reserve_edge_space(
size_t n) {
318 edges_tmp.reserve_edge_space(n);
325 const EdgeData& edata = EdgeData()) {
328 <<
"Attempting add edge to a finalized local_graph." << std::endl;
329 ASSERT_MSG(
false,
"Add edge to a finalized local_graph.");
332 if(source == target) {
334 <<
"Attempting to add self edge (" << source <<
" -> " << target <<
"). "
335 <<
"This operation is not permitted in GraphLab!" << std::endl;
336 ASSERT_MSG(source != target,
"Attempting to add self edge!");
339 if(source >= vertices.size() || target >= vertices.size())
340 add_vertex(std::max(source, target));
343 edges_tmp.add_edge(source, target, edata);
352 void add_edges(
const std::vector<lvid_type>& src_arr,
353 const std::vector<lvid_type>& dst_arr,
354 const std::vector<EdgeData>& edata_arr) {
355 ASSERT_TRUE((src_arr.size() == dst_arr.size())
356 && (src_arr.size() == edata_arr.size()));
359 <<
"Attempting add edges to a finalized local_graph." << std::endl;
362 for (
size_t i = 0; i < src_arr.size(); ++i) {
365 if ( source >= vertices.size()
366 || target >= vertices.size() ) {
368 <<
"Attempting add_edge (" << source
370 <<
") when there are only " << vertices.size()
371 <<
" vertices" << std::endl;
372 ASSERT_MSG(source < vertices.size(),
"Invalid source vertex!");
373 ASSERT_MSG(target < vertices.size(),
"Invalid target vertex!");
376 if(source == target) {
378 <<
"Attempting to add self edge (" << source <<
" -> " << target <<
"). "
379 <<
"This operation is not permitted in GraphLab!" << std::endl;
380 ASSERT_MSG(source != target,
"Attempting to add self edge!");
383 edges_tmp.add_block_edges(src_arr, dst_arr, edata_arr);
389 ASSERT_LT(vid, vertices.size());
390 return vertex_type(*
this, vid);
394 const vertex_type vertex(
lvid_type vid)
const {
395 ASSERT_LT(vid, vertices.size());
396 return vertex_type(*
this, vid);
401 ASSERT_LT(v, vertices.size());
406 const VertexData& vertex_data(
lvid_type v)
const {
407 ASSERT_LT(v, vertices.size());
413 ASSERT_TRUE(finalized);
414 return gstore.edge_data(source, target);
420 ASSERT_TRUE(finalized);
421 return gstore.edge_data(source, target);
425 EdgeData& edge_data(
const edge_type& edge) {
426 ASSERT_TRUE(finalized);
427 return gstore.edge_data(edge.e);
430 const EdgeData& edge_data(
const edge_type& edge)
const {
431 ASSERT_TRUE(finalized);
432 return gstore.edge_data(edge.e);
438 void load(iarchive& arc) {
447 void save(oarchive& arc)
const {
455 void swap(local_graph& other) {
456 std::swap(vertices, other.vertices);
457 std::swap(gstore, other.gstore);
458 std::swap(finalized, other.finalized);
463 void load(
const std::string& filename) {
464 std::ifstream fin(filename.c_str());
475 void save(
const std::string& filename)
const {
476 std::ofstream fout(filename.c_str());
492 void save_adjacency(
const std::string& filename)
const {
493 std::ofstream fout(filename.c_str());
494 ASSERT_TRUE(fout.good());
495 for(
size_t i = 0; i < num_edges(); ++i) {
496 fout << gstore.source(i) <<
", " << gstore.target(i) <<
"\n";
497 ASSERT_TRUE(fout.good());
512 return gstore.edge_id(edge.e);
518 size_t num_in_edges(
const lvid_type v)
const {
519 ASSERT_TRUE(finalized);
520 return gstore.num_in_edges(v);
526 size_t num_out_edges(
const lvid_type v)
const {
527 ASSERT_TRUE(finalized);
528 return gstore.num_out_edges(v);
535 return edge_list_type(*
this, gstore.in_edges(v));
542 return edge_list_type(*
this, gstore.out_edges(v));
548 size_t estimate_sizeof()
const {
549 const size_t vlist_size =
sizeof(vertices) +
550 sizeof(VertexData) * vertices.capacity();
551 size_t elist_size = edges_tmp.estimate_sizeof();
552 size_t store_size = gstore.estimate_sizeof();
557 return store_size + vlist_size + elist_size;
563 const std::vector<lvid_type>& get_out_index_storage()
const {
564 return gstore.get_csr_src();
570 const std::vector<lvid_type>& get_in_index_storage()
const {
571 return gstore.get_csc_dst();
577 const std::vector<lvid_type>& get_out_edge_storage()
const {
578 return gstore.get_csr_dst();
585 const std::vector<lvid_type>& get_in_edge_storage()
const {
586 return gstore.get_csc_src();
592 const std::vector<EdgeData> & get_edge_data_storage()
const {
593 return gstore.get_edge_data();
600 if (edges_tmp.size()) {
602 foreach(
lvid_type i, edges_tmp.source_arr)
603 max = std::max(max, i);
604 foreach(
lvid_type i, edges_tmp.target_arr)
605 max = std::max(max, i);
618 std::vector<VertexData> vertices;
637 template<
typename VertexData,
typename EdgeData>
638 std::ostream& operator<<(std::ostream& out,
639 const local_graph<VertexData, EdgeData>& local_graph) {
640 for(
lvid_type vid = 0; vid < local_graph.num_vertices(); ++vid) {
641 foreach(
edge_id_type eid, local_graph.out_edge_ids(vid))
642 out << vid <<
", " << local_graph.target(eid) <<
'\n';
653 template<
typename VertexData,
typename EdgeData>
654 inline void swap(graphlab::local_graph<VertexData,EdgeData>& a,
655 graphlab::local_graph<VertexData,EdgeData>& b) {
661 #include <graphlab/macros_undef.hpp>