All path in a DAG (a kind of connected binary tree)?

As I understand your problem, node of depth n and rank r at that level will be connected to nodes of level n+1 with rank r and r+1 The direct path is certainly to look for some recurrence relation using some search function that will take one of your dags as input. You can certainly start by just looking for the max weight, when this works also building the list of nodes should not be a big problem I had it working following this path, the code and the test sets I used are below... but I removed the most interesting part to avoid spoiling the subject. I can give you some more hint if necessary.

That's only to get you started import unittest def weight(tdag, path): return sum(levelp for p, level in zip(path,tdag)) def search_max(tdag): if len(tdag) == 1: return (0,) if len(tdag) > 1: # recursive call to search_max with some new tdag # when choosing first node at depth 2 path1 = (0,) + search_max(...) # recursive call to search_max with some new tdag # when choosing second node at depth 2 # the result path should also be slightly changed # to get the expected result in path2 path2 = (0,) + ... if weigth(tdag, path1) > weigth(tdag, path2): return path1 else: return path2 class Testweight(unittest. TestCase): def test1(self): self. AssertEquals(1, weight(1,(0,))) def test2(self): self.

AssertEquals(3, weight(1, 2, 3,(0, 0))) def test3(self): self. AssertEquals(4, weight(1, 2, 3,(0, 1))) class TestSearchMax(unittest. TestCase): def test_max_one_node(self): self.

AssertEquals((0,), search_max(1)) def test_max_two_nodes(self): self. AssertEquals((0, 1), search_max(1, 2, 3)) def test_max_two_nodes_alternative(self): self. AssertEquals((0, 0), search_max(1, 3, 2)) def test_max_3_nodes_1(self): self.

AssertEquals((0, 0, 0), search_max(1, 3, 2, 6, 4, 5)) def test_max_3_nodes_2(self): self. AssertEquals((0, 0, 1), search_max(1, 3, 2, 4, 6, 5)) def test_max_3_nodes_3(self): self. AssertEquals((0, 1, 1), search_max(1, 2, 3, 4, 6, 5)) def test_max_3_nodes_4(self): self.

AssertEquals((0, 1, 2), search_max(1, 2, 3, 4, 5, 6)) if __name__ == '__main__': unittest.main().

As I understand your problem, node of depth n and rank r at that level will be connected to nodes of level n+1 with rank r and r+1. The direct path is certainly to look for some recurrence relation using some search function that will take one of your dags as input. You can certainly start by just looking for the max weight, when this works also building the list of nodes should not be a big problem.

I had it working following this path, the code and the test sets I used are below... but I removed the most interesting part to avoid spoiling the subject. I can give you some more hint if necessary. That's only to get you started.

Import unittest def weight(tdag, path): return sum(levelp for p, level in zip(path,tdag)) def search_max(tdag): if len(tdag) == 1: return (0,) if len(tdag) > 1: # recursive call to search_max with some new tdag # when choosing first node at depth 2 path1 = (0,) + search_max(...) # recursive call to search_max with some new tdag # when choosing second node at depth 2 # the result path should also be slightly changed # to get the expected result in path2 path2 = (0,) + ... if weigth(tdag, path1) > weigth(tdag, path2): return path1 else: return path2 class Testweight(unittest. TestCase): def test1(self): self. AssertEquals(1, weight(1,(0,))) def test2(self): self.

AssertEquals(3, weight(1, 2, 3,(0, 0))) def test3(self): self. AssertEquals(4, weight(1, 2, 3,(0, 1))) class TestSearchMax(unittest. TestCase): def test_max_one_node(self): self.

AssertEquals((0,), search_max(1)) def test_max_two_nodes(self): self. AssertEquals((0, 1), search_max(1, 2, 3)) def test_max_two_nodes_alternative(self): self. AssertEquals((0, 0), search_max(1, 3, 2)) def test_max_3_nodes_1(self): self.

AssertEquals((0, 0, 0), search_max(1, 3, 2, 6, 4, 5)) def test_max_3_nodes_2(self): self. AssertEquals((0, 0, 1), search_max(1, 3, 2, 4, 6, 5)) def test_max_3_nodes_3(self): self. AssertEquals((0, 1, 1), search_max(1, 2, 3, 4, 6, 5)) def test_max_3_nodes_4(self): self.

AssertEquals((0, 1, 2), search_max(1, 2, 3, 4, 5, 6)) if __name__ == '__main__': unittest.main().

Just because @Hugh posted a full solution, doesn't mean you should do it too. Please read my comment to his answer. – Björn Pollex Mar 8 at 8:11 ok thanks to all!

: ) i'm tring first to do this solution and then check Hugh Botwell. My program fails in data such a 1,2,1,2,3,9.. i'm working on! – nkint Mar 8 at 11:02 mhmm I understand Hugh Bothwell but with your.. i'm break my head with itertools.

Product but it's only more complicated.. – nkint Mar 8 at 17:52 @NKINT: The missing part in my version is only six lines long and need no import. Some list comprehension used, but nothing fancy. OK: I will give some more hint.

– kriss Mar 8 at 20:46 ok, i've done, thanks for help! – nkint Mar 8 at 23:27.

Looks like a variation on the longest path problem. You'll need to treat the node values as edge weights.

Thanks for answer, but the first problem is how to construct the DAG from the list.. – nkint Mar 8 at 0:33 You don't really have to construct it, the list already contains enough information by itself. – kriss Mar 8 at 1:50.

I don't know if this counts as "the more functional way as possible", but it is a good, clean, working solution. Hope it helps! Import random class Tree(object): def __init__(self, depth=5, rng=None, data=None): super(Tree,self).

__init__() if data is None: # generate a random tree if rng is None: _ri = random. Randint rng = lambda:_ri(1,20) self. Tree = rng() for I in range(d+1) for d in range(depth) else: # copy provided data self.

Tree = row: for row in data def copy(self): "Return a shallow copy" return Tree(data=self. Tree) def maxsum(self): "Find the maximum achievable sum to each point in the tree" t = self. Tree for row in range(1,len(t)): trow0 += trow-10 for I in range(1,row): trowi += max(trow-1i-1, trow-1i) trowrow += trow-1row-1 return self def maxpath(self): """Find the path (list of per-level indices) which leads to the greatest sum at the bottom of the tree.

Note: only makes sense when applied to a summed tree. """ t = self. Tree maxval = max(t-1) # find highest value in last row maxi = t-1.

Index(maxval) path = maxi for row in range(len(t)-2, -1, -1): # work backwards to discover how it was accumulated if maxi==0: maxi = 0 elif maxi==row+1: maxi = row elif trowmaxi-1 > trowmaxi: maxi -= 1 path. Append(maxi) path.reverse() return path def pathvalues(self, path): "Return the values following the given path" return rowi for row,i in zip(self. Tree,path) def __str__(self, width=2): fmt = '{0:>'+str(width)+'}' return '\n'.

Join(' '. Join(fmt. Format(i) for I in row) for row in self.

Tree) def solve(self, debug=False): copy = self.copy() maxpath = copy.maxsum().maxpath() origvalues = self. Pathvalues(maxpath) sumvalues = copy. Pathvalues(maxpath) if debug: print 'Original:' print self, ' ->', origvalues print 'Tree sum:' print copy, ' ->', sumvalues return origvalues def main(): tree = Tree(data=1,2,3,4,5,6) solution = tree.

Solve(debug=True) if __name__=="__main__": main() results in Original: 1 2 3 4 5 6 -> 1, 3, 6 Tree sum: 1 3 4 7 9 10 -> 1, 4, 10 and the solution returned is 1,3,6.

Homework question should not be answered with a full solution, but rather with an explanation that will help the OP understand, so that they can devise their own solution. See this meta-post. – Björn Pollex Mar 8 at 8:10 @Space_C0wb0: OK, I agree with you, I will revert to previous version.

I beleive solutions for homework problem should be published if available, but afterward. – kriss Mar 8 at 8:58.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.