uni/algodat/ue5/independent-set/is.py

#!/usr/bin/env python3
import sys

# utility class
class Tree:
    def __init__(self, value):
        self.value = value
        self.children = list()

    # wrapper removing truth value from tuple
    def independent_set_in_tree(self):
        return self.independent_set()[1]

    # represents implementation of independent-set-in-a-forest
    # as presented in our lectures
    def independent_set(self):
        s = list()
        adjacent = False
        if self.children == list():
            s.append(self.value)
            return (False, s)
        for c in self.children:
            if c == None: continue
            cis = c.independent_set()
            if not cis[0]:
                adjacent = True
            [s.append(i) for i in cis[1]]
        if not adjacent:
            s.append(self.value)
        return (adjacent, s)

    def add(self, pair):
        if self.value == pair[0]:
            self.children.append(Tree(pair[1]))
            return
        [c.add(pair) for c in self.children]

    def __str__(self):
        return str(self.value) + ", (" + ", ".join(str(c) for c in self.children) + ")"

# wraps remove, as node is potentially not contained in list
def remove(nodes, node):
    try:
        nodes.remove(node)
    except ValueError:
        pass

# original algorithm!
def biggest_independent_sets(trees, w_i):
    # use independent-set-in-a-forest for all individual trees
    independent_sets = list()
    for tree in trees:
        independent_sets.append(tree.independent_set_in_tree())

    print("independent_sets:", independent_sets)

    onethree  = 1 if independent_sets[0][-1] == w_i[0] else 0
    onethree += 1 if independent_sets[2][-1] == w_i[2] else 0
    twofour   = 1 if independent_sets[1][-1] == w_i[1] else 0
    twofour  += 1 if independent_sets[3][-1] == w_i[3] else 0
    print(onethree, twofour)
    biggest_total_is = list()
    # decide between w_1, ..., w_4
    if onethree >= twofour:
        remove(independent_sets[1], w_i[1])
        remove(independent_sets[3], w_i[3])
    else:
        remove(independent_sets[0], w_i[0])
        remove(independent_sets[2], w_i[2])
    # append
    for independent_set in independent_sets:
        [biggest_total_is.append(s) for s in independent_set]

    return biggest_total_is

def main(lines):
    # parsing
    T = list()
    for line in lines.split("\n"):
        if line == "": continue
        E_i = list()
        V_i = list()
        for pair in line.split(" "):
            P = list(map(int, pair.split(",")))
            E_i.append((P[0], P[1]))
            V_i.append(P[0])
            V_i.append(P[1])
        T.append(E_i)
    print("graph:", T)

    # init
    trees = list()
    w_i = list()
    for subtree in T:
        root = subtree[0][0]
        tree = Tree(root)
        w_i.append(root)
        for pair in subtree:
            tree.add(pair)
        print("tree:", tree)
        trees.append(tree)

    print(biggest_independent_sets(trees, w_i))

if __name__ == '__main__':
    lines = sys.stdin.read()
    main(lines)