BFS README¶
## Generate edge list using a R-MAT generator ``` ./rmat_edge_generator/generate_edge_list
-o [out edge list file name (required)]
-s [seed for random number generator; default is 123]
-v [SCALE; The logarithm base two of the number of vertices; default is 17]
-e [#of edges; default is 2^{SCALE} x 16]
-a [initiator parameter A; default is 0.57]
-b [initiator parameter B; default is 0.19]
-c [initiator parameter C; default is 0.19]
-r [if true, scrambles edge IDs; default is true]
-u [if true, generates edges for the both direction; default is true] ```
- As for the initiator parameters,
see [Graph500, 3.2 Detailed Text Description](https://graph500.org/?page_id=12#sec-3_2) for more details.
#### Generate Graph 500 inputs
`
./generate_edge_list -o /mnt/ssd/edge_list -v 20 -e $((2**20*16))
``
This command generates a edge list file (/mnt/ssd/edge_list) which contains the edges of a SCALE 20 graph.
In Graph 500, the number of edges of a graph is #vertives x 16 (16 is called ‘edge factor’).
## Ingest Edge List (construct CSR graph)
`
./ingest_edge_list -g /l/ssd/csr_graph_file /l/ssd/edgelist1 /l/ssd/edgelist2
`
- Load edge data from files /l/ssd/edgelist1 and /l/ssd/edgelist2 (you can specify an arbitrary number of files).
A CSR graph is constructed in /l/ssd/csr_graph_file. * Each line of input files must be a pair of source and destination vertex IDs (unsigned 64bit number). * This program treats inputs as a directed graph, that is, it does not ingest edges for both directions. * This is a multi-threads (OpenMP) program. You can control the number of threads using the environment variable OMP_NUM_THREADS. * As for real-world datasets, [SNAP Datasets](http://snap.stanford.edu/data/index.html) is popular in the graph processing community. Please note that some datasets in SNAP are a little different. For example, the first line is a comment; you have to delete the line before running this program.
## Run BFS
`
./run_bfs -n \[#of vertices\] -m \[#of edges\] -g \[/path/to/graph_file\]
`
- You can get #of vertices and #of edges by running ingest_edge_list.
- This is a multi-threads (OpenMP) program.
You can control the number of threads using the environment variable OMP_NUM_THREADS.