Linear Directed Acyclic Graph
Question: I have an OCR task, where I over-segment the image. Now I want to build a
data-structure (a variety of a directed acyclic graph) to get all possible
combinations of images.

Example:  
![this picture](http://i.stack.imgur.com/29hZM.png)

I start with splitting it into four parts, a [3], b [left half of 4], c[right
half of 4], d [2]. Now I will combine them variously. To get, say, the
following paths.

0) a, b, c, d (The basic config)

1) a, bc, d (The correct config)

2) ab, c, d

3) a, b, cd

etc.

I am looking to implement this in Python. Is there an existing package? If
not, what is the best data structure? Is DAG the closest? Is there a variety
of DAG that works better?

Thanks,


Answer: OK, I have an answer. One can implement it like this.

    
    
    import random
    
    def combine(wt1, wt2):
        return random.random() < .1, (wt1+wt2)//2
    
    class Linetree():
        def __init__(self, wts):
            self.nodes = []
            for i, wt in enumerate(wts):
                self.nodes.append([[i+1, wt]])
    
            self.nodes.append([])
            self.processed = []
            self.checked = []
    
        def processnode(self, idx):
            if idx in self.processed:
                return
    
            ichild = 0
            while ichild < len(self.nodes[idx]):
                chidx, chwt = self.nodes[idx][ichild]
                self.processnode(chidx)
    
                igrandchild = 0
                while igrandchild < len(self.nodes[chidx]):
                    grchidx, grchwt = self.nodes[chidx][igrandchild]
                    if (idx, grchidx) in self.checked:
                        igrandchild += 1
                        continue
    
                    tocombine, newwt = combine(chwt, grchwt)
                    self.checked.append((idx, grchidx))
                    if tocombine:
                        self.nodes[idx].append([grchidx, newwt])
    
                    igrandchild += 1
                ichild += 1
            self.processed.append(idx)
    
        def build(self):
            self.processnode(0)
    
        def get_paths(self, n=0):
            if len(self.nodes[n]) == 0:
                yield [n]
    
            for ch, wt in self.nodes[n]:
                for sub_path in self.get_paths(ch):
                    yield [n] + sub_path
    
        def pathwt(self, path):
            ret = 0
            for i in range(len(path)-1):
                for child, wt in self.nodes[path[i]]:
                    if child == path[i+1]:
                        ret += wt
                        break
                else:
                    raise ValueError(str(path))
    
            return ret
    
        def __str__(self):
            ret = ""
            for i, children in enumerate(self.nodes):
                ret += "\nNode {}: ".format(i)
                for child in children:
                    ret += "{}, ".format(child)
            return ret
    
    def main():
        wts = range(10, 80, 10)
        print(list(enumerate(wts)))
        lt = Linetree(wts)
        print(lt.nodes)
        print(lt)
        lt.build()
        print(lt)
    
        paths = lt.get_paths()
        for path in paths:
            print(path, lt.pathwt(path))
    
    main()
    

