Unzipping "trilist.zip" will give you our program "trilist" and a list of 
folders to be used by the program. 

The program was compiled under Ubuntu 12.04 (64-bit) using GCC 4.6.3.


======================================================================
Command Line Usage
======================================================================

trilist input_graph algo_name memory(bytes) [output_file] 

- "input_graph": path to the file of the input graph

- algo_names: name of the algorithm, which can be:

  # dgp - deterministic graph partitioning
  # emcf - external memory compact forward
  # emni - external memory node iterator
  # mgt - massive gragh triangulation (our algorithm)
  # rgp - randomized graph partitioning

- The 3rd argument states the maximum amount of memory that the
program can use (in bytes).

- The 4th argument "output_file" is optional. If not specified, the
program simply counts the number of triangles in the graph;
otherwise, the program writes all triangles to that file.

The program stores temporary files and the final output in 
"./tl_disk/algo_name/". For example, when running our MGT algorithm, the 
files will be written into "./tl_disk/mgt/". Leave the folder empty 
before running the algorithm.


======================================================================
Sample Dataset
======================================================================

There is a sample dataset named "minimal" in the "./dataset" folder. The 
following command line will list all the triangles in this graph using 
our MGT algorithm and 1MB memory, and write output file
"tl_disk/mgt/minimal.out":

./trilist datasets/minimal mgt 1048576 minimal.out


======================================================================
Data Format
======================================================================

The program accepts an undirected simple graph without isolated 
vertices (i.e., vertices with no edges). There should be two files
for the graph:

- a ".deg" file storing the vertex degrees, and
- a ".adj" file storing the neighbors of each vertex.

As an example, consider a graph with n vertices and m edges, where
the vertices are numbered as 0, 1, ..., n - 1. Let d(i) be the degree of
vertex i, and N(i) be a list (sorted by vertex id) of the neighbors of
vertex i. Then:

- the ".deg" file consecutively stores n pairs of integers (i, d(i)),
namely, (0, d(0)), (1, d(1)), ..., (n-1, d(n-1)). Each integer should
be stored in binary (little endian), and occupies 32 bits. So the 
".deg" file has in total 8n bytes.

- the ".adj" files consecutively stores the neighbors of the n
vertices. It stores first N(0) as d(0) 32-bit integers, then N(1), and
so on. So the ".adj" file should contain 2m integers, i.e., 8m bytes.

For example, file "datasets/minimal.deg" stores the following list of
integers (in binary format):

0 1 1 1

and "datasets/minimal.adj" stores:

1 0

Together, the two files describe a graph with 2 nodes and 1 edge
between them.

======================================================================
Output Format
======================================================================

The output file is also in the binary format. Each triangle occupies 12
bytes, specifying its 3 vertices each as a 32-bit integer.