I need to store a large enough direct acyclic graph in Java (about 100,000 nodes, depth between 7 and 20, irregular shape, average depth 13).
What will be the most efficient data structure for saving it, if the main operation that I need after creating the data structure is as follows:
- 99% of operations: find the full set of access paths (from root to given node)
- 1% of operations: find all the children or, most often, all the ancestors of this node.
As obvious, I would like the first operation to be O (1), if possible, as opposed to O (Medium Depth)
Note that for the purposes of this question, the data structure is a one-time entry: after I build it from a list of nodes and vertices, the graph topology will never change .
My naive implementation would be to save it as a combination:
HashMap<Integer, Integer[]> childrenPerParent;
HashMap<Integer, Integer[]> ascendantPaths;
eg. I save for each node: a list of children of this node; and separately, a set of root paths from this node.
Downside: . This seems very wasteful with respect to space (we basically store each of the nodes of the internal graph that are multiples of times in ascendantPaths - for example, given size estimates, we will store an additional 100,000 * 13 = 1.3 million instances of node in ascendantPaths, each of which is the object to be created and saved)