Algorithms for visiting all vertices accessible from a given start vertex.
Sample partial implementation: parse.py
Issues:
Note: for printing the tree, you can use the following format:
parent
child-1
grandchild-1-1
grandchild-1-2
child-2
child-3
grandchild-3-1
grandchild-3-2
import random
class MatrGraph:
"""A directed graph, represented by adjacency matrix.
Vertices are numbers from 0 to n-1"""
def __init__(self, n):
"""Creates a graph with n vertices (numbered from 0 to n-1)
and no edges"""
self._matr = []
for i in range(n):
self._matr.append([])
for j in range(n):
self._matr[i].append(False)
def parseX(self):
"""Returns an iterable containing all the vertices"""
nrOfVertices = len(self._matr)
return range(nrOfVertices)
def parseNout(self, x):
"""Returns an iterable containing the outbound neighbours of x"""
list =[]
for i in range(len(self._matr[x])):
if self._matr[x][i] :
list.append(i)
return list
def parseNin(self,x):
"""Returns an iterable containing the inbound neighbours of x"""
list =[]
for i in range(len(self._matr)):
if self._matr[i][x] :
list.append(i)
return list
def isEdge(self,x,y):
"""Returns True if there is an edge from x to y, False otherwise"""
return self._matr[x][y]
def addEdge(self,x,y):
"""Adds an edge from x to y.
Precondition: there is no edge from x to y"""
self._matr[x][y] = True
class DictGraph:
"""A directed graph, represented as a map from each vertex to
the set of outbound neighbours"""
def __init__(self,n):
"""Creates a graph with n vertices (numbered from 0 to n-1)
and no edges"""
self._dict={}
for i in range(n):
self._dict[i]=[]
def parseX(self):
"""Returns an iterable containing all the vertices"""
return self._dict.keys()
def parseNout(self,x):
"""Returns an iterable containing the outbound neighbours of x"""
return self._dict[x]
def parseNin(self,x):
"""Returns an iterable containing the inbound neighbours of x"""
list=[]
for i in self._dict.keys():
if x in self._dict[i]:
list.append(i)
return list
def isEdge(self,x,y):
"""Returns True if there is an edge from x to y, False otherwise"""
return y in self._dict[x]
def addEdge(self,x,y):
"""Adds an edge from x to y.
Precondition: there is no edge from x to y"""
self._dict[x].append(y)
class DoubleDictGraph:
"""A directed graph, represented as two maps,
one from each vertex to the set of outbound neighbours,
the other from each vertex to the set of inbound neighbours"""
def __init__(self,n):
"""Creates a graph with n vertices (numbered from 0 to n-1)
and no edges"""
self._dictOut={}
self._dictIn = {}
for i in range(n):
self._dictOut[i]=[]
self._dictIn[i] = []
def parseX(self):
"""Returns an iterable containing all the vertices"""
return self._dictOut.keys()
def parseNout(self,x):
"""Returns an iterable containing the outbound neighbours of x"""
return self._dictOut[x]
def parseNin(self,x):
"""Returns an iterable containing the inbound neighbours of x"""
return self._dictIn[x]
def isEdge(self,x,y):
"""Returns True if there is an edge from x to y, False otherwise"""
return y in self._dictOut[x]
def addEdge(self,x,y):
"""Adds an edge from x to y.
Precondition: there is no edge from x to y"""
self._dictOut[x].append(y)
self._dictIn[y].append(x)
def accessible(g, s):
"""Returns the set of vertices of the graph g that are accessible
from the vertex s"""
acc = set()
acc.add(s)
list = [s]
while len(list) > 0:
x = list[0]
list = list[1 : ]
for y in g.parseNout(x):
if y not in acc:
acc.add(y)
list.append(y)
return acc
class GoatStatus:
def __init__(self, i):
self._status = i
def __str__(self):
return self.strX(~self._status) + "/" + self.strX(self._status)
def __eq__(self, other):
if isinstance(other, self.__class__):
return self.__dict__ == other.__dict__
else:
return False
def __ne__(self, other):
return not self.__eq__(other)
def __hash__(self):
return self._status
def isValid(self):
"""True if nobody eats nobody in this state"""
return self.isValidBank(self._status) and self.isValidBank(~self._status)
def parseN(self):
ret = []
for i in range(4):
if (self._status & 1) == ((self._status >> i) & 1):
ns = self._status ^ ((1 << i) | 1);
s = GoatStatus(ns)
if s.isValid():
ret.append(s)
return ret
def isValidBank(self, i):
return (i&4) == 0 or (i&1) == 1 or ((i&2) == 0 and (i&8) == 0)
def strX(self, i):
ret = "("
for j in range(4):
if (i & (1<<j)) != 0:
ret = ret + " " + self.names[j]
return ret + ")"
names = ("boat", "cabbage", "goat", "wolf")
class GoatGraph:
def parseX(self):
ret = []
for i in range(16):
s = GoatStatus(i)
if s.isValid():
ret.append(s)
return ret
def parseNout(self, s):
return s.parseN()
def parseNin(self, s):
return s.parseN()
def initMyGraph(ctor):
"""Constructs and returns a hard-coded sample graph.
ctor must be a callable that gets the number of vertices and
creates a graph with the given number of vertces and with no edges"""
g = ctor(5)
g.addEdge(0,1)
g.addEdge(1,0)
g.addEdge(1,1)
g.addEdge(1,2)
g.addEdge(4,0)
g.addEdge(4,2)
return g
def initRandomGraph(ctor,n,m):
"""Constructs and returns a randomly generated graph
with n vertices and m edges.
ctor must be a callable that gets the number of vertices and
creates a graph with the given number of vertces and with no edges"""
g=ctor(n)
addedEdges=0
while addedEdges < m:
x=random.randrange(0,n)
y=random.randrange(0,n)
if not g.isEdge(x,y):
g.addEdge(x,y)
addedEdges+=1
return g
def run():
g = initMyGraph(DoubleDictGraph)
for x in g.parseX():
print ("%s:" % x)
for y in g.parseNin(x):
print ("%s <- %s" % (x, y))
run()
g = initMyGraph(MatrGraph)
s = 0
print accessible(g, s)