all path in a DAG (a kind of connected binary tree)

i have this DAG (it is similar to a binary tree, but it is a graph.. has this a specified name?):

(each number is a node and numbers in the node are for example, the program should run with random numbers)

it is represented as a list of list:

[[1],[2,3],[4,5,6]]

i have to find in the more functional way as possible the path that maximize the sum of nodes:

[1,3,6]

i've开发者_如何学Python searched and this is really similar to projecteuler #18, but project euler asks the hole sum of the path, and in my homework i have to find not only the sum but all nodes. i've tried to adapt some really good solutions to my problem but i didn't managed to. some advice?

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([level[p] 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()

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

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)):
            t[row][0] += t[row-1][0]
            for i in range(1,row):
                t[row][i] += max(t[row-1][i-1], t[row-1][i])
            t[row][row] += t[row-1][row-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 t[row][maxi-1] > t[row][maxi]:
                maxi -= 1
            path.append(maxi)
        path.reverse()
        return path

    def pathvalues(self, path):
        "Return the values following the given path"
        return [row[i] 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].