Top-rated recipes tagged "directed"http://code.activestate.com/recipes/tags/directed/top/2013-04-03T19:30:32-07:00ActiveState Code RecipesStrongly connected components of a directed graph. (Python)
2013-04-03T19:30:32-07:00Mark Dickinsonhttp://code.activestate.com/recipes/users/4172683/http://code.activestate.com/recipes/578507-strongly-connected-components-of-a-directed-graph/
<p style="color: grey">
Python
recipe 578507
by <a href="/recipes/users/4172683/">Mark Dickinson</a>
(<a href="/recipes/tags/connected/">connected</a>, <a href="/recipes/tags/directed/">directed</a>, <a href="/recipes/tags/graph/">graph</a>, <a href="/recipes/tags/strong/">strong</a>, <a href="/recipes/tags/tarjan/">tarjan</a>).
Revision 3.
</p>
<p>Two linear-time algorithms for finding the strongly connected components of a directed graph. <code>strongly_connected_components_tree</code> implements (a variant of) Tarjan's well-known algorithm for finding strongly connected components, while <code>strongly_connected_components_path</code> implements a path-based algorithm due (in this form) to Gabow.</p>
<p>Edit: I added an iterative function <code>strongly_connected_components_iterative</code>; this is a direct conversion of <code>strongly_connected_components_path</code> into iterative form. It's therefore safe to use on high-depth graphs, without risk of running into Python's recursion limit.</p>
Simple graph algorithms with a modular design (Python)
2011-04-21T13:40:32-07:00jimmy2timeshttp://code.activestate.com/recipes/users/4177690/http://code.activestate.com/recipes/577668-simple-graph-algorithms-with-a-modular-design/
<p style="color: grey">
Python
recipe 577668
by <a href="/recipes/users/4177690/">jimmy2times</a>
(<a href="/recipes/tags/algorithms/">algorithms</a>, <a href="/recipes/tags/breadth/">breadth</a>, <a href="/recipes/tags/depth/">depth</a>, <a href="/recipes/tags/directed/">directed</a>, <a href="/recipes/tags/first/">first</a>, <a href="/recipes/tags/graph/">graph</a>, <a href="/recipes/tags/object/">object</a>, <a href="/recipes/tags/oriented/">oriented</a>, <a href="/recipes/tags/python/">python</a>, <a href="/recipes/tags/search/">search</a>, <a href="/recipes/tags/theory/">theory</a>, <a href="/recipes/tags/undirected/">undirected</a>, <a href="/recipes/tags/visit/">visit</a>).
Revision 7.
</p>
<p>The purpose of this recipe is to look at algorithmic graph theory from an object-oriented perspective.</p>
<p>A graph is built on top of a dictionary indexed by its vertices, each item being the set of neighbours of the key vertex.
This ensures that iterating through the neighbours of a vertex is still efficient in sparse graphs (as with adjacency lists) while at the same time checking for adjacency is expected constant-time (as with the adjacency matrix).</p>
<p>Any valid class of graph must implement the interface defined by AbstractGraph.</p>
<p>A generic search algorithm takes as input a graph, source and target vertices and a queue.
A queue must implement the methods Q.get(), Q.put() and Q.empty() in such a way to get the desired order in visiting the vertices.</p>
<p>Given this pattern, breadth-first and depth-first search are essentially defined by the corresponding expansion policies: the first one uses an actual FIFO queue, the second one a LIFO queue (or stack).</p>