# -*- coding: utf-8 -*- """ Created on Tue Apr 6 23:27:35 2021 @author: ismet """ from queue import Queue, PriorityQueue from pygraphviz import AGraph from os import path, makedirs counter = 0 def show(yol, kenar, kesif, onyuz, baslangic, bitis): global counter if not path.exists(yol): makedirs(yol) graph = AGraph() for node in kesif: if node == bitis: graph.add_node(node, shape="doublecircle") elif node == baslangic: graph.add_node(node, style="bold", shape="circle") else: graph.add_node(node, style="filled", shape="circle") for node in onyuz: if node == bitis: if node not in kesif: graph.add_node(node, style="dotted", shape="doublecircle") else: graph.add_node(node, style="dotted", shape="circle") for edge in kenar: graph.add_edge(edge[0], edge[1]) graph.draw( '%s%s' % (yol, counter), format='png', prog='dot' ) counter += 1 def breadsearch(graph, baslangic, bitis): frontier = Queue() frontier.put(baslangic) explored = [] edges = [] while True: if frontier.empty(): raise Exception("Yol Bulunamadi") current_node = frontier.get() explored.append(current_node) show('/tmp/out/breadhsearch', edges, explored, frontier.queue, baslangic, bitis) if current_node == bitis: return for node in graph[current_node]: if node not in explored: edges.append((current_node, node)) frontier.put(node) show('/tmp/out/breadhsearch', edges, explored, frontier.queue, baslangic, bitis) def depthsearch(graph, baslangic, bitis): frontier = [baslangic, ] explored = [] edges = [] while True: if len(frontier) == 0: raise Exception("Yol Yok") current_node = frontier.pop() explored.append(current_node) # Check if node is goal-node show('/tmp/out/depthsearch', edges, explored, frontier, baslangic, bitis) if current_node == bitis: return # expanding nodes for node in reversed(graph[current_node]): if node not in explored: edges.append((current_node, node)) frontier.append(node) show('/tmp/out/depthsearch', edges, explored, frontier, baslangic, bitis) def ucs_weight(from_node, to_node, weights=None): return weights.get((from_node, to_node), 10e100) if weights else 1 def unicost(graph, baslangic, bitis, weights=None): frontier = PriorityQueue() frontier.put((0, baslangic)) explored = [] edges = [] while True: if frontier.empty(): raise Exception("Yol Yok") ucs_w, current_node = frontier.get() explored.append(current_node) show('/tmp/out/ucs', edges, explored, [node[1] for node in frontier.queue], baslangic, bitis) if current_node == bitis: return for node in graph[current_node]: if node not in explored: frontier.put(( ucs_w + ucs_weight(current_node, node, weights), node )) edges.append((current_node, node)) show('/tmp/out/ucs', edges, explored, [node[1] for node in frontier.queue], baslangic,bitis) if __name__ == "__main__": # This is Tree first_graph = { 'A': ['B', 'C', 'D', 'E'], 'B': ['A', 'F', 'G'], 'C': ['A', 'H'], 'D': ['A', 'I', 'J'], 'E': ['A', 'K', 'L'], 'F': ['B', 'M', 'N', 'O'], 'G': ['B', 'P', 'Q', 'R'], 'H': ['C', 'S'], 'I': ['D'], 'J': ['D', 'T', 'U'], 'K': ['E'], 'L': ['E', 'V'], 'M': ['F'], 'N': ['F'], 'O': ['F'], 'P': ['G'], 'Q': ['G'], 'R': ['G'], 'S': ['H', 'W', 'X'], 'T': ['J'], 'U': ['J', 'Y', 'Z'], 'V': ['L'], 'W': ['S'], 'X': ['S'], 'Y': ['U'], 'Z': ['U'] } breadsearch(first_graph, 'A', 'Y') depthsearch(first_graph, 'A', 'Y') unicost(first_graph, 'A', 'Y') ucs_test_graph = { 'S': ['A', 'B', 'C'], 'A': ['S', 'G'], 'B': ['S', 'G'], 'C': ['S', 'G'], 'G': ['A', 'B', 'C'] } ucs_test_weight = { ('S', 'A'): 1, ('S', 'B'): 5, ('S', 'C'): 15, ('A', 'G'): 10, ('A', 'S'): 1, ('B', 'S'): 5, ('B', 'G'): 5, ('C', 'S'): 15, ('C', 'G'): 5, ('G', 'A'): 10, ('G', 'B'): 5, ('G', 'C'): 5, } unicost(ucs_test_graph, 'S', 'G', ucs_test_weight) second_graph = { 'A': ['B', 'C', 'D', 'E'], 'B': ['A', 'F', 'G', 'H'], 'C': ['A', 'H'], 'D': ['A', 'I', 'J'], 'E': ['A', 'K', 'L'], 'F': ['B', 'G', 'M', 'N', 'O'], 'G': ['B', 'F', 'P', 'Q', 'R'], 'H': ['C', 'G', 'S'], 'I': ['D'], 'J': ['D', 'T', 'U'], 'K': ['E'], 'L': ['E', 'V'], 'M': ['F'], 'N': ['F'], 'O': ['F'], 'P': ['G'], 'Q': ['G'], 'R': ['G'], 'S': ['H', 'W', 'X'], 'T': ['J'], 'U': ['J', 'Y', 'Z'], 'V': ['L'], 'W': ['S'], 'X': ['S'], 'Y': ['U'], 'Z': ['U'] } breadsearch(second_graph, 'A', 'Y') depthsearch(second_graph, 'A', 'Y') unicost(second_graph, 'A', 'Y')