bfs_dfs.py

from graphviz import Digraph
import os


class Node:
    def __init__(self, state, parent, action, depth):
        self.state = state
        self.parent = parent
        self.action = action
        self.depth = depth
        self.id = "".join(str(n) for n in self.state)

    def __repr__(self):
        joined_string = " ".join(str(n) for n in self.state)
        return joined_string[0:5] + "\n" + joined_string[6:11] + "\n" + joined_string[12:17]


def possible_moves(state):
    pos_moves = []
    indexOf0 = state.index(0)
    if indexOf0 % 3 != 0:
        pos_moves.append("left")
    if indexOf0 - 3 >= 0:
        pos_moves.append("up")
    if indexOf0 % 3 != 2:
        pos_moves.append("right")
    if indexOf0 + 3 < 9:
        pos_moves.append("down")
    return pos_moves


def generate_state(state, m):
    def switch(index1, index2, state):
        result = []
        for element in state:
            result.append(element)
        result[index1] = state[index2]
        result[index2] = state[index1]
        return result

    temp = []
    indexoOf0 = state.index(0)
    if m == "left":
        temp = switch(indexoOf0, indexoOf0 - 1, state)
    if m == "up":
        temp = switch(indexoOf0, indexoOf0 - 3, state)
    if m == "right":
        temp = switch(indexoOf0, indexoOf0 + 1, state)
    if m == "down":
        temp = switch(indexoOf0, indexoOf0 + 3, state)
    return temp


def create_node(state, parent, action, depth):
    return Node(state, parent, action, depth)


def expand_node(node):
    expanded_nodes = []
    mouvementsPossibles = possible_moves(node.state)
    for i in mouvementsPossibles:
        nouveauEtat = generate_state(node.state, i)
        expanded_nodes.append(create_node(nouveauEtat, node.id, i, node.depth + 1))
    return expanded_nodes


def bfs():
    queue = []
    visited = []
    visited_str = []
    depth_limit = 2000
    queue.append(create_node(initial, "283164705", None, 0))
    while len(queue) > 0:
        node = queue.pop(0)
        if node.id in visited_str:
            continue
        else:
            visited.append(node)
            visited_str.append(node.id)
        if node.state == goal:
            return visited
        if node.depth < depth_limit:
            expanded_nodes = expand_node(node)
            for node in expanded_nodes:
                if node.id not in visited_str:
                    queue.append(node)


def DFS():
    stack = []
    visited = []
    visited_str = []
    depth_limit = 10
    stack.append(create_node(initial, "283164705", None, 0))
    while len(stack) > 0:
        if len(stack) == 0: return None
        node = stack.pop(0)
        if node.id in visited_str:
            continue
        else:
            visited.append(node)
            visited_str.append(node.id)
        if node.state == goal:
            return visited
        if node.depth < depth_limit:
            expanded_nodes = expand_node(node)
            if (expanded_nodes not in visited):
                expanded_nodes.extend(stack)
                stack = expanded_nodes


def display(title, path, file):
    graph_dfs = Digraph(comment=title)
    step = 0
    color = "black"
    for node in path:
        node_str = node.__str__()
        if node.state == goal: color = "green"
        graph_dfs.node(str(node.id), node_str, color=color)
        graph_dfs.edge(str(node.parent), str(node.id), str(node.action) + "\n" + str(step))
        step += 1
    graph_dfs.render(str(os.getcwd() + '/outputs/' + file + '.gv'), view=True)


goal = [1, 2, 3, 8, 0, 4, 7, 6, 5]
initial = [2, 8, 3, 1, 6, 4, 7, 0, 5]


display("BFS graph", bfs(), "bfs")
display("DFS graph", DFS(), "dfs")