{ "info": { "author": "Brian Horn", "author_email": "trycatchhorn@gmail.com", "bugtrack_url": null, "classifiers": [ "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" ], "description": "=======\nCONTENT\n=======\n+ ABOUT PYALGDAT\n+ FEATURES\n+ REQUIREMENTS\n+ INSTALLATION\n+ EXAMPLES\n+ DOCUMENTATION\n+ LICENSE\n+ AUTHOR\n+ CHANGELOG\n\nABOUT PYALGDAT\n==============\nPyAlgDat is a collection of data structures and algorithms written in Python.\nThe purpose of the code is to show how many of the abstract data types (ADTs) and\nalgorithms being thought in Computer Science courses can be realised in Python.\n\nMy primary focus has been to write a library which presents a clear\nimplementation of the various data structures and algorithms and how they can\nbe used. This means that I have made a conscious tradeoff where clarity of the\ncode outweighs subtle and exotic implementation constructs.\n\nThe library has mostly been implemented as a recreational project and should\nas such not be used in production code, since most of the data structures and\nalgorithms are already available in the standard Python library. However,\nwriting software that is robust, performs well, and is easy to maintain requires\nknowledge of data structures and algorithms. Therefore, implementing and\nexperimenting with these provides valuable knowledge about the inner workings\nand implementation details found in such standard libraries.\n\nFEATURES\n========\nData structures included in the library\n\n+ Dynamic array\n+ Stack\n+ Queue\n+ BinaryHeap\n\n - MinHeap\n - MaxHeap\n\n+ LinkedList\n\n - Singly linked list\n - Doubly linked list\n\n+ Partition/Union-Find\n+ Graph\n - Directed\n - Undirected \n - Directed weighted\n - Undirected weighted\n\nAdditionally, the library contains the most common algorithms and operations\nneeded when working with these data structures.\n\nREQUIREMENTS\n============\nThe library is selfcontained and does not have any external dependencies.\nPyAlgDat should run on any platform with Python 2.7 or above.\n\nINSTALLATION\n============\nThe package can be installed using `pip `_\n\n.. code-block:: shell\n\n $ pip install PyAlgDat\n\nEXAMPLES\n========\nPyAlgDat has a collection of functional test examples which shows how the\nlibrary can be used from a client's perspective. \n\nShortest path using Dijkstra's algorithm\n----------------------------------------\nBelow is a simple example showing howto create a directed weighted graph\nusing PyAlgDat and how the shortest path in this graph can be found using\nDijkstra's algorithm.\n\n.. code-block:: python\n\n #!/usr/bin/env python\n\n \"\"\"\n Test of Dijkstra's algorithm for a Directed Weighted Graph.\n \"\"\"\n\n def create_graph():\n \"\"\"\n \tCreates a Directed Weighted Graph\n\t\"\"\"\n \t# Create an empty directed weighted graph\n \tgraph = DirectedWeightedGraph(7)\n\n \t# Create vertices\n \tvertex0 = UnWeightedGraphVertex(graph, \"A\")\n \tvertex1 = UnWeightedGraphVertex(graph, \"B\")\n \tvertex2 = UnWeightedGraphVertex(graph, \"C\")\n \tvertex3 = UnWeightedGraphVertex(graph, \"D\")\n \tvertex4 = UnWeightedGraphVertex(graph, \"E\")\n \tvertex5 = UnWeightedGraphVertex(graph, \"F\")\n \tvertex6 = UnWeightedGraphVertex(graph, \"G\")\n\n \t# Add vertices\n \tgraph.add_vertex(vertex0)\n \tgraph.add_vertex(vertex1)\n \tgraph.add_vertex(vertex2)\n \tgraph.add_vertex(vertex3)\n \tgraph.add_vertex(vertex4)\n \tgraph.add_vertex(vertex5)\n \tgraph.add_vertex(vertex6)\n\n \t# Add edges\n \tgraph.add_edge(vertex0, vertex1, 7) # ( A <- B, 7 )\n \tgraph.add_edge(vertex1, vertex2, 2) # ( B <- C, 2 )\n \tgraph.add_edge(vertex1, vertex6, 3) # ( B -> G, 3 )\n \tgraph.add_edge(vertex2, vertex3, 2) # ( C -> D, 2 )\n \tgraph.add_edge(vertex2, vertex6, 4) # ( C -> G, 4 )\n \tgraph.add_edge(vertex3, vertex4, 5) # ( D -> E, 5 )\n \tgraph.add_edge(vertex3, vertex6, 1) # ( D -> G, 1 )\n \tgraph.add_edge(vertex4, vertex5, 6) # ( E -> F, 6 )\n \tgraph.add_edge(vertex5, vertex0, 1) # ( F <- A, 1 )\n \tgraph.add_edge(vertex5, vertex6, 4) # ( F <- G, 4 )\n \tgraph.add_edge(vertex6, vertex0, 7) # ( G -> A, 7 )\n \tgraph.add_edge(vertex6, vertex4, 1) # ( G -> E, 1 )\n\n \t# B--<--7--<--A\n \t# / \\ / \\\n \t# / \\ / \\\n \t# 2 3 7 1\n \t# / \\ / \\\n \t# / \\ / \\\n \t# C-->--4-->--G--<--4--<--F\n \t# \\ / \\ /\n \t# \\ / \\ /\n \t# 2 1 1 6\n \t# \\ / \\ /\n \t# \\ / \\ /\n \t# D-->--5-->--E\n\n \treturn graph\n\n if __name__ == \"__main__\":\n\n # Make it possible to use py_alg_dat without performing\n # an installation. This is needed in order to be able\n # to run: python dijkstra_test.py, without having\n # performed an installation of the package. The is\n # neccessary due to Python's handling of relative\n # imports.\n if __package__ is None:\n import sys\n from os import path\n sys.path.append(path.dirname(path.dirname(path.abspath(__file__))))\n from py_alg_dat.graph import DirectedWeightedGraph\n from py_alg_dat.graph_vertex import UnWeightedGraphVertex\n from py_alg_dat.graph_algorithms import GraphAlgorithms\n else:\n from ..py_alg_dat.graph import DirectedWeightedGraph\n from ..py_alg_dat.graph_vertex import UnWeightedGraphVertex\n from ..py_alg_dat.graph_algorithms import GraphAlgorithms\n\n # Create the graph\n GRAPH = create_graph()\n # Run Dijkstra starting at vertex \"A\"\n TABLE = GraphAlgorithms.dijkstras_algorithm(GRAPH, GRAPH[0])\n # Find the edges in the Spanning Tree and its total weight\n SPANNING_TREE_EDGES = set()\n SPANNING_TREE_WEIGHT = 0\n for i in xrange(len(TABLE)):\n entry = TABLE[i]\n if entry.predecessor != None:\n edge = entry.edge\n SPANNING_TREE_EDGES.add(edge)\n SPANNING_TREE_WEIGHT += edge.get_weight()\n print \"Edges in Spanning Tree: \" + str(SPANNING_TREE_EDGES)\n print \"Weight of Spanning Tree: \" + str(SPANNING_TREE_WEIGHT)\n\n\nMinimum spanning tree using Kruskal's algorithm\n-----------------------------------------------\nBelow is a simple example showing howto create an un-directed weighted graph\nusing PyAlgDat and how the minimum spanning tree of this graph can be found\nusing Kruskal's algorithm.\n\n.. code-block:: python\n\n #!/usr/bin/env python\n\n \"\"\"\n Test of Kruskal's algorithm for a UnDirected Weighted Graph.\n \"\"\"\n\n def create_graph():\n \"\"\"\n Creates an UnDirected Weighted Graph\n \"\"\"\n # Create an empty undirected weighted graph\n graph = UnDirectedWeightedGraph(7)\n\n # Create vertices\n vertex1 = UnWeightedGraphVertex(graph, \"A\")\n vertex2 = UnWeightedGraphVertex(graph, \"B\")\n vertex3 = UnWeightedGraphVertex(graph, \"C\")\n vertex4 = UnWeightedGraphVertex(graph, \"D\")\n vertex5 = UnWeightedGraphVertex(graph, \"E\")\n vertex6 = UnWeightedGraphVertex(graph, \"F\")\n vertex7 = UnWeightedGraphVertex(graph, \"G\")\n\n # Add vertices\n graph.add_vertex(vertex1)\n graph.add_vertex(vertex2)\n graph.add_vertex(vertex3)\n graph.add_vertex(vertex4)\n graph.add_vertex(vertex5)\n graph.add_vertex(vertex6)\n graph.add_vertex(vertex7)\n\n # Add edges\n graph.add_edge(vertex1, vertex2, 7) # (A - B, 7)\n graph.add_edge(vertex1, vertex4, 5) # (A - D, 5)\n graph.add_edge(vertex2, vertex3, 8) # (B - C, 8)\n graph.add_edge(vertex2, vertex4, 9) # (B - D, 9)\n graph.add_edge(vertex2, vertex5, 7) # (B - E, 7)\n graph.add_edge(vertex3, vertex5, 5) # (C - E, 5)\n graph.add_edge(vertex4, vertex5, 15) # (D - E, 1)\n graph.add_edge(vertex4, vertex6, 6) # (D - F, 6)\n graph.add_edge(vertex5, vertex6, 8) # (E - F, 8)\n graph.add_edge(vertex5, vertex7, 9) # (E - G, 9)\n graph.add_edge(vertex6, vertex7, 11) # (F - G, 11)\n return graph\n\n if __name__ == \"__main__\":\n # Make it possible to use py_alg_dat without performing\n # an installation. This is needed in order to be able\n # to run: python kruskal_test.py, without having\n # performed an installation of the package. The is\n # neccessary due to Python's handling of relative\n # imports.\n if __package__ is None:\n \t import sys\n from os import path\n sys.path.append(path.dirname(path.dirname(path.abspath(__file__))))\n from py_alg_dat.graph import UnDirectedWeightedGraph\n from py_alg_dat.graph_vertex import UnWeightedGraphVertex\n from py_alg_dat.graph_algorithms import GraphAlgorithms\n else:\n\t from ..py_alg_dat.graph import UnDirectedWeightedGraph\n from ..py_alg_dat.graph_vertex import UnWeightedGraphVertex\n from ..py_alg_dat.graph_algorithms import GraphAlgorithms\n\n # Create the graph\n GRAPH = create_graph()\n # Run Kruskal's algorithm\n MST = GraphAlgorithms.kruskals_algorithm(GRAPH)\n print MST\n\nThe above examples -and others can be found in the 'examples' folder in\nthe PyAlgDat directory.\n\nDOCUMENTATION\n=============\nThe PyAlgDat API contains Docstrings for all classes and methods. Additional\ndocumentation about the library can be found in the 'docs' folder in the\nPyAlgDat directory.\n\nThe full documentation is at http://pyalgdat.readthedocs.org/en/latest/.\n\nLICENSE\n=======\nPyAlgDat is published under the MIT License. The copyright and license are\nspecified in the file \"LICENSE.txt\" in the PyAlgDat directory and shown\nbelow.\n\nAUTHOR\n======\nBrian Horn, trycatchhorn@gmail.com\n\n\n\n\n\nCHANGELOG\n=========\n\n1.0.2 (2016-09-01)\n==================\n\n* Added Bellman-Ford graph algorithm\n* Made unit tests part of the distribution\n\n\n1.0.1 (2015-07-19)\n==================\n\n* First release on PyPi\n* 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.\n* Fixed a problem in singly linked list when removing the last element.\n* Implemented functionality to remove a vertex from a graph.\n* Implemented functionality to remove an edge from a graph.\n* Implemented shallow copy functionality in array_list.py.\n* Implemented support for slicing in array_list.py.\n* Implemented equal -and not equal operators in class UnDirectedGraph.\n* Implemented equal -and not equal operators in singly_linked_list.py.\n* Implemented equal -and not equal operators in doubly_linked_list.py.\n* Implemented shallow copy functionality in singly_linked_list.py.\n* Implemented shallow copy functionality in doubly_linked_list.py.\n* Library has now changed name to PyAlgDat.\n* Removed attribute 'numberOfVertices' in graph.py.\n* Removed attribute 'numberOfEdges' in graph.py.\n* Renamed attribute 'vertexName' in graph_vertex.py to 'vertex_name'\n* Renamed attribute 'vertexNumber' in graph_vertex.py to 'vertex_number'\n* Renamed attribute 'vertexWeight' in graph_vertex.py to 'vertex_weight'\n* PyAlgDat is licensed under The MIT License (MIT)\n* Made PyAlgDat pylint compliant\n* Added content to README.rst\n* Added examples folder containing test programs showing API usage\n\n\n1.0.0 (2014-02-09)\n==================\n\n* First public release", "description_content_type": null, "docs_url": null, "download_url": "http://www.brianhorn.dk/projects/pyalgdat/release/PyAlgDat-1.0.2.tar.gz", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "http://www.brianhorn.dk", "keywords": "algorithms,data structures,graph,heap,linked list,partition", "license": "The MIT License (MIT)\n\nCopyright (c) 2015 by Brian Horn, trycatchhorn@gmail.com.\n\nPermission is hereby granted, free of charge, to any person obtaining a copy\nof this software and associated documentation files (the \"Software\"), to deal\nin the Software without restriction, including without limitation the rights\nto use, copy, modify, merge, publish, distribute, sublicense, and/or sell\ncopies of the Software, and to permit persons to whom the Software is\nfurnished to do so, subject to the following conditions:\n\nThe above copyright notice and this permission notice shall be included in\nall copies or substantial portions of the Software.\n\nTHE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\nIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\nFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\nAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\nLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\nOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN\nTHE SOFTWARE.", "maintainer": null, "maintainer_email": null, "name": "PyAlgDat", "package_url": "https://pypi.org/project/PyAlgDat/", "platform": "any", "project_url": "https://pypi.org/project/PyAlgDat/", "project_urls": { "Download": "http://www.brianhorn.dk/projects/pyalgdat/release/PyAlgDat-1.0.2.tar.gz", "Homepage": "http://www.brianhorn.dk" }, "release_url": "https://pypi.org/project/PyAlgDat/1.0.2/", "requires_dist": null, "requires_python": null, "summary": "Various data structures and algorithms.", "version": "1.0.2" }, "last_serial": 2317513, "releases": { "1.0.1": [ { "comment_text": "", "digests": { "md5": "dcc171cfaa4e5efff3e9c0294ca07ff8", "sha256": "8afe70155263cb3aef6959c8c505faefe4bd43a70a34b6781c8ba3af3afa6ce6" }, "downloads": -1, "filename": "PyAlgDat-1.0.1.tar.gz", "has_sig": false, "md5_digest": "dcc171cfaa4e5efff3e9c0294ca07ff8", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 46159, "upload_time": "2015-07-19T16:57:27", "url": "https://files.pythonhosted.org/packages/17/fb/3d7c4b3ac70070328f23abbb57228a46cc053188e37532d359eb5d1ba1a6/PyAlgDat-1.0.1.tar.gz" } ], "1.0.2": [ { "comment_text": "", "digests": { "md5": "f8b2fbe38dac3eac198805e9d87d72f5", "sha256": "3f5f849439ea6172d4f8237b44a9d48d1f9e6c864ebb8701cfaa38c31ab4df7a" }, "downloads": -1, "filename": "PyAlgDat-1.0.2.tar.gz", "has_sig": false, "md5_digest": "f8b2fbe38dac3eac198805e9d87d72f5", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 124351, "upload_time": "2016-09-01T03:00:55", "url": "https://files.pythonhosted.org/packages/d3/2b/073c0637bc618162696e49c7c3a318def11aea93335b24b4e242605b3f95/PyAlgDat-1.0.2.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "f8b2fbe38dac3eac198805e9d87d72f5", "sha256": "3f5f849439ea6172d4f8237b44a9d48d1f9e6c864ebb8701cfaa38c31ab4df7a" }, "downloads": -1, "filename": "PyAlgDat-1.0.2.tar.gz", "has_sig": false, "md5_digest": "f8b2fbe38dac3eac198805e9d87d72f5", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 124351, "upload_time": "2016-09-01T03:00:55", "url": "https://files.pythonhosted.org/packages/d3/2b/073c0637bc618162696e49c7c3a318def11aea93335b24b4e242605b3f95/PyAlgDat-1.0.2.tar.gz" } ] }