DAG: Minimizing distance between entries in grouped nodes

Question

I have a directed acyclic graph with nodes that are lists of entries that connect to entries in other nodes. Kind of like this:

entry     ]
entry--|  ] node 1
entry  |  ]
-----  |
entry<-|  ] node 2
entry  |  ]
-----  |
entry  |  ] node 3
entry--|  ]

The ordering of entries within a node is fixed. The entries are stored in an array with absolute indexes to the entries they link to. There is a maximum of 1 link per entry, and every node has at least 1 link. (in other words, this is a highly connected graph). The graph contains approximately 100,000 entries grouped in 40,000 nodes.

What I need to do is minimize the maximum distance between entries by reordering nodes so that I can use relative indexes for the links and compress the underlying data structure.

Because compression and performance is the goal, solutions that add external data (jump tables, special jump elements in the list) are unacceptable. I really need an algorithm for reordering nodes that minimizes the maximum distance between entries. Any thoughts?

Answer 1

The problem you are describing is how to minimize the maximum distance. I think it's NP-hard so a simple solution won't be very good. You could however model it as an ILP problem and use some solver for that.

You would then minimize M as an objective.

constraints would be M>= abs(s_i-e_i) for all links l_i. s_i and e_i represent the absolute indices of the start and end entry of your link.

These entries can be rewritten in terms of the node they belong to as s_i=n_i+c_i with n_i the index of the node s_i belongs to and c_i the fixed offset within that node (among the other entries). e_i is similarly rewritten. Then you're set to optimize n_i with the solver