Skip to content

huyang1988/TC

Repository files navigation

TC

Preprocess from SNAP data

Data Formats

SNAP

A SNAP dataset http://snap.stanford.edu/ is a text file that each line is an edge with source and destination vertex IDs, such as
11 25

CSR

A CSR data generally contains two lists, the begin position array which represents the offsets of the neighbor lists by source vertex ID, and the adjacency list which stores destination vertices of all edges.

adjacent.bin
begin.bin
head.bin
edge

converter

The codes are in the folder below.

TC/graph_converter/undirected_csr/
./tuple_to_undirected_csr.bin input

It automatically generates CSR files adjacent.bin, head.bin and begin.bin to current path. Each line in SNAP file (e.g., 0,1) generates two edges (0,1) and (1,0). The converted files are bit files. The begin position file begin.bin represents the offsets of each neighbor lists in both head.bin and adjacent.bin. The neighbor lists are not sorted.

cleaner

The codes are in the folder below.

TC/graph_cleaner/
./graph_cleane.bin input_path

The cleaner sorts all neighbor lists, removes self-loop and multiple edges. After this step, the graph is an undirected graph in CSR format (both directions of each edge is stored in the CSR). The output files are written to current folder, so to copy the executable to target folder is suggested.

rank_by_degree

./rank_by_degree.bin input_path

The rank_by_degree orientation tool removes half of all edges. It only keeps the edges from lower degree vertex to higher degree vertex. After this step, the graph is an undirected graph in CSR format. The output files are written to current folder, so to copy the executable to target folder is suggested.

Partition

The codes are in the folder below.

TC/TC-EXT/partitioner-x/
./partition-x input_path

The partitioner tool partition the graph in a 2-D fashion. The rule is described in paper It only keeps the edges from lower degree vertex to higher degree vertex. After this step, the graph is an undirected graph in CSR format. The output files are written to current folder, so to copy the executable to target folder is suggested.

Triangle counting

GPU in-memory

The path of in-memory GPU triangle counting is TC/TC-GPU/work-steal/. Run the code with command ./tc <input_path>.

CPU in-memory

The path of in-memory CPU triangle counting is TC/TC-CPU/tc-ne-cpu/. Run the code with command ./tc <input_path>.

GPU on 2d partitioned data

CPU on 2d partitioned data

Graph Challenge Example Dataset and Toolkit

The dataset path is TC/example_dataset/amazon0302/, the _adj.mmio is the original data format downloaded from https://graphchallenge.mit.edu/data-sets. Converter tool source code is in TC/gConv/, copy the executable to dataset path, line 8 of the bash script converter.sh needs to be modified (set the number to (#vertex+1), the vertex count can be found by less <input>_adj.mmio). Run the bash script with command ./converter.sh <input>_adj.mmio (replace the input name, for example, amazon0302).

About

No description, website, or topics provided.

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published