BreadthFirst search in Java

Question

I created a tree in Java, using this type of constructor:

public class Node
{
    private List<Node> children = null;
    private String value;

    public Node(String value)
    {
        this.children = new ArrayList<>();
        this.value = value;
    }

    public void addChild(Node child)
    {
        children.add(child);
    }

}

Taken from How to create own tree in java?

I am using certain methods, to create childs for each Node.

I can't figure out how to generate the nodes using breadth-first and depth-first. I tried with a recursive method, which won't work:

public void depthFirst(Node node, int op){
    if (op == 1) operationsNoTrim(node); //child generator method
    else if (op == 2) operationsWithTrim(node); //child generator method
    else if (op == 3) operationsWithTrimNSecure(node); //child generator method
    for(int i = 0; i < node.getTotalChild(); i++){
        depthFirst(node.getChild(i), op);
    }
}

I need to generate children with a breath-first and a depth-first method, with either an iterative or recursive way, for an artificial intelligence project. If I manage these, I can probably figure out how to generate nodes with A* and IDA*... I already programmed the quality and the heuristics.

operationsNoTrim contain 4 operators, which work similarily (in terms of generating nodes), but have different rules. Note, that here, State = Node.

public void operateYellow(State state){
    int pos = 0;
    while (pos <= sqn*sqn-1 && foundObjective == false){//try each position         if (checkPosPiece(state, pos, -1) == true){ //check if field is empty
            State clonedState = cloneState(state);
            removePieceFromList(clonedState); //removes the next piece to be added, from the list
            setPieceToState(clonedState, 3, pos); //sets the piece on the field
            int points = 0;
            nodes++;
            modifyBoard(clonedState, pos, 3); //updates the board
            //Verifies if a figure has been made
            int tempPos = 0;
            boolean figureFound = false;
            while (tempPos <= (sqn*sqn-1)-(sqn+1) && figureFound == false){ //Verifies if there is a figure corner between field 0 and 18
                if (checkYellow(clonedState,tempPos)) figureFound = true;
                tempPos++;
            }
            if (figureFound){
                points = calculatePoints(armLength(clonedState, tempPos-1, 0, 1, 3)*4); //computes the size of the figure
                clearYellow(clonedState, tempPos-1);
            }
            setTotalPointsOfState(clonedState, points);
            setStateID(clonedState);
            setParentStateID(state, clonedState);
            state.addChild(clonedState);
            if (objectiveState(clonedState)){ 
                pos = sqn*sqn;
                foundObjective = true;
            }
        }
        pos++;
    }
}

I managed to create kind of a game-tree, with an arraylist, using this:

public void breadthFirst(State state, int op){
        int i = 0;
        while (foundObjective == false){ //Generate nodes until a solution is found
            if (op == 1) noTrimOperations(state);
            else if (op == 2) operationsWithTrim(state);
            else if (op == 3) operationsWithTrimNSeg(state);
            i++;
            try{
                state = cloneState(States.get(i)); //The next node to be expanded                   
                System.out.println("State: " + i);  
                System.out.println("Nodes: "+ (States.size()));
            } catch(IndexOutOfBoundsException e) { //if no mode nodes can be generated due to empty list of pieces
                return;
            }
        }
    }

However, with this arraylist I am not able to create A* and IDA*.

The State constructor contains an ID and a Parent ID field. So, after a solution is found, I backtrack the states until the root state, for the positions where the pieces must be placed.

I don't understand the question. First, the medthod `breadthFirst` seems to implement depth-frist search, not breadth-first search. What are the 'child generator methods' supposed to do? — Codor, Jan 21 '15 at 08:13
Thanks for taking the time! I have the child generator methods, which should generate childs for as long as a solution is found, or until no possible solution is found. And they should do it in a breadth-first and a depth-first manner — Timea Sorban, Jan 21 '15 at 08:16
Please show the implementation of of the child generator methods. In `breadthFirst`, their return value is not used. If the child generator methods are supposed to filter children for later processing, this might be the problem. — Codor, Jan 21 '15 at 08:19
Say I have an empty board with 2x2 fields, and a list of pieces. The child generators place the 1st piece on each field, generating 4 childs (4 more nodes). Then, the 2nd node should be taken, and place the 2nd piece on the remaining fields, and so on. — Timea Sorban, Jan 21 '15 at 08:20
I don't really follow you. Are you trying to represent a game tree as described here? http://en.wikipedia.org/wiki/Game_tree — Codor, Jan 21 '15 at 08:23
Yes, something like that, but it only has one player. I also added a method that better represents what a child generator does. — Timea Sorban, Jan 21 '15 at 08:28

BeyelerStudios · Answer 1 · 2015-01-21T09:03:58.773

if this is your depth-first:

public void depthFirst(Node node, int op){
    if (op == 1) operationsNoTrim(node); //child generator method
    else if (op == 2) operationsWithTrim(node); //child generator method
    else if (op == 3) operationsWithTrimNSecure(node); //child generator method
    for(int i = 0; i < node.getTotalChild(); i++){
        depthFirst(node.getChild(i), op);
    }
}

then this would be your breadth-first (start with list containing root)

public void breadthFirst(ArrayList<Node> nodes, int op) {
    ArrayList<Node> children = new ArrayList<>();
    // nodes contain the nodes on the previous (or parent) level
    for(int i = 0; i < nodes.size(); ++i) {
        Node node = nodes.get(i);
        if (op == 1) operationsNoTrim(node); //child generator method
        else if (op == 2) operationsWithTrim(node); //child generator method
        else if (op == 3) operationsWithTrimNSecure(node); //child generator method
        for(int i = 0; i < node.getTotalChild(); ++i) {
            children.add(node.getChild(i));
        }
    }
    // children contain the nodes on the current level
    // all the nodes have been created, but not processed yet
    // now process this level recursively...
    breadthFirst(children, op);
}

and without recursion:

public void breadthFirst(Node root, int op) {
    ArrayList<Node> nodes = new ArrayList<>();
    ArrayList<Node> children = new ArrayList<>();
    // start
    nodes.add(root);
    // as long as unprocessed nodes are available...
    while(!nodes.isEmpty()) {
        // nodes contain the nodes on the previous (or parent) level
        for(int i = 0; i < nodes.size(); ++i) {
            Node node = nodes.get(i);
            if (op == 1) operationsNoTrim(node); //child generator method
            else if (op == 2) operationsWithTrim(node); //child generator method
            else if (op == 3) operationsWithTrimNSecure(node); //child generator method
            for(int i = 0; i < node.getTotalChild(); ++i) {
                children.add(node.getChild(i));
            }
        }
        // children contain the nodes on the current level
        // all the nodes have been created, but not processed yet
        // now process this level...
        ArrayList<Node> tmp = nodes;
        nodes = children; // children is the new "parent level"
        children = tmp;
        children.clear(); // throw away previous level
    }
}

BreadthFirst search in Java

1 Answers1