Breadth-First Path Finding, Python 3

Breadth-First Path Finding

"""
Breadth-First Path Finding
Version: 1.1
"""

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = {}
        
    def getNeighbors(self):
        return self.neighbors
    
    def __repr__(self):
        return str(self.val)
        
    def __str__(self):
        return str(self.val) + ": " + str([neighbor for neighbor in self.neighbors.keys()])

class Graph:
    def __init__(self):
        self.nodesList = []
        self.nodesCount = 0
        
    def addNode(self, val):
        newnode = Node(val)
        if newnode not in self.nodesList:
            self.nodesList.append(newnode)
            self.nodesCount += 1
        return newnode
            
    def addEdge(self, source, destination, cost = 0):
        if source not in self.nodesList:
            self.nodesList.append(source)
            self.nodesCount += 1
        
        if destination not in self.nodesList:
            self.nodesList.append(destination)
            self.nodesCount += 1
            
        source.neighbors[destination] = 1
    
    def isconnected(self, node1, node2):
        if node1 not in self.nodesList or node2 not in self.nodesList:
            return False
        
        return node2 in node1.neighbors
        
            
    def size(self):
        return self.nodesCount
            
    def __str__(self):
        result = ''
        for node in self.nodesList:
            result += str(node) + "\n"
        return result

graph = Graph()
node1 = graph.addNode( "A" )
node2 = graph.addNode( "B" )
node3 = graph.addNode( "C" )

graph.addEdge(node1, node2)
graph.addEdge(node2, node3)
graph.addEdge(node3, node1)

print(graph)

print('A connected to B: ' + str(graph.isconnected(node1, node2)))
print('A connected to C: ' + str(graph.isconnected(node1, node3)))
print('B connected to C: ' + str(graph.isconnected(node2, node3)))
print('C connected to A: ' + str(graph.isconnected(node3, node1)))
print('C connected to B: ' + str(graph.isconnected(node3, node2)))

print('Size = ' + str(graph.size()))


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development