How to traverse tree with specific properties

Question

I have a tree as shown below.

• Red means it has a certain property, unfilled means it doesn't have it. I want to minimise the Red checks.
  1. If Red than all Ancestors are also Red (and should not be checked again).
  2. If Not Red than all Descendants are Not Red.
• The depth of the tree is d.
• The width of the tree is n.

• Note that children nodes have value larger than the parent.

  • Example: In the tree below,
    • Node '0' has children [1, 2, 3],
    • Node '1' has children [2, 3],
    • Node '2' has children [3] and
    • Node '4' has children [] (No children).

  • Thus children can be constructed as:

    if vertex.depth > 0:
        vertex.children = [Vertex(parent=vertex, val=child_val, depth=vertex.depth-1, n=n) for child_val in xrange(self.val+1, n)]
    else:
        vertex.children = []
    

Here is an example tree:

I am trying to count the number of Red nodes. Both the depth and the width of the tree will be large. So I want to do a sort of Depth-First-Search and additionally use the properties 1 and 2 from above.

How can I design an algorithm to do traverse that tree?

PS: I tagged this [python] but any outline of an algorithm would do.

Update & Background

1. I want to minimise the property checks.
2. The property check is checking the connectedness of a bipartite graph constructed from my tree's path. Example:
   • The bottom-left node in the example tree has path = [0, 1].
   • Let the bipartite graph have sets R and C with size r and c. (Note, that the width of the tree is n=r*c).
   • From the path I get to the edges of the graph by starting with a full graph and removing edges (x, y) for all values in the path as such: x, y = divmod(value, c).

The two rules for the property check come from the connectedness of the graph: - If the graph is connected with edges [a, b, c] removed, then it must also be connected with [a, b] removed (rule 1). - If the graph is disconnected with edges [a, b, c] removed, then it must also be disconnected with additional edge d removed [a, b, c, d] (rule 2).

Update 2

So what I really want to do is check all combinations of picking d elements out of [0..n]. The tree structure somewhat helps but even if I got an optimal tree traversal algorithm, I still would be checking too many combinations. (I noticed that just now.)

Let me explain. Assuming I need checked [4, 5] (so 4 and 5 are removed from bipartite graph as explained above, but irrelevant here.). If this comes out as "Red", my tree will prevent me from checking [4] only. That is good. However, I should also mark off [5] from checking.

How can I change the structure of my tree (to a graph, maybe?) to further minimise my number of checks?

Answer 1

Use a variant of the deletion–contraction algorithm for evaluating the Tutte polynomial (evaluated at (1,2), gives the total number of spanning subgraphs) on the complete bipartite graph K_{r,c}.

In a sentence, the idea is to order the edges arbitrarily, enumerate spanning trees, and count, for each spanning tree, how many spanning subgraphs of size r + c + k have that minimum spanning tree. The enumeration of spanning trees is performed recursively. If the graph G has exactly one vertex, the number of associated spanning subgraphs is the number of self-loops on that vertex choose k. Otherwise, find the minimum edge that isn't a self-loop in G and make two recursive calls. The first is on the graph G/e where e is contracted. The second is on the graph G-e where e is deleted, but only if G-e is connected.

Answer 2

How hard are you working on making the test for connectedness fast?

To test a graph for connectedness I would pick edges in a random order and use union-find to merge vertices when I see an edge that connects them. I could terminate early if the graph was connected, and I have a sort of certificate of connectedness - the edges which connected two previously unconnected sets of vertices.

As you work down the tree/follow a path on the bipartite graph, you are removing edges from the graph. If the edge you remove is not in the certificate of connectedness, then the graph must still be connected - this looks like a quick check to me. If it is in the certificate of connectedness you could back up to the state of union/find as of just before that edge was added and then try adding new edges, rather than repeating the complete connectedness test.

Depending on exactly how you define a path, you may be able to say that extensions of that path will never include edges using a subset of vertices - such as vertices which are in the interior of the path so far. If edges originating from those untouchable vertices are sufficient to make the graph connected, then no extension of the path can ever make it unconnected. Then at the very least you just have to count the number of distinct paths. If the original graph is regular I would hope to find some dynamic programming recursion that lets you count them without explicitly enumerating them.

Answer 3

Python is close enough to pseudocode.

class counter(object):
    def __init__(self, ival = 0):
        self.count = ival

    def count_up(self):
        self.count += 1
        return self.count

def old_walk_fun(ilist, func=None):
    def old_walk_fun_helper(ilist, func=None, count=0):
        tlist = []
        if(isinstance(ilist, list) and ilist):
            for q in ilist:
                tlist += old_walk_fun_helper(q, func, count+1)
        else:
            tlist = func(ilist)
        return [tlist] if(count != 0) else tlist
    if(func != None and hasattr(func, '__call__')):
        return old_walk_fun_helper(ilist, func)
    else:
        return []

def walk_fun(ilist, func=None):
    def walk_fun_helper(ilist, func=None, count=0):
        tlist = []
        if(isinstance(ilist, list) and ilist):
            if(ilist[0] == "Red"): # Only evaluate sub-branches if current level is Red
                for q in ilist:
                    tlist += walk_fun_helper(q, func, count+1)
        else:
            tlist = func(ilist)
        return [tlist] if(count != 0) else tlist
    if(func != None and hasattr(func, '__call__')):
        return walk_fun_helper(ilist, func)
    else:
        return []

# Crude tree structure, first element is always its colour; following elements are its children
tree_list = \
["Red",
    ["Red", 
        ["Red", 
            []
        ], 
        ["White", 
            []
        ],
        ["White", 
            []
        ]
    ],
    ["White",
        ["White", 
            []
        ],
        ["White", 
            []
        ]
    ],
    ["Red", 
        []
    ]
]

red_counter = counter()
eval_counter = counter()
old_walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up())
print "Unconditionally walking"
print "Reds found: %d" % red_counter.count
print "Evaluations made: %d" % eval_counter.count
print ""

red_counter = counter()
eval_counter = counter()
walk_fun(tree_list, lambda x: (red_counter.count_up(), eval_counter.count_up()) if(x == "Red") else eval_counter.count_up())
print "Selectively walking"
print "Reds found: %d" % red_counter.count
print "Evaluations made: %d" % eval_counter.count
print ""