README 750 Bytes
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Connected components in undirected graphs
=========================================

This benchmark implements the Awerbuch-Shiloach and Hybrid algorithms for
finding connected components in undirected graphs from
http://www.cs.cmu.edu/~scandal/nesl/algorithms.html#concomp

Generating test data
--------------------

The utility mkg generates random test graphs. Call it with

  mkg NODES EDGES > FILE

where NODES and EDGES determine the number of nodes and edges, respectively.

Running the benchmark
---------------------

concomp --help displays the available options.

The following algorithms are supported:

  awshu, awshup   - Awerbuch-Shiloach (sequential and parallel version)
  hybu, hybup     - Hybrid (sequential and parallel version)