Python: Trouver le plus long chemin

Question

J'ai un graphique simple créé en tant que tel dans le ci-dessous

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) 

nous avons donc deux chemins possibles

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

de sorte que les chemins les plus longs seraient les premiers

est-il un moyen facile de recueillir le plus long chemin, 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

pas la solution la plus efficace, mais en voici un qui devrait fonctionner:

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

Si vous utilisez une solution OO, il est facile de fournir un moyen de stocker seulement le plus lourd chemin. C'est la solution que je suis venu avec - en utilisant une classe appelable

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) 

après coup:

Il me est apparu hier soir qu'en cas de dépendance cyclique (voir mon commentaire), la solution ci-dessus ne donne pas de réponse, s'arrêtant avec exception lorsque la profondeur de récursivité maximale est atteinte. Juste ajouter la ligne ci-dessous va souffler n'importe quel arbre algorithme de déplacement - pas seulement celui-ci.

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 

Pendant que je laisse tenter de réparer la mise en œuvre pour vous - si vous le souhaitez - simple, sauvegarde peut fixer que

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: 

.....

Problème résolu

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