Python: Finding the longest path
<p>I have a simple graph created as such in the below</p>

<pre><code>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)
</code></pre>

<p>so we have two possible paths</p>

<pre><code>A-&gt;B-&gt;D-&gt;F  0+4+10+11 = 25
A-&gt;C-&gt;E-&gt;F  0+2+3+11 = 16
</code></pre>

<p>so the longest paths would be the former</p>

<p>Is there an easy way to gather the longest path, <code>A-&gt;B-&gt;D-&gt;F</code>?</p>

<pre><code>def longest_path(root):
    paths = []
    # some logic here
    return paths

print longest_path(jobA) # should print A-&gt;B-&gt;D-&gt;F
</code></pre>

<p>If you use OO solution, it's easy to provide a way to store only the heaviest path.
This is the solution I came up with - using a callable class</p>

<pre><code>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 &gt; 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 '-&gt;'.join(list(self.path)), self.weight
     ...:                 

In [112]: Heaviest(jobA)()
Out[112]: ('A-&gt;B-&gt;D-&gt;F', 25)
</code></pre>

<p>An afterthought:</p>

<p>It occurred to me last night that in case of cyclic dependency (see my comment), the solution above will not yield an answer, stopping with exception when maximum recursion depth is reached. Just adding the line below will blow any tree traversing algorithm - not just this one.</p>

<pre><code>In [226]: jobF.add_dependent(jobA)

In [227]: Heaviest(jobA)()
---------------------------------------------------------------------------
RuntimeError                              Traceback (most recent call last)
&lt;ipython-input-227-94e994624b4e&gt; in &lt;module&gt;()
----&gt; 1 Heaviest(jobA)()

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

&lt;ipython-input-111-1ff9f69480a9&gt; in _find_heaviest(self, job, path, weight)
     13         else:
     14             for job in job.depends:
---&gt; 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 ...

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

RuntimeError: maximum recursion depth exceeded
</code></pre>

<p>While I leave attempt to mend the implementation to you - if you wish - simple safeguard can fix that</p>

<pre><code>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 &gt; self.weight:
</code></pre>

<p>.....</p>

<p>Problem solved</p>

<pre><code>In [230]: Heaviest(jobA)()
Out[230]: ('A-&gt;B-&gt;D-&gt;F', 25)
</code></pre>

python python-2.7 longest-path