Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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++)

share|improve this question
    
Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask –  gnat Jun 20 '13 at 23:10

2 Answers 2

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.

share|improve this answer

For rapid access and efficient storage of the data you want, you can store a pair of std::set objects whose entries are the coordinates of cells. The first is the set of cells with a neighbour to the right, the second the set of those with a neighbour below it.

If efficiency producing this structure matters to you, then I would recommend building a set of all coordinates of cells, then iterating over it and for each cell finding out whether its neighbours to the right and bottom are in the set. (Both lookups are fast.)

If you need to consider more distant neighbours, then use a std::map to store the coordinates of the cell as the key, and the coordinates of the neighbour as a value. To find those neighbours, you can use a http://en.wikipedia.org/wiki/Quadtree.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.