Реализация первого обхода глубины на основе стратегии в Python

Question

Добрый день.

У меня проблема с реализацией поиска в глубину на основе стратегии, которая определяется в классе Strategy.py. Существует также граф и класс обхода. Класс обхода хорошо отвечает за обход графа.

Класс стратегии выглядит следующим образом:

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 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 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}

Любые советы, указатели? Они были бы хорошо оценены.

Answer 1

Если бы вы просто писали два, вы бы делали обычный итеративный цикл, используя стек для DFS и очередь для BFS. здесь вы объединяете тех, кто имеет приоритетную очередь. так что вам нужно расставить приоритеты так, чтобы эти два поведения проявились. для DFS это означает, что каждый раз, когда вы добавляете что-либо, оно имеет более высокий приоритет, чем раньше (так что оно выходит раньше того, что уже есть) - увеличивающееся положительное число вполне подойдет. для BFS оно должно быть ниже, чем все, что вы добавили до сих пор (чтобы оно получилось после того, что там уже есть) - хорошо работает уменьшение отрицательного числа.

это только мой взгляд от сканирования вашего кода. Я могу ошибаться, и я не собираюсь смотреть подробно - я просто подумал, что это интересный способ взглянуть на вещи, которые могут помочь.

ps это нормально помечать домашнее задание "домашнее задание". если вы этого не сделаете, люди будут суки.