Common Graph Algorithms Library
Project description
Common Graph Algorithms Library
Library of graph algorithms which operate directly on python data structures.
This library uses a novel API for representing graphs. Graph vertexes can be any hashable python value and the connectivity between vertexes is represented with a callback function. This callback is named the ‘adjacent’ function. The adjacent function has the following form:
- def adjacent(vertex):
‘’’ This function returns all vertexes which the given vertex is connected to. ‘’’ return iterable-of-neighboring-vertexes
Contents:
- depth_first_traversal()
A lazy depth first traversal
- depth_first_search()
A depth first search
- iterative_deepening_depth_first_search()
Searching infinite graphs
- a_star()
Fast optimal pathfinding
- topological_sort()
Dependency resolution.
- strongly_connected_components()
Determines which areas of the graph can reach which other areas.
In the future I would like to implement more algorithms: - Minimum Spanning Tree - Min-cut/Max-flow - Substructure Search
Installation note: This package optionally uses numpy. Numpy is used by some unit tests. Numpy is used to calculate A-stars effective branching factor (EBF). If numpy is not available then EBF is not reported.
Comments and feedback are welcome Send to David McDougall email: dam1784[at]rit.edu
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.