Skip to content

An example implementation of my algorithm for finding Strongly Connected Components.

License

Notifications You must be signed in to change notification settings

DavePearce/StronglyConnectedComponents

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

StronglyConnectedComponents

Two example implementations of my algorithm for finding strongly connected components in a directed graph. This algorithm improves the space requirements of Tarjan's by compressing two arrays into one. See the following paper for details of how the algorithm works:

  • A Space Efficient Algorithm for Detecting Strongly Connected Components. David J. Pearce. In Information Processing Letters, 116(1):47--52, 2016. © Elsevier.

Both a recursive and imperative version of this algorithm are given for completeness. These algorithms are not intended to be specifically efficient, just to provide sample implementations. In particular, I've tried to keep them as close to the presentation in the paper as possible.

Documentation

  • A preprint version of the paper can be obtained here.

  • A nice blog article of the algorithm can be found here.

About

An example implementation of my algorithm for finding Strongly Connected Components.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages