GraphChi  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Macros
Classes | Macros | Typedefs | Functions | Variables
trianglecounting.cpp File Reference
#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_containeradjcontainer

Detailed Description

Author:
Aapo Kyrola akyro.nosp@m.la@c.nosp@m.s.cmu.nosp@m..edu
Version:
1.0

LICENSE

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.

DESCRIPTION

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.


Macro Definition Documentation

#define SUPPORT_DELETIONS   1

Need to define prior to including GraphChi headers. This enabled edge-deletion in the vertex object.


Typedef Documentation

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).


Variable Documentation

int grabbed_edges = 0

Code for intersection size computation and pivot management.