Python: найти самый длинный путь

Question

У меня есть простой график, созданный как таковой в ниже

class Job(): 
    def __init__(self, name, weight): 
     self.name = name 
     self.weight = weight 
     self.depends = [] 

    def add_dependent(self, dependent): 
     self.depends.append(dependent) 


jobA = Job('A', 0) 
jobB = Job('B', 4) 
jobC = Job('C', 2) 
jobD = Job('D', 10) 
jobE = Job('E', 3) 
jobF = Job('F', 11) 

jobA.add_dependent(jobB) 
jobA.add_dependent(jobC) 
jobB.add_dependent(jobD) 
jobC.add_dependent(jobE) 
jobD.add_dependent(jobF) 
jobE.add_dependent(jobF) 

поэтому у нас есть два возможных пути

A->B->D->F 0+4+10+11 = 25 
A->C->E->F 0+2+3+11 = 16 

поэтому длинные пути будут бывший

Есть ли простой способ собрать самый длинный путь, A->B->D->F?

def longest_path(root): 
    paths = [] 
    # some logic here 
    return paths 

print longest_path(jobA) # should print A->B->D->F 

Answer 1

не самое эффективное решение, но вот один, который должен работать:

import operator 

def longest_path(root): 
    def _find_longest(job): 
     costs = [_find_longest(depend) for depend in job.depends] 
     if costs: 
      # Find most expensive: 
      path, cost = max(costs, key=operator.itemgetter(1)) 
      return ([job.name] + path, job.weight + cost) 
     else: 
      return ([job.name], job.weight) 
    return "->".join(_find_longest(root)[0]) 

Answer 2

Если вы используете OO решение, легко обеспечить способ для хранения только тяжелый путь. Этого решения, которое я придумал - используя вызываемый класс

In [111]: class Heaviest(object): 
    ...:  def __init__(self, job): 
    ...:   self.path = '' 
    ...:   self.weight = 0 
    ...:   self.job = job 
    ...:  def _find_heaviest(self, job, path='', weight=0): 
    ...:   path += job.name 
    ...:   weight += job.weight 
    ...:   if not job.depends: 
    ...:    if weight > self.weight: 
    ...:     self.weight = weight 
    ...:     self.path = path 
    ...:   else: 
    ...:    for job in job.depends: 
    ...:     self._find_heaviest(job, path, weight) 
    ...:  def __call__(self): 
    ...:   self._find_heaviest(self.job) 
    ...:   return '->'.join(list(self.path)), self.weight 
    ...:     

In [112]: Heaviest(jobA)() 
Out[112]: ('A->B->D->F', 25) 

второстепенный:

Это произошло со мной прошлой ночью, что в случае циклической зависимости (см моего комментария), то решением выше воль не дают ответа, останавливаясь с исключением, когда достигается максимальная глубина рекурсии. Просто добавление строки ниже приведет к удалению любого алгоритма пересечения деревьев, а не только этого.

In [226]: jobF.add_dependent(jobA) 

In [227]: Heaviest(jobA)() 
--------------------------------------------------------------------------- 
RuntimeError        Traceback (most recent call last) 
<ipython-input-227-94e994624b4e> in <module>() 
----> 1 Heaviest(jobA)() 

<ipython-input-111-1ff9f69480a9> in __call__(self) 
    15     self._find_heaviest(job, path, weight) 
    16  def __call__(self): 
---> 17   self._find_heaviest(self.job) 
    18   return '->'.join(list(self.path)), self.weight 
    19 

<ipython-input-111-1ff9f69480a9> in _find_heaviest(self, job, path, weight) 
    13   else: 
    14    for job in job.depends: 
---> 15     self._find_heaviest(job, path, weight) 
    16  def __call__(self): 
    17   self._find_heaviest(self.job) 

... last 1 frames repeated, from the frame below ... 

<ipython-input-111-1ff9f69480a9> in _find_heaviest(self, job, path, weight) 
    13   else: 
    14    for job in job.depends: 
---> 15     self._find_heaviest(job, path, weight) 
    16  def __call__(self): 
    17   self._find_heaviest(self.job) 

RuntimeError: maximum recursion depth exceeded 

Пока я оставляю попытки исправиться реализации к вам - если вы хотите - просто гарантия может исправить

def _find_heaviest(self, job, path='', weight=0): 
    if not job.name in path: 
     path += job.name 
     weight += job.weight 
     stop_search = not job.depends 
    else: 
     stop_search = True 
    if stop_search: 
     if weight > self.weight: 

.....

Проблема решена

In [230]: Heaviest(jobA)() 
Out[230]: ('A->B->D->F', 25)