Page MenuHomeSoftware Heritage

Add graph compression documentation
ClosedPublic

Authored by haltode on Jul 4 2019, 11:53 AM.

Details

Summary

Lists and explains the different steps in the compression process (see T1878).

Diff Detail

Repository
rDGRPH Compressed graph representation
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

zack requested changes to this revision.Jul 4 2019, 3:23 PM
zack added inline comments.
docs/compression.rst
7–14

We should add a reference about BFS-based graph compression. The canonical citation seems to be this one:

  • Alberto Apostolico, Guido Drovandi, *Graph compression by BFS*, Algorithms 2009, 2(3), 1031-1044. mdpi <https://www.mdpi.com/1999-4893/2/3/1031/pdf>_
15

I'm missing an introduction of sort here, linking together the references above to the sections below.

Ideally we want a dataflow picture here, showing a pipeline of the various phases and which files are produced as byproduct of each phase and which ones are used as input of the next one. Could be an ASCII art, a graphviz-based diagram, or a hand-created diagram (e.g., using draw.io) that is then referenced by the .rst doc.

26

use active voice here (and in general): "we can use" → "we use"

40–41
  • "the graph" → "the resulting BV graph" (I think)
  • "stored using multiple files" → "stored as a set of files"
  • adding a brief (even very brief) description of what each one of this file contains would be useful
53–54
  • "The ordering" → "The resulting ordering"
59–61

as many files have been involved during the process, we should list here which (and all) files form the final compressed representation of the graph

74
  • style: use active voice here
  • similarly about what we did above, we should probably give here a pointer to what class/tool is used to implement this step
This revision now requires changes to proceed.Jul 4 2019, 3:23 PM
  • Add compression steps diagram
  • Add BFS compression reference
  • Fix style/grammar
haltode added inline comments.
docs/compression.rst
74

Concerning the second point, the class used is already in webgraph unlike the MPH function which is in an external library

zack requested changes to this revision.Jul 5 2019, 2:36 PM

Great graph !

Only a couple of minor things and we'll be there.

docs/compression.rst
32–36

This is great, but the other phases are inconsistently documented w.r.t. this one. Can we please have a pointer to the relevant class that implements the transformation in all phase descriptions?

docs/images/Makefile
1–9

Please generate (and clean) also SVG here.

I'm guessing for sphinx favors PNG, and allows to do its popup thingie on PNG images, but as the diagram is vectorial, it's nice to also have a non-lossy version of it available.

This revision now requires changes to proceed.Jul 5 2019, 2:36 PM
  • Specify for each steps the framework/class used
  • Add svg version of the diagram
haltode added inline comments.
docs/compression.rst
32–36

The only step where i cannot link to the specific class is the BFS since BFSBig is not yet merged in LAW.

zack requested changes to this revision.Jul 5 2019, 2:57 PM

last one ! :-)

docs/images/Makefile
12–13

these should be rm -f, otherwise make clean as a whole can fail if the first file format that make tries to remove is not available on disk

This revision now requires changes to proceed.Jul 5 2019, 2:57 PM

Add -f flag in make clean rm commands.

This revision is now accepted and ready to land.Jul 5 2019, 3:11 PM
haltode marked an inline comment as done.

Rebasing on master.

This revision was automatically updated to reflect the committed changes.