Graph Compression by BFS SOURCE CODE APIDOCS

The Graph Compression by BFS project helps you to compress your graphs/networks in an efficient way using just a simple BFS and some more complex tricks. You can use the compressed version directly to query and navigate your original graph, so it is possible to deal with huge networks in main memory. Overall it is suitable for the Web Graph since it is able to exploit all the redundacies tipical of this graph.

You can download the original paper, wrote with Prof. Alberto Apostolico, from MDPI. Please use the following BibTeX entry if you would like to cite this software:

@Article{ad-gcbfs-09,
    AUTHOR  = {Apostolico, Alberto and Drovandi, Guido},
    TITLE   = {Graph Compression by BFS},
    JOURNAL = {Algorithms},
    VOLUME  = {2},
    YEAR    = {2009},
    NUMBER  = {3},
    PAGES   = {1031--1044},
    URL     = {http://www.mdpi.com/1999-4893/2/3/1031},
    ISSN    = {1999-4893},
    DOI     = {10.3390/a2031031}
}
                    

News

- Try your own code! more info [since 0.3.5]
- Bugfix 'Compare Contract' [since 0.3.4]

Try your own code!

The compression performance is strictly correlated to the efficiency of the BFS. This depends on how we choose to order the neighbours of a node added to the BFS queue. If you want to try different algorithms you inject your own code into the software.

To try your technique follow this steps.

Step 1.
Write your class extending BFSComparison:

package my.site.com;

import it.uniroma3.dia.gc.comparator.BFSComparator;

public class MyOwnBFSComparison extends BFSComparator {

    @Override
    public int compare(final Integer n1, final Integer n2) {
        final int d1 = graph.outDegree(n1);
        final int d2 = graph.outDegree(n2);
        return d1 - d2;
    }

    @Override
    public void beforeSort(final Integer[] a, final int length) {}

    @Override
    public void afterSort(final Integer[] a, final int length) {}

    @Override
    public void addToQueue(final int node) {}

    @Override
    public void nodeBFS(int node) {}

}

Step 2.
Add your package to the classpath.

Step 3.
Run the program:

java it.uniroma3.dia.gc.Main ax your_network -c my.site.com.MyOwnBFSComparison

Trying different methods you will get different results. You can take a look at the default method in the package it.uniroma3.dia.gc.comparator.

Results

Here compression results on some datasets gathered by the Laboratory for Web Algorithmics. All these results are obtained using a compresison level of 1000 (option -l 1000).