Algorithm for laying out a directed acyclic graph in memory to maxmise data locality

Question

Say I have the edges

A -> C
A -> D
A -> E
B -> D
B -> E

To maximise data locality I'd arrange for the DAG to be stored in this order in memory (as an array) to minimise the distance between the node and it's dependencies.

C, A, D, E, B

so that A has a distance 1 to C, 1 to D, 2 to E.

And that B has a distance of 1 to E, and 2 to D.

Is there name for an algorithm that does this? If not, how would one implement this?

Answer 1

Looks like you want to linearize the DAG. I don't know whether you are using it for dependancy resolution. Topological_sorting looks familiar to your question. also the program tsort does very similer thing.

However it is dependancy linearization.

neel@gentoo:~$ tsort
C A
D A
E A
D B
E B

C
D
E
B
A

Which prints the order in which that tasks have to be performed. and it will possible not work if there is a cycle. its relevant as you mentioned its acyclic.

I dont know if there is any such algorithm for data locality ordering string or anything similar however It looks like your data locality string have some problem.

What if C is close(1) to A and is also close(1) to B and B is too far(4) from A how will you represent it with your data locality string ?

I don't now what exactly you want to do. If you want to liniarize dependency to perform tasks in proper order then do a topological sort.

Answer 2

Here is slightly different approach to improve locality:

http://ceur-ws.org/Vol-733/paper_pacher.pdf

The described algorithm seems to be closer to force-directed graph drawing algorithm than to topological sorting.

You should also read papers on in-memory graph databases such as imGraph