A new frontier in large-scale graph analysis and data mining
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Pages
1 #ifndef __FGLIB_H__
2 #define __FGLIB_H__
4 /*
5  * Copyright 2014 Open Connectome Project (http://openconnecto.me)
6  * Written by Da Zheng (zhengda1936@gmail.com)
7  *
8  * This file is part of FlashGraph.
9  *
10  * Licensed under the Apache License, Version 2.0 (the "License");
11  * you may not use this file except in compliance with the License.
12  * You may obtain a copy of the License at
13  *
14  * http://www.apache.org/licenses/LICENSE-2.0
15  *
16  * Unless required by applicable law or agreed to in writing, software
17  * distributed under the License is distributed on an "AS IS" BASIS,
18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
19  * See the License for the specific language governing permissions and
20  * limitations under the License.
21  */
23 #include "graph_engine.h"
24 #include "graph.h"
25 #include "FG_vector.h"
26 #include "graph_file_header.h"
28 namespace safs
29 {
30  class file_io_factory;
31 };
33 namespace fg
34 {
42 class FG_graph
43 {
44  graph_header header;
45  std::string graph_file;
46  std::string index_file;
47  std::shared_ptr<in_mem_graph> graph_data;
48  std::shared_ptr<vertex_index> index_data;
49  config_map::ptr configs;
51  FG_graph(const std::string &graph_file,
52  const std::string &index_file, config_map::ptr configs);
53  FG_graph(std::shared_ptr<in_mem_graph> graph_data,
54  std::shared_ptr<vertex_index> index_data,
55  const std::string &graph_name, config_map::ptr configs);
56 public:
57  typedef std::shared_ptr<FG_graph> ptr;
60  graph_engine::destroy_flash_graph();
61  }
72  static ptr create(const std::string &graph_file,
73  const std::string &index_file, config_map::ptr configs) {
74  return ptr(new FG_graph(graph_file, index_file, configs));
75  }
86  static ptr create(std::shared_ptr<in_mem_graph> graph_data,
87  std::shared_ptr<vertex_index> index_data,
88  const std::string &graph_name, config_map::ptr configs) {
89  return ptr(new FG_graph(graph_data, index_data, graph_name, configs));
90  }
92  std::shared_ptr<safs::file_io_factory> get_graph_io_factory(int access_option);
101  config_map::ptr get_configs() const {
102  return configs;
103  }
105  bool is_in_mem() const {
106  return graph_data != NULL;
107  }
109  std::shared_ptr<in_mem_graph> get_graph_data() const {
110  return graph_data;
111  }
113  std::shared_ptr<vertex_index> get_index_data() const;
115  graph_engine::ptr create_engine(graph_index::ptr index);
122  return header;
123  }
124 };
146 {
147  CYCLE,
148  ALL,
149 };
151 FG_vector<vertex_id_t>::ptr compute_cc(FG_graph::ptr fg);
160 FG_vector<vertex_id_t>::ptr compute_wcc(FG_graph::ptr fg);
170 FG_vector<vertex_id_t>::ptr compute_sync_wcc(FG_graph::ptr fg);
182 FG_vector<vertex_id_t>::ptr compute_ts_wcc(FG_graph::ptr fg,
183  time_t start_time, time_t time_interval);
192 FG_vector<vertex_id_t>::ptr compute_scc(FG_graph::ptr fg);
204 FG_vector<size_t>::ptr compute_directed_triangles(FG_graph::ptr fg,
206 FG_vector<size_t>::ptr compute_directed_triangles_fast(FG_graph::ptr fg,
216 FG_vector<size_t>::ptr compute_undirected_triangles(FG_graph::ptr fg);
225 FG_vector<size_t>::ptr compute_local_scan(FG_graph::ptr);
226 FG_vector<size_t>::ptr compute_local_scan2(FG_graph::ptr fg);
237 FG_vector<std::pair<vertex_id_t, size_t> >::ptr compute_topK_scan(
238  FG_graph::ptr, size_t topK);
246 size_t estimate_diameter(FG_graph::ptr fg, int num_bfs, bool directed);
261 FG_vector<float>::ptr compute_pagerank(FG_graph::ptr fg, int num_iters,
262  float damping_factor);
277 FG_vector<float>::ptr compute_pagerank2(FG_graph::ptr, int num_iters,
278  float damping_factor);
280 FG_vector<float>::ptr compute_sstsg(FG_graph::ptr fg, time_t start_time,
281  time_t interval, int num_intervals);
290 in_mem_subgraph::ptr fetch_subgraph(FG_graph::ptr graph,
291  const std::vector<vertex_id_t> &vertices);
305 FG_vector<size_t>::ptr compute_kcore(FG_graph::ptr fg,
306  size_t k, size_t kmax=0);
314 FG_vector<vsize_t>::ptr get_degree(FG_graph::ptr fg, edge_type type);
323 FG_vector<float>::ptr compute_transitivity(FG_graph::ptr fg);
333 FG_vector<float>::ptr compute_betweenness_centrality(FG_graph::ptr fg,
334  const std::vector<vertex_id_t>& vids);
345 FG_vector<vsize_t>::ptr get_ts_degree(FG_graph::ptr fg, edge_type type,
346  time_t start_time, time_t time_interval);
354 std::pair<time_t, time_t> get_time_range(FG_graph::ptr fg);
362 void compute_overlap(FG_graph::ptr fg, const std::vector<vertex_id_t> &vids,
363  std::vector<std::vector<double> > &overlap_matrix);
370 FG_vector<float>::ptr compute_transitivity(FG_graph::ptr fg);
377 void compute_louvain(FG_graph::ptr fg, const uint32_t levels);
378 }
379 #endif
FG_vector< vsize_t >::ptr get_ts_degree(FG_graph::ptr fg, edge_type type, time_t start_time, time_t time_interval)
Get the degree of all vertices in a specified time interval in a time-series graph.
Definition: io_interface.h:428
void compute_overlap(FG_graph::ptr fg, const std::vector< vertex_id_t > &vids, std::vector< std::vector< double > > &overlap_matrix)
Get the neighborhood overlap of each pair of vertices in `vids'.
FG_vector< vertex_id_t >::ptr compute_scc(FG_graph::ptr fg)
Compute all strongly connected components of a graph.
FG_vector< float >::ptr compute_transitivity(FG_graph::ptr fg)
Compute the transitivity/clustering coefficient of a graph.
void compute_louvain(FG_graph::ptr fg, const uint32_t levels)
Compute louvain clustering for a graph.
FG_vector< size_t >::ptr compute_kcore(FG_graph::ptr fg, size_t k, size_t kmax=0)
Compute the k-core/coreness of a graph. The algorithm will determine which vertices are between core ...
size_t estimate_diameter(FG_graph::ptr fg, int num_bfs, bool directed)
Compute the diameter estimation for a graph.
std::pair< time_t, time_t > get_time_range(FG_graph::ptr fg)
Get the time range in which the time-series graph is.
Triangle computation type.
Definition: FGlib.h:145
FG_vector< vertex_id_t >::ptr compute_sync_wcc(FG_graph::ptr fg)
Compute all weakly connectected components of a graph synchronously. The reason of having this implem...
Edge type of an edge in the graph.
Definition: vertex.h:43
in_mem_subgraph::ptr fetch_subgraph(FG_graph::ptr graph, const std::vector< vertex_id_t > &vertices)
Fetch the clusters with the wanted cluster IDs.
FG_vector< std::pair< vertex_id_t, size_t > >::ptr compute_topK_scan(FG_graph::ptr, size_t topK)
Obtain the top K vertices with the largest local Scan Statistic value.
FG_vector< size_t >::ptr compute_directed_triangles(FG_graph::ptr fg, directed_triangle_type type)
Compute the directed triangle count for each each vertex. Currently, it only counts the number of cyc...
FG_vector< vsize_t >::ptr get_degree(FG_graph::ptr fg, edge_type type)
Get the degree of all vertices in the graph.
FG_vector< vertex_id_t >::ptr compute_ts_wcc(FG_graph::ptr fg, time_t start_time, time_t time_interval)
Compute all weakly connectected components of a time-series graph in a specified time interval...
Definition: graph_file_header.h:58
FG_vector< float >::ptr compute_betweenness_centrality(FG_graph::ptr fg, const std::vector< vertex_id_t > &vids)
Compute the betweeenness centrality of a graph.
static ptr create(std::shared_ptr< in_mem_graph > graph_data, std::shared_ptr< vertex_index > index_data, const std::string &graph_name, config_map::ptr configs)
Method to instantiate a graph object. This method is used in lieu of explicitly calling a ctor...
Definition: FGlib.h:86
FG_vector< float >::ptr compute_pagerank2(FG_graph::ptr, int num_iters, float damping_factor)
Compute the PageRank of a graph using the push method where vertices send deltas of their PageRank to...
const graph_header & get_graph_header()
Get the header of the graph that contains basic information of the graph.
Definition: FGlib.h:121
Definition: FGlib.h:59
FG_vector< vertex_id_t >::ptr compute_wcc(FG_graph::ptr fg)
Compute all weakly connectected components of a graph.
config_map::ptr get_configs() const
Get the map that contains the runtime configurations for FlashGraph.
Definition: FGlib.h:101
FG_vector< float >::ptr compute_pagerank(FG_graph::ptr fg, int num_iters, float damping_factor)
Compute the PageRank of a graph using the pull method where vertices request the data from all their ...
A user-friendly wrapper for FlashGraph's raw graph type. Very usefule when when utilizing FlashGraph ...
Definition: FGlib.h:42
FG_vector< size_t >::ptr compute_local_scan(FG_graph::ptr)
Compute the per-vertex local Scan Statistic.
static ptr create(const std::string &graph_file, const std::string &index_file, config_map::ptr configs)
Method to instantiate a graph object. This method is used in lieu of explicitly calling a ctor...
Definition: FGlib.h:72
FG_vector< size_t >::ptr compute_undirected_triangles(FG_graph::ptr fg)
Compute undirected triangle count for each vertex.