-
-
Save thushw/e495a494512e280d583c4d2333080444 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Edge: | |
def __init__(self, fv, tv, name, weight): | |
self.fv = fv | |
self.tv = tv | |
self.name = name | |
self.weight = weight | |
def __repr__(self): | |
return '{}:{}:{}:{}'.format(self.fv, self.tv, self.name, self.weight) | |
class GraphNode: | |
def __init__(self, value, edges=[]): | |
self.value = value | |
self.edges = edges | |
def __repr__(self): | |
return '{} -> {}'.format(self.value, ' '.join([e.__repr__() for e in self.edges])) | |
class Graph: | |
def __init__(self): | |
self.nodes = [] | |
def __repr__(self): | |
return '\n'.join([node.__repr__() for node in self.nodes]) | |
def add_node(self, node): | |
if self.find_nodes(node.value): | |
raise ValueError('duplicate vertex {}'.format(node.value)) | |
if any([e.fv != node.value for e in node.edges]): | |
raise ValueError('the from vertex should be the same as the node you are adding it to') | |
#add any nodes on the other side of edges | |
for e in node.edges: | |
if not self.find_nodes(e.tv): | |
print ('adding missing node for {}'.format(e.tv)) | |
self.nodes.append(GraphNode(e.tv)) | |
self.nodes.append(node) | |
def find_nodes(self, tgt): | |
return [node for node in self.nodes if node.value == tgt] | |
def add_edge(self, fromv, tov, name, weight): | |
to_nodes = self.find_nodes(tov) | |
from_nodes = self.find_nodes(fromv) | |
if len(from_nodes) == 0: | |
raise IndexError('missing vertex: {}'.format(fromv)) | |
elif len(from_nodes) > 1: | |
raise ValueError('{} duplicate vertices exist for: {}'.format(len(from_nodes)-1, fromv)) | |
if len(to_nodes) > 1: | |
raise ValueError('{} duplicate vertices exist for: {}'.format(len(to_nodes)-1, tov)) | |
elif len(to_nodes) == 0: | |
print ('adding missing node') | |
self.add_node(GraphNode(tov)) | |
print ('added edge with weight {} from {} == {} to {}'.format (weight, from_nodes[0].value, fromv, tov)) | |
from_nodes[0].edges.append(Edge(fromv, tov, name, weight)) | |
g = Graph() | |
g.add_node(GraphNode('bellevue')) | |
g.add_node(GraphNode('lynwood')) | |
g.add_node(GraphNode('seattle', [Edge('seattle', 'bellevue', 'dist', 10), Edge('seattle', 'lynwood', 'dist', 20)])) | |
g.add_edge('bellevue', 'lynwood', 'dist', 5) | |
g.add_edge('bellevue', 'lynwood', 'friends', 15) | |
print (g) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment