StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I think the key to good software is choosing the optimal data structure. I think that is more important than the procedures (though those are important, of course). I don't believe 2-dimensional array for a huge graph and lists for a huge number of cities are the optimal data structures; for both types of data structure you're forced to do linear search. Meaning that the speed will get worse as those data structures grow in size.</p> <p>So I propose a re-design where you rely on <code>HashMap<String></code> and <code>HashSet<String></code>. The main value of a HashMap is the constant look-up time, meaning the performance will not get worse (read more on Wikipedia if you're interested in how it works).</p> <p>So, as some answers above suggested, the outline in pseudocode would be:</p> <pre><code>HashMap<String, HashSet<String>> m = new ... For each pair c1 c2 { if c1 is not a key in m { HashSet<String> set = new HashSet<String> set.add(c2) m.put(c1, set); } else //c is a key m.get(c1).add(c2) } </code></pre> <p>Now for looking up if c1 and c2 are connected:</p> <pre><code>boolean isDirectlyConnected(c1, c2) { return m.get(c1).contains(c2) || m.get(c2).contains(c1) } boolean isConnected (c1, c2) { //checking the transitive closure of directly connected HashSet<String> citiesAlreadyChecked = new ... //cities whose edges have already been checked Queue<String> citiesToCheck = new ... citiesToCheck.push(c1) while (citiesToCheck is not empty) { String cityBeingCurrentlyChecked = citiesToCheck.pull if (isDirectlyConnected(cityBeingCurrentlyChecked,c2)) { return true; } else { citiesAlreadyChecked.add(cityBeingCurrentlyChecked) for (String adjacentCity: m.get(cityBeingCurrentlyChecked)) { if (adjacentCity is not in citiesAlreadyChecked) { citiesToCheck.push(adjacentCity) } } } } return false //transitive colsure of cities connected to c1 have been checked, and c2 was not found there. } </code></pre> <p>One could also make the graph doubly linked, and thus get rid of the || in isDirectlyConnected. Making doubly linked is done while constructing by calling </p> <p>m.put(c1, set with c2 added) AND m.put(c2, set with c1 added)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload