I would to find an efficient structure (speed and volume) to store nodes and the
ID: 654660 • Letter: I
Question
I would to find an efficient structure (speed and volume) to store nodes and their neighbourhood.
My input is build out of stings in the following format
./X/Y.log
where X ? [0,359] and Y ? [0,169] and each pair of (X,Y) defined the coordinate of a cell on a grid of the size [170x360].
I would like to find which cells are neighboured (above, below, right and left), maximal 4 possibilities and to store this information (coordinate and direction). The structure, where the information will be stored, should not contain duplicate information (e.g. cell (50,50) is neighboured to cell (51,50) from the left side, but cell (51,50) is as well neighboured to cell (50,50) from the right side. Only one of those likes should be stored).
An additional information, the number of input strings (format ./X/Y.log) is not more then 5% of the total amount of possible cells (360*170 = 61200 possible cells).
Which storage structure should I good to my problem? (The code would be written in C++)
Explanation / Answer
I think a graph data structure would solve your problem. Since the connections are non-directional, a tree might be difficult to implement. Also, with a tree, the "child" of one node might be the "child" of another node leading to issues of how to build the tree structure.