-
Notifications
You must be signed in to change notification settings - Fork 698
/
graph-problems.py
96 lines (86 loc) · 3.08 KB
/
graph-problems.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# -*- coding: utf-8 -*-
"""
@author: salimt
"""
class Node(object):
def __init__(self, name):
"""Assumes name is a string"""
self.name = name
def getName(self):
return self.name
def __str__(self):
return self.name
class Edge(object):
def __init__(self, src, dest):
"""Assumes src and dest are nodes"""
self.src = src
self.dest = dest
def getSource(self):
return self.src
def getDestination(self):
return self.dest
def __str__(self):
return self.src.getName() + '->' + self.dest.getName()
class Digraph(object):
"""edges is a dict mapping each node to a list of
its children"""
def __init__(self):
self.edges = {}
def addNode(self, node):
if node in self.edges:
raise ValueError('Duplicate node')
else:
self.edges[node] = []
def addEdge(self, edge):
src = edge.getSource()
dest = edge.getDestination()
if not (src in self.edges and dest in self.edges):
raise ValueError('Node not in graph')
self.edges[src].append(dest)
def childrenOf(self, node):
return self.edges[node]
def hasNode(self, node):
return node in self.edges
def getNode(self, name):
for n in self.edges:
if n.getName() == name:
return n
raise NameError(name)
def __str__(self):
result = ''
for src in self.edges:
for dest in self.edges[src]:
result = result + src.getName() + '->'\
+ dest.getName() + '\n'
return result[:-1] #omit final newline
class Graph(Digraph):
def addEdge(self, edge):
Digraph.addEdge(self, edge)
rev = Edge(edge.getDestination(), edge.getSource())
Digraph.addEdge(self, rev)
# For example, an acceptable permutation (edge)
# is between "ABC" and "ACB" but not between "ABC" and "CAB".
nodes = []
nodes.append(Node("ABC")) # nodes[0]
nodes.append(Node("ACB")) # nodes[1]
nodes.append(Node("BAC")) # nodes[2]
nodes.append(Node("BCA")) # nodes[3]
nodes.append(Node("CAB")) # nodes[4]
nodes.append(Node("CBA")) # nodes[5]
g = Graph()
for n in nodes:
g.addNode(n)
n = len(nodes)
for node in range(n-1):
currentNode = Node.getName(nodes[node])
for item in range(node+1, n):
nextNode = Node.getName(nodes[item])
# print(currentNode, nextNode)
if currentNode == nextNode: raise ValueError ('Same Value Exists!')
if currentNode[0] == nextNode[0] and currentNode[1] == nextNode[2] \
and currentNode[2] == nextNode[1]:
g.addEdge(Edge(g.getNode(currentNode), g.getNode(nextNode)))
if currentNode[0] == nextNode[1] and currentNode[1] == nextNode[0] \
and currentNode[2] == nextNode[2]:
g.addEdge(Edge(g.getNode(currentNode), g.getNode(nextNode)))
print(g)