CODEWITHSUNDEEP
graph-theory
Alex Petrosyan
Alex Petrosyan

Reputation: 493

Understanding the PBBS Adjacency Graph format.

I'm trying to figure out a way to convert an Edge list representation i.e. Edge(start, end), of a graph, and the one described here and here.

I've tried figuring it out on my own, but the documentation is incredibly terse. I mainly don't understand what the numerical values are counted from: Is the offset the number of lines from where the offset is written? Is it just the line number of the beginning of the adjacency list? If I subtract the neighbouring offsets will I get the size of the contiguous block? Is it off by one?

Too many questions that could have been cleared up with an example, but unfortunately everything that uses this suite never actually explains how it's supposed to be interpreted.

e.g. if I had a directed graph that looked like this 

Edge(1,2), Edge (2,4), Edge(3,4), Edge(1,3), ..., Edge(i,j)

how would it be represented in the Adjacency Graph format of PBBS.

I understand that this is very specific, and that it probably really is simple to understand, but I'm having trouble personally. I can't understand it. If anyone could help, I'd much appreciate it.

Upvotes: 0

Views: 115

Answers (1)

MaxPlankton
MaxPlankton

Reputation: 1258

I have never used this format, but it's not difficult to understand with a example.

enter image description here

Here is the ordered list of all out edges of the graph shown above: 

0-6  line 0
1-5  line 1
2-4  line 2
2-6  line 3
3-0  line 4
3-6  line 5
3-7  line 6
5-4  line 7

Out-edge list for vertex

0 starts at line 0, mark it as [0, 1)
1 starts at line 1, mark it as [1, 2)
2 starts at line 2, mark it as [2, 4)
3 starts at line 4, mark it as [4, 7)
4 starts at line 7, mark it as [7, 7)
5 starts at line 7, mark it as [7, 8)
6 starts at line 8, mark it as [8, 8)
7 starts at line 8, mark it as [8, 8)

According to the format description,

The offset for a vertex i refers to the location of the start of a contiguous block of out edges for vertex i in the sequence of edges. The block continues until the offset of the next vertex, or the end if i is the last vertex.

It should be written as,

0
1
2
4
7
7
8
8

0-6
1-5
2-4
2-6
3-0
3-7
5-4

As how to convert edge-list graph to adjacency list graph, you can sort the graph by comparing edges nodes. Assume e1 = (source1, target1), e2 = (source2, target2), e1 < e2 if

source1 < souce2
or
source1 == source2 and target1 < target2

Upvotes: 1

Related Questions