# -*- coding: utf-8 -*- """ Created on Tue Apr 6 23:27:35 2021 @author: ismet """ from graphviz import Digraph as pgv from queue import Queue, PriorityQueue from os import path, makedirs counter = 0 def show(yol, kenar, kesfedilen, onyuz, baslangic, bitis): global counter if not path.exists(yol): makedirs(yol) graph = pgv.Digraph() for node in kesfedilen: if node == bitis: graph.attr(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 kesfedilen: 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]) # print(graph) graph.draw( '%s%s' % (yol, counter), format='png', prog='dot' ) counter += 1 def breadfirstsearch(graph, baslangic, bitis): onyuz = Queue() onyuz.put(baslangic) kesfedilen = [] kenar = [] # kenar that have been used while True: if onyuz.empty(): raise Exception("No way Exception") current_node = onyuz.get() kesfedilen.appbitis(current_node) # Check if node is goal-node show('/tmp/out/breadfirstsearch', kenar, kesfedilen, onyuz.queue, baslangic, bitis) if current_node == bitis: return for node in graph[current_node]: if node not in kesfedilen: kenar.appbitis((current_node, node)) onyuz.put(node) show('/tmp/out/breadfirstsearch', kenar, kesfedilen, onyuz.queue, baslangic, bitis) def deapfirstsearch(graph, baslangic, bitis): onyuz = [baslangic, ] kesfedilen = [] kenar = [] while True: if len(onyuz) == 0: raise Exception("No way Exception") current_node = onyuz.pop() kesfedilen.appbitis(current_node) # Check if node is goal-node show('/tmp/out/deapfirstsearch', kenar, kesfedilen, onyuz, baslangic, bitis) if current_node == bitis: return # expanding nodes for node in reversed(graph[current_node]): if node not in kesfedilen: kenar.appbitis((current_node, node)) onyuz.appbitis(node) show('/tmp/out/deapfirstsearch', kenar, kesfedilen, onyuz, baslangic, bitis) def uniformcostsearch_weight(from_node, to_node, weights=None): return weights.get((from_node, to_node), 10e100) if weights else 1 def uniformcostsearch(graph, baslangic, bitis, weights=None): """ Function to compute uniformcostsearch(Uniform Cost Search) for a graph :param graph: The graph to compute uniformcostsearch for :param baslangic: baslangic node :param bitis: bitis node :param weights: A dictionary of weights; maps (baslangic_node, bitis_node) -> weight """ onyuz = PriorityQueue() onyuz.put((0, baslangic)) # (priority, node) kesfedilen = [] kenar = [] while True: if onyuz.empty(): raise Exception("No way Exception") uniformcostsearch_w, current_node = onyuz.get() kesfedilen.appbitis(current_node) show('/tmp/out/uniformcostsearch', kenar, kesfedilen, [node[1] for node in onyuz.queue], baslangic, bitis) if current_node == bitis: return for node in graph[current_node]: if node not in kesfedilen: onyuz.put(( uniformcostsearch_w + uniformcostsearch_weight(current_node, node, weights), node )) kenar.appbitis((current_node, node)) show('/tmp/out/uniformcostsearch', kenar, kesfedilen, [node[1] for node in onyuz.queue], baslangic, bitis) if __name__ == "__main__": ilkresim = { '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'] } breadfirstsearch(ilkresim, 'A', 'Y') deapfirstsearch(ilkresim, 'A', 'Y') uniformcostsearch(ilkresim, 'A', 'Y') uniformcostsearch_test_graph = { 'S': ['A', 'B', 'C'], 'A': ['S', 'G'], 'B': ['S', 'G'], 'C': ['S', 'G'], 'G': ['A', 'B', 'C'] } uniformcostsearch_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, } uniformcostsearch(uniformcostsearch_test_graph, 'S', 'G', uniformcostsearch_test_weight) ikinciresim = { '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'] } breadfirstsearch(ikinciresim, 'A', 'Y') deapfirstsearch(ikinciresim, 'A', 'Y') uniformcostsearch(ikinciresim, 'A', 'Y')