StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>This is a basic problem (I'm guessing this must be a some kind of homework), I think a simple recursion could help you solve it.</p> <p>Make a function that finds every child of a node, and call this function on every child:</p> <pre><code>private static void addNodesRecursive(TreeNode node) { for(String stationName : network.getConnections(node)) { TreeNode child = new TreeNode(stationName); node.addChild(child); addNodesRecursive(child); } } </code></pre> <p>This only works if the graph we are making is a <a href="http://en.wikipedia.org/wiki/Directed_acyclic_graph" rel="noreferrer">DAG</a>. If the graph has any cycles in it (even a two way edge), it will fail.</p> <p>It will fail because we do not yet store if a node was added to our graph before. The parent will be the connected to the child and vica-versa, they are going to be added infinitely as neighbours to each other.</p> <p>The thing you can do is: make a list that stores what is added yet.</p> <pre><code>private static void addNodesRecursive(TreeNode node, List<TreeNode> addedList) { for(String stationName : network.getConnections(node)) { TreeNode child = new TreeNode(stationName); node.addChild(child); addedList.add(child); addNodesRecursive(child, addedList); } } </code></pre> <p>And only add the new node if it's not on the addedList yet:</p> <pre><code>private static void addNodesRecursive(TreeNode node, List<String> addedList) { for(String stationName : network.getConnections(node)) { if (!addedList.contains(stationName)) { TreeNode child = new TreeNode(stationName); node.addChild(child); addedList.add(child); addNodesRecursive(child, addedList); } } } </code></pre> <p>You just need to call this on the root node, so your <code>createTree</code> will be:</p> <pre><code>private static void createTree(String homeStation) { root = new TreeNode(homeStation); List<String> addedList = new ArrayList<String>(); addedList.add(homeStation); addNodesRecursive(root, addedList); } </code></pre> <p>And BAM you are finished. Calling <code>createTree</code> will create the tree starting from the root.</p> <p>P.S. I'm writing this on the fly, and I did not try my code, also my Java is a little rusty, so you could expect it to contain syntax errors (like I have corrected all my strings with small s to capital S just now).</p> <hr> <p><strong>EDIT</strong>:</p> <p>It is very important to be able to figure out a recursive problem on your own if you have any plans on being a programmer. A little help on how to figure out something recursive.</p> <ol> <li><strong>There are problems (like yours) that smell like recursion.</strong> They are about algorhythms going deep in multiple directions, and you just cannot get through it with a simple loop. Or when you try to build something that can contain multiple instances of the same thing, an so on. Be careful though. If you are programming in an <a href="http://en.wikipedia.org/wiki/Imperative_programming" rel="noreferrer">imperative</a> language (most languages, except some <a href="http://en.wikipedia.org/wiki/Declarative_programming" rel="noreferrer">declarative</a> ones, like <a href="http://en.wikipedia.org/wiki/Erlang_%28programming_language%29" rel="noreferrer">Erlang</a>, <a href="http://en.wikipedia.org/wiki/Prolog" rel="noreferrer">Prolog</a>, etc... where recursion is both bread and butter), recursion tends to be quite expensive. If you can think of an algorhythm which produces the same results but is not recursive, it is usually cheaper.</li> <li>If you decide that the problem needs recursion, then go for it: <strong>try to find a building block of a recursion.</strong> In your case it was "make a node and add all of it's child nodes to it". The child nodes should contain their children, so when you add the child node you call the same step on each of them (the step is finding and adding their child nodes).</li> <li><strong>Are we ready?</strong> When dealing with recursive problems, I usually feel that there must be something left to do even when everything is perfect. It's because you don't write the algorhythm from the beginning through the end, but in a strange unnatural order. In your case we are far from ready.</li> <li><strong>Why is it not infinite?</strong> When dealing with recursion, it's very easy to make a function calling itself infinitely, and therefore a <a href="http://en.wikipedia.org/wiki/Stack_overflow" rel="noreferrer">stack overflow</a>. We need to find the boundaries of the function. In your case the recursion will end if a node has no more child nodes. But wait: If the connections are two way two nodes will be children to each other, so every node will have a child! Somehow we need to stop adding the nodes to the tree! The most straightforward solution I can think of is remembering which nodes were added before, and only add a node <strong>if</strong> it hasn't been added yet. The list of nodes is finite, so we will run out of new nodes eventually. The keyword is <strong>if</strong>. There should be an <em>if</em> in every recursion. And there should be a branch of the condition where the recursion stops.</li> <li><strong>What is my algorythm doing?</strong> When you feel like you got somewhere, stop, and try to think through what your algorhythm is currently doing. How will it start? There are cases when you need to write a few lines of initialization before kicking off the recursion. In your case I needed to create the root, create a list of strings, and add the name of the root to the list before calling the recursion. Make sure your algorhythm has everything to start. Also make sure that it ends when you want it to. Make sure your conditions are at the right place. Try to think through simple examples.</li> </ol> <p>At least this is how I do it (and also did it while answering this :) ).</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