How is graph represented/ stored for running algorithms here?

[amit-upadhyay-IT]

I wanted to know how is the Graph is actually represented in memory for some algorithms written here in this framework. I wanted to run some algorithms for my school project where the input to the algorithm is a graph.

I can see the input data provided here but I can't conclude the representation of the Graph(Although, it's written 'Adjacency Graph' on the top, but is it 'Adjacency List' or what?). It seems like just vertices of the graph is provided in the input file, but how do I form edges in the Graph?

In the docs here I see that:

One of the main goals of Ligra is to abstract away implementation specific details about how the graph is represented (Is the graph compressed/uncompressed? Is it directed/undirected?)

But still, I wanted to pass my own graph input which is represented as Adjacency List? Can you please tell how is the Graph formed from the data given below? How can I form Adjacency List out of it?

AdjacencyGraph
128
708
0
8
8
17
24
28
28
33
37
.
.
.

These are the first few lines of the input file written here.

Or can you please tell how to pass our own graph (represented as Adjacency List) as the input to the algorithms written here.

Example: How do I pass the below graph in the input?

         1
        /  \
       2    3
      / \  / \
     4  5,6   7
      \ | | /
         8

If I have to represent the above graph in memory then I would write the file something like this:

(source node, destination node)
1, 2
1, 3
2, 4
2, 5
3, 6
3, 7
4, 8
5, 8
6, 8
7, 8

So how can I pass this representation(or modify this representation) to work with the algorithms written here.

[ldhulipala]

Hi Amit,

Ligra currently doesn't support an adjacency list representation, but it supports something close called compressed sparse row (CSR). There's an example of how the format should look here: https://github.com/jshun/ligra#input-format-for-ligra-applications-and-the-ligra-encoder

Basically, the format consists of the header, which contains three lines ("adjacency graph", n, and m) followed by n vertex offsets (the index of each vertex's edges in the edge array), followed by the edge array.

AdjacencyGraph
<n>
<m>
<o0>
<o1>
...
<o(n-1)>
<e0>
<e1>
...
<e(m-1)>

If you have files in a different format it should be straightforward to write a converter that outputs a file in this CSR format. Note that for directed graphs you only represent the out-edges of each vertex --- the in-edges (the transpose) gets computed in-memory once the graph has been loaded.

[amit-upadhyay-IT]

Thanks! It's useful.