#include <string>
#include <vector>
#include "graphchi_basic_includes.hpp"
#include "engine/dynamic_graphs/graphchi_dynamicgraph_engine.hpp"
Classes | |
struct | dense_adj |
class | adjlist_container |
struct | TriangleCountingProgram |
Macros | |
#define | SUPPORT_DELETIONS 1 |
Typedefs | |
typedef uint32_t | VertexDataType |
typedef uint32_t | EdgeDataType |
Functions | |
bool | findadj_linear (vid_t *datachunk, size_t n, vid_t target) |
bool | findadj (vid_t *datachunk, size_t n, vid_t target) |
int | main (int argc, const char **argv) |
Variables | |
int | grabbed_edges = 0 |
adjlist_container * | adjcontainer |
Copyright [2012] [Aapo Kyrola, Guy Blelloch, Carlos Guestrin / Carnegie Mellon University]
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
Triangle counting application. Counts the number of incident (full) triangles for each vertex. Edge direction is ignored.
This algorithm is quite complicated and requires 'trickery' to work well on GraphChi. The complexity stems from the need to store large number of adjacency lists in memory: we cannot store the adjacency lists reasonable to edges, nor can we store all of them once at memory. Therefore the problems is solved in a series of phases. On each phase, the relevant adjacency lists of an interval of vertices (called 'pivots') is loaded into memory, and all vertices that have id smaller than the pivots are matched with them. With 'relevant adjacency list' I mean the list of neighbors that have higher id then the pivots themselves. That is, we only count triangles a -> b -> c where a > b > c.
The application involves a special preprocessing step which orders the vertices in ascending order of their degree. This turns out to be a very important optimization on big graphs.
This algorithm also utilizes the dynamic graph engine, and deletes edges after they have been accounted for.
#define SUPPORT_DELETIONS 1 |
Need to define prior to including GraphChi headers. This enabled edge-deletion in the vertex object.
typedef uint32_t VertexDataType |
Type definitions. Vertex data stores the number of incident triangles. Edge stores number of unaccounted triangles that the edge participates on. When vertex is updated, it updates its vertex count by summing up the counts from edges (after which the edges are deleted).
int grabbed_edges = 0 |
Code for intersection size computation and pivot management.