Thoughts on a recursive algorithm.

Question

Hi. I have a problem at hand, which can be stated as follows.

There are two set of nodes (in a bipartite directed graph), type1 and type2.

For every node in the graph of type1, I have to find out a set which is constructed in this fashion:

Let node1 be the first node of type1.

Add node1 in the set. For node1, find out the list of nodes of type2 connected via an edge who's source is node1. For each member in the list obtained above, find the nodes of type 1 (not already in the set) connected via an edge who's target is node of type2. Add those nodes in the set. Rerun, until there is nothing to add in the set.

Iterate for all the nodes of type1.

My intuition is going towards a recursive implementation, but am unable to figure out on what parameters (confused).

Any suggestions?

Answer 1

This sounds like you could modify a breadth first search algorithm (which you can implement using a queue).

Answer 2

Since it's directed, there's a total order to the nodes.

You can use depth-first searching through the structure.

def visit( some_node, type_1_set ):
    assert node.type == 1
    type_1_set.add( some_node )
    for child in some_node.children: 
        if child.type == 2:
            for grand_child in child.children:
                if grant_child.type == 1:
                    visit( grand_child, type_1_set )

It sounds something like that.