1
おはよう。Pythonの戦略に基づいた深さ優先トラバーサルの実装
私は、strategy.pyクラスで定義されているStrategyに基づいて深さ優先検索を実装する際に問題があります。グラフとトラバーサルクラスもあります。トラバーサルクラスは、グラフをトラバースするうえで責任があります。次のように
戦略クラスは次のとおりです。最初はしかし私の時間の手間を与えている
class BreadthFirst(Strategy):
sequence = None # the sequence in which nodes are visted
treeEdges = None # the edges used to visit the nodes traversed
root = -1 # the origin of the traversal
last_pri = -1 # the most recent priority used
def __init__(self):
"""The BreadthFirst strategy uses an initial priority of 0"""
Strategy(0)
def init(self, graph, node):
"""We reset all our state information so that old traversals do not
affect the one that is about to start."""
self.last_pri = self.init_priority
self.treeEdges = []
self.sequence = []
self.root = -1
def visit(self, node, src, pri):
"""Breadth first traversal pays no attention to weights."""
self.sequence.append(node)
if src == -1:
self.root = node
else:
self.treeEdges.append((src, node))
def complete(self, node):
pass
def discover(self, nbr, node, pri):
"""Want FIFO behaviour so increment priority (ignore weights)"""
self.last_pri += 1
return self.last_pri
def rediscover(self, nbr, node, pri):
"""Rules for rediscovery same as for discovery (because weights are
ignored)"""
self.last_pri += 1
return self.last_pri
def getResult(self):
"""Return the details of the traversal as a dictionary."""
return {"origin":self.root,
"tree":self.treeEdges,
"sequence":self.sequence}
奥行き：
class Strategy:
init_priority = 0
def __init__(self, init_pri = 0):
self.init_priority = init_pri
def init(self, graph, node):
"""Called at beginning of traversal process. Expected that
this will carry out any necessary initialisation for the
specific traversal process
"""
pass
def visit(self, node, pri):
"""Called whenever NODE is visited by a traversal process.
PRI is the priority associated with the node in the priority
queue used by the traversal process.
"""
pass
def complete(self, node):
"""Called at the end of all the processing performed in visiting NODE.
"""
pass
def discover(self, nbr, node, weight, pri):
"""Return the priority that should be associated with NBR when it is
added to the priority queue.
Called whenever NBR is discovered for the first time. NODE
is the node from which the neighbour was discovered, and
WEIGHT is the value on the edge from NODE to NBR. PRI is the
value associated with NODE in the priority queue, at the time
of discovering NBR.
"""
def rediscover(self, nbr, node, weight, pri):
"""Return the priority that should be associated with NBR when it is
added to the priority queue.
Called whenever NBR is rediscovered. NODE is the node from
which the neighbour is rediscovered, and WEIGHT is the value
associated with the edge from NODE to NBR. PRI is the
priority of NODE in the priority queue. It is provided in
case it is relevant to the traversal strategy (e.g. for Dijkstra's)
"""
pass
def getResult(self):
"""Called at the end of the traversal process. It should
return whatever is relevant or appropriate for the type of
traversal implemented by this strategy.
"""
pass
私は次のように幅優先探索を実装するために管理しました。これまで私が持っているものは次のとおりです。
class DepthFirst(Strategy):
forward = None # the forward sequence in which nodes are visted
back = None # the backward sequence in which nodes are visited
treeEdges = None # the edges used to visit the nodes traversed
cross = None
root = -1 # the origin of the traversal
last_pri = -1 # the most recent priority used
def __init__(self):
"""The DepthFirst strategy uses an initial priority of 0"""
Strategy(0)
def init(self, graph, node):
"""Called at beginning of traversal process. Expected that
this will carry out any necessary initialisation for the
specific traversal process
"""
self.last_pri = self.init_priority
self.treeEdges = []
self.forward = []
self.back = []
self.cross = []
def visit(self, node, src, pri):
"""Called whenever NODE is visited by a traversal process.
PRI is the priority associated with the node in the priority
queue used by the traversal process.
"""
self.forward.append(node)
if src == -1:
self.root = node
else:
self.treeEdges.append((src, node))
def complete(self, node):
"""Called at the end of all the processing performed in visiting NODE.
"""
if node not in self.forward:
self.cross.append(node)
def discover(self, nbr, node, pri):
"""Return the priority that should be associated with NBR when it is
added to the priority queue.
Called whenever NBR is discovered for the first time. NODE
is the node from which the neighbour was discovered, and
WEIGHT is the value on the edge from NODE to NBR. PRI is the
value associated with NODE in the priority queue, at the time
of discovering NBR.
"""
self.forward.append((node, nbr))
self.last_pri -= 1
return self.last_pri
def rediscover(self, nbr, node, pri):
"""Return the priority that should be associated with NBR when it is
added to the priority queue.
Called whenever NBR is rediscovered. NODE is the node from
which the neighbour is rediscovered, and WEIGHT is the value
associated with the edge from NODE to NBR. PRI is the
priority of NODE in the priority queue. It is provided in
case it is relevant to the traversal strategy (e.g. for Dijkstra's)
"""
self.back.append((nbr, node))
self.last_pri -= 1
return self.last_pri
def getResult(self):
"""Called at the end of the traversal process. It should
return whatever is relevant or appropriate for the type of
traversal implemented by this strategy.
"""
return {"tree":self.treeEdges,
"forward":self.forward,
"back":self.back,
"cross":self.cross}
ヒント、ポインタはありますか？彼らはよく評価されるだろう。
ありがとうございました。 – Zeno