adjacent behavior

[Becheler]

Hi again! 🌱
I'm trying to understand what the code relative to adjacent matrix does.

From what I understand (telll me if I'm wrong), you have two different behaviors/implementations that are decided based on a condition on the number of nodes in the graph, so you can

• compress everything in one big vector if it fits in memory
• or dispatch it across a vector of vectors (int**) if it does not. Am i correct?

If this is the case, then I do not understand how the rest of the code works:

• int **adj; // adj[x] - adjacency list of node x is supposed to be a vector of vector (2 dimensions)
• int *adj_matrix; // compressed adjacency matrix is supposed to be the 1D representation of the same data (?)
• bool (*adjacent)(int, int); this is a pointer on a function so you can switch execution at runtime
• bool adjacent_list(int x, int y) { return binary_search(adj[x], adj[x] + deg[x], y); } this is the behavior that goes with the 2D implementation (adj)
• bool adjacent_matrix(int x, int y) { return adj_matrix[(x * n + y) / adj_chunk] & (1 << ((x * n + y) % adj_chunk)); } is the behavior that goes with the 1D representation (adj_matrix)

That is what I could put together, but there are few things I do not understand:

1. what does the function adjacent_matrix(int, int) actually do?
2. did the adj vs adj_matrix names get swapped by inadvertence? I would expect adj to be 1D, adj_matrix to be 2D, but it seems to be the reverse in the code?
3. what is adj_matrix used for? The big algorithm defined in count() seems to access adjacency data uniquely through a call to adj[x][y], what would work only for the 2D representation.

I guess I'm missing a bunch of things! That's a big algo 😉 👏🏽

[Becheler]

Hi again! 😃
Any (even small/rapid/partial) update on this question?
Thank you!

[thocevar]

Sorry for a late reply, I'm on vacation. All your points are correct. Ideally, we would use only the adjacency matrix, where we can test adjacency in constant time. Because it can be too big since it has quadratic size, we have a backup with adjacency lists that have logarithmic lookup time. It might be worth investigating how would the new C++ unordered_map perform instead.

Function adjacent_matrix extracts a bit that indicates the adjacency of two nodes. This is encoded in individual bits to save space.

I think the names are fine. adj_matrix is a 1D representation of a 2D array. It is an array of size O(n^2) with row-wise adjacency entries.

I'll need to check the last point when I get back.

[thocevar]

3. what is adj_matrix used for? The big algorithm defined in count() seems to access adjacency data uniquely through a call to adj[x][y], what would work only for the 2D representation.

In places where it iterates over all adjacent nodes it indeed uses the adjacency list adj (with adj[x] being a list of all nodes adjacent to x). However, you will also find plenty of uses of the function pointer adjacent in if statements for efficient adjacency testing of two nodes. This pointer is initialized to either the adjacent_list or adjacent_matrix function.