PyAlgDat 1.0.2
Various data structures and algorithms.
 ABOUT PYALGDAT
 FEATURES
 REQUIREMENTS
 INSTALLATION
 EXAMPLES
 DOCUMENTATION
 LICENSE
 AUTHOR
 CHANGELOG
ABOUT PYALGDAT
PyAlgDat is a collection of data structures and algorithms written in Python. The purpose of the code is to show how many of the abstract data types (ADTs) and algorithms being thought in Computer Science courses can be realised in Python.
My primary focus has been to write a library which presents a clear implementation of the various data structures and algorithms and how they can be used. This means that I have made a conscious tradeoff where clarity of the code outweighs subtle and exotic implementation constructs.
The library has mostly been implemented as a recreational project and should as such not be used in production code, since most of the data structures and algorithms are already available in the standard Python library. However, writing software that is robust, performs well, and is easy to maintain requires knowledge of data structures and algorithms. Therefore, implementing and experimenting with these provides valuable knowledge about the inner workings and implementation details found in such standard libraries.
FEATURES
Data structures included in the library
Dynamic array
Stack
Queue
BinaryHeap
 MinHeap
 MaxHeap
LinkedList
 Singly linked list
 Doubly linked list
Partition/UnionFind
 Graph
 Directed
 Undirected
 Directed weighted
 Undirected weighted
Additionally, the library contains the most common algorithms and operations needed when working with these data structures.
REQUIREMENTS
The library is selfcontained and does not have any external dependencies. PyAlgDat should run on any platform with Python 2.7 or above.
EXAMPLES
PyAlgDat has a collection of functional test examples which shows how the library can be used from a client’s perspective.
Shortest path using Dijkstra’s algorithm
Below is a simple example showing howto create a directed weighted graph using PyAlgDat and how the shortest path in this graph can be found using Dijkstra’s algorithm.
#!/usr/bin/env python """ Test of Dijkstra's algorithm for a Directed Weighted Graph. """ def create_graph(): """ Creates a Directed Weighted Graph """ # Create an empty directed weighted graph graph = DirectedWeightedGraph(7) # Create vertices vertex0 = UnWeightedGraphVertex(graph, "A") vertex1 = UnWeightedGraphVertex(graph, "B") vertex2 = UnWeightedGraphVertex(graph, "C") vertex3 = UnWeightedGraphVertex(graph, "D") vertex4 = UnWeightedGraphVertex(graph, "E") vertex5 = UnWeightedGraphVertex(graph, "F") vertex6 = UnWeightedGraphVertex(graph, "G") # Add vertices graph.add_vertex(vertex0) graph.add_vertex(vertex1) graph.add_vertex(vertex2) graph.add_vertex(vertex3) graph.add_vertex(vertex4) graph.add_vertex(vertex5) graph.add_vertex(vertex6) # Add edges graph.add_edge(vertex0, vertex1, 7) # ( A < B, 7 ) graph.add_edge(vertex1, vertex2, 2) # ( B < C, 2 ) graph.add_edge(vertex1, vertex6, 3) # ( B > G, 3 ) graph.add_edge(vertex2, vertex3, 2) # ( C > D, 2 ) graph.add_edge(vertex2, vertex6, 4) # ( C > G, 4 ) graph.add_edge(vertex3, vertex4, 5) # ( D > E, 5 ) graph.add_edge(vertex3, vertex6, 1) # ( D > G, 1 ) graph.add_edge(vertex4, vertex5, 6) # ( E > F, 6 ) graph.add_edge(vertex5, vertex0, 1) # ( F < A, 1 ) graph.add_edge(vertex5, vertex6, 4) # ( F < G, 4 ) graph.add_edge(vertex6, vertex0, 7) # ( G > A, 7 ) graph.add_edge(vertex6, vertex4, 1) # ( G > E, 1 ) # B<7<A # / \ / \ # / \ / \ # 2 3 7 1 # / \ / \ # / \ / \ # C>4>G<4<F # \ / \ / # \ / \ / # 2 1 1 6 # \ / \ / # \ / \ / # D>5>E return graph if __name__ == "__main__": # Make it possible to use py_alg_dat without performing # an installation. This is needed in order to be able # to run: python dijkstra_test.py, without having # performed an installation of the package. The is # neccessary due to Python's handling of relative # imports. if __package__ is None: import sys from os import path sys.path.append(path.dirname(path.dirname(path.abspath(__file__)))) from py_alg_dat.graph import DirectedWeightedGraph from py_alg_dat.graph_vertex import UnWeightedGraphVertex from py_alg_dat.graph_algorithms import GraphAlgorithms else: from ..py_alg_dat.graph import DirectedWeightedGraph from ..py_alg_dat.graph_vertex import UnWeightedGraphVertex from ..py_alg_dat.graph_algorithms import GraphAlgorithms # Create the graph GRAPH = create_graph() # Run Dijkstra starting at vertex "A" TABLE = GraphAlgorithms.dijkstras_algorithm(GRAPH, GRAPH[0]) # Find the edges in the Spanning Tree and its total weight SPANNING_TREE_EDGES = set() SPANNING_TREE_WEIGHT = 0 for i in xrange(len(TABLE)): entry = TABLE[i] if entry.predecessor != None: edge = entry.edge SPANNING_TREE_EDGES.add(edge) SPANNING_TREE_WEIGHT += edge.get_weight() print "Edges in Spanning Tree: " + str(SPANNING_TREE_EDGES) print "Weight of Spanning Tree: " + str(SPANNING_TREE_WEIGHT)
Minimum spanning tree using Kruskal’s algorithm
Below is a simple example showing howto create an undirected weighted graph using PyAlgDat and how the minimum spanning tree of this graph can be found using Kruskal’s algorithm.
#!/usr/bin/env python """ Test of Kruskal's algorithm for a UnDirected Weighted Graph. """ def create_graph(): """ Creates an UnDirected Weighted Graph """ # Create an empty undirected weighted graph graph = UnDirectedWeightedGraph(7) # Create vertices vertex1 = UnWeightedGraphVertex(graph, "A") vertex2 = UnWeightedGraphVertex(graph, "B") vertex3 = UnWeightedGraphVertex(graph, "C") vertex4 = UnWeightedGraphVertex(graph, "D") vertex5 = UnWeightedGraphVertex(graph, "E") vertex6 = UnWeightedGraphVertex(graph, "F") vertex7 = UnWeightedGraphVertex(graph, "G") # Add vertices graph.add_vertex(vertex1) graph.add_vertex(vertex2) graph.add_vertex(vertex3) graph.add_vertex(vertex4) graph.add_vertex(vertex5) graph.add_vertex(vertex6) graph.add_vertex(vertex7) # Add edges graph.add_edge(vertex1, vertex2, 7) # (A  B, 7) graph.add_edge(vertex1, vertex4, 5) # (A  D, 5) graph.add_edge(vertex2, vertex3, 8) # (B  C, 8) graph.add_edge(vertex2, vertex4, 9) # (B  D, 9) graph.add_edge(vertex2, vertex5, 7) # (B  E, 7) graph.add_edge(vertex3, vertex5, 5) # (C  E, 5) graph.add_edge(vertex4, vertex5, 15) # (D  E, 1) graph.add_edge(vertex4, vertex6, 6) # (D  F, 6) graph.add_edge(vertex5, vertex6, 8) # (E  F, 8) graph.add_edge(vertex5, vertex7, 9) # (E  G, 9) graph.add_edge(vertex6, vertex7, 11) # (F  G, 11) return graph if __name__ == "__main__": # Make it possible to use py_alg_dat without performing # an installation. This is needed in order to be able # to run: python kruskal_test.py, without having # performed an installation of the package. The is # neccessary due to Python's handling of relative # imports. if __package__ is None: import sys from os import path sys.path.append(path.dirname(path.dirname(path.abspath(__file__)))) from py_alg_dat.graph import UnDirectedWeightedGraph from py_alg_dat.graph_vertex import UnWeightedGraphVertex from py_alg_dat.graph_algorithms import GraphAlgorithms else: from ..py_alg_dat.graph import UnDirectedWeightedGraph from ..py_alg_dat.graph_vertex import UnWeightedGraphVertex from ..py_alg_dat.graph_algorithms import GraphAlgorithms # Create the graph GRAPH = create_graph() # Run Kruskal's algorithm MST = GraphAlgorithms.kruskals_algorithm(GRAPH) print MST
The above examples and others can be found in the ‘examples’ folder in the PyAlgDat directory.
DOCUMENTATION
The PyAlgDat API contains Docstrings for all classes and methods. Additional documentation about the library can be found in the ‘docs’ folder in the PyAlgDat directory.
The full documentation is at http://pyalgdat.readthedocs.org/en/latest/.
LICENSE
PyAlgDat is published under the MIT License. The copyright and license are specified in the file “LICENSE.txt” in the PyAlgDat directory and shown below.
CHANGELOG
1.0.2 (20160901)
 Added BellmanFord graph algorithm
 Made unit tests part of the distribution
1.0.1 (20150719)
 First release on PyPi
 Fixed a problem in singly linked list when inserting an element at a specific index, causing the reference to the tail element to be wrong.
 Fixed a problem in singly linked list when removing the last element.
 Implemented functionality to remove a vertex from a graph.
 Implemented functionality to remove an edge from a graph.
 Implemented shallow copy functionality in array_list.py.
 Implemented support for slicing in array_list.py.
 Implemented equal and not equal operators in class UnDirectedGraph.
 Implemented equal and not equal operators in singly_linked_list.py.
 Implemented equal and not equal operators in doubly_linked_list.py.
 Implemented shallow copy functionality in singly_linked_list.py.
 Implemented shallow copy functionality in doubly_linked_list.py.
 Library has now changed name to PyAlgDat.
 Removed attribute ‘numberOfVertices’ in graph.py.
 Removed attribute ‘numberOfEdges’ in graph.py.
 Renamed attribute ‘vertexName’ in graph_vertex.py to ‘vertex_name’
 Renamed attribute ‘vertexNumber’ in graph_vertex.py to ‘vertex_number’
 Renamed attribute ‘vertexWeight’ in graph_vertex.py to ‘vertex_weight’
 PyAlgDat is licensed under The MIT License (MIT)
 Made PyAlgDat pylint compliant
 Added content to README.rst
 Added examples folder containing test programs showing API usage
1.0.0 (20140209)
 First public release
File  Type  Py Version  Uploaded on  Size  

PyAlgDat1.0.2.tar.gz (md5)  Source  20160901  121KB  
 Author: Brian Horn
 Home Page: http://www.brianhorn.dk
 Download URL: http://www.brianhorn.dk/projects/pyalgdat/release/PyAlgDat1.0.2.tar.gz
 Keywords: algorithms,data structures,graph,heap,linked list,partition

License:
The MIT License (MIT) Copyright (c) 2015 by Brian Horn, trycatchhorn@gmail.com. Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 Platform: any

Categories
 Development Status :: 3  Alpha
 Intended Audience :: Developers
 Intended Audience :: Education
 Intended Audience :: Information Technology
 Intended Audience :: Science/Research
 Intended Audience :: Telecommunications Industry
 License :: OSI Approved :: MIT License
 Natural Language :: English
 Operating System :: OS Independent
 Programming Language :: Python
 Programming Language :: Python :: 2
 Programming Language :: Python :: 3
 Topic :: Scientific/Engineering
 Topic :: Software Development :: Libraries :: Python Modules
 Package Index Owner: trycatchhorn
 DOAP record: PyAlgDat1.0.2.xml