recursive ordered node coloring

Question

I want to color all nodes of a given graph according to a given node ordering: the order is set through the Iterator<Node> nodeIterator parameter which contains all the nodes to process in the right order.

A node is colored if its neighbor is not and if a certain condition between the two considered nodes is met. A node is colored if it is an element of the parameter vector. A node is colored with its pre-defined color.

here's my code:

  #Recursive method colorNodes
    colorNodes(Graph graph,Iterator<Node> nodeIterator, Vector vector)
        if (vector.size() == graph.size())
            return true;
        node = nodeIterator.next();
        nodeNeighbors = node.getNeighbors();
        while(nodeNeighbors.hasnext()) {
            neighbor = nodeNeighbors.next();
            if (!nodeIsColored(vector, neighbor)) {
                if(conditionBetweenNodeAndNeighbor is true) {
                    vector.add(node) #color current node 
                    colorNodes(graph, nodeIterator,vector)#call recursively the method
                }
            }  
            else if (!nodeNeighbors.hasNext()) {
                    #potential last node or isolated node (having one neighbor only)
                  if(conditionBetweenNodeAndNeighbor is true) {
                    vector.add(node) #color last node anyway 
                    colorNodes(graph, nodeIterator,vector)#call recursively the method
                    }
                   }
            else {
                    continue;
                }
          return false;
        }

Could anyone clarify how to approach this problem and if my approach is correct (especially the cases differentiation)?

Answer 1

I am not sure I fully understood the requirement. Please check this pseudo code:

    //Recursive method colorNodes
    colorNodes(Graph graph,Iterator<Node> nodeIterator, Vector vector){
        
        if (vector.size() == graph.size())   return true;
        node = nodeIterator.next();       
        neighbors = node.getNeighbors()
        
        //check if leaf or isolted or all neigbors colored 
        if( (! nodeIterator.hasNext())  or  (neighbor.length == 0)   or (allNodesAreColored(neighbors))  ) { 
            //color leaf 
            if(conditionBetweenNodeAndNeighbor is true) {
                vector.add(node) 
                node.setColor(color)
                // no need for recursive call for a leaf 
            }
            return;
        }
        
        for(neighbor : neighbors ){

            if ((!nodeIsColored(vector, neighbor) and
                    (conditionBetweenNodeAndNeighbor is true) ){
                    vector.add(node) 
                    node.setColor(color)
                    colorNodes(graph, nodeIterator,vector)
                    //break if you don't want to check rest of the neighbors 
             }
         }                      
     }