DISCLib

DISCLib is a Non-Object-Oriented Python library for teaching data structure and algorithms at Universidad de los Andes, developed by professors and staff in the Faculty of Engineering, Department of Systems and Computer Engineer #DISC.

View Demo and Examples · Report Bug · Request Feature

Table of Contents (up to date)

1. DISCLib
   1. About The Project
      1. Structure
      2. Implementation
   2. Getting Started
      1. Prerequisites
      2. Installation
   3. Usage
   4. Contact and support
   5. Roadmap
   6. Contributing
   7. License
   8. Authors and acknowledgment

About The Project

This project was created as a pedagogical library to teach the undergraduate students in the Systems and Computer Engineer program at Universidad de los Andes and others in the faculty to use and understand data structures and its related algorithm. This includes Arrays, Lists, Maps, Ordered Maps, Binary Search Trees (BST), Red Black Trees (RBT) and Graphs.

IMPORTANT This is a work in progress. The project is mainly focused as a teaching tool for undergraduate college students and is not intended to be used as a full-functional library.

Back to top

Structure

The project has four main parts:

1. DISClib Root folder with the library implementation.

   1. ADT Folder with the main Abstract Data Types (ADT) implemented in the library.

      1. List Script implementing the ADT Lists in the library, configurable by Array List, Single Linked List and Double Linked List structures.
      2. Queue Script implementing the ADT queue based in the ADT List.
      3. Stack Script implementing the ADT stack based in the ADT List.
      4. Map Script implementing the ADT Map using Hash Tables as data structures, configurable by collision handling method to Linear Probing and Separate Chaining.
      5. Ordered Map Script implementing the ADT Ordered Maps using binary trees as data structures, configurable to Binary Search Trees (BST) and Red Black Tree (RBT).
      6. MinPQ Script implementing the ADT Min Priority Queue using heap data structures.
      7. Indexed MinPQ Script implementing the ADT Indexed Min Priority Queue using the indexed heap data structure.
      8. Graph Script implementing the ADT Graph using adjacency lists as data structures.

   2. Algorithms Folder with the main algorithms implemented to manage the ADTs.

      1. Graphs Folder with the algorithms to manage the ADT Graph.
         1. DFS Script implementing the Depth First Search (DFS) algorithm.
         2. BFS Script implementing the Breath First Search (BFS) algorithm.
         3. DFO Script implementing the Depth First Order (DFO) topological sorting algorithm.
         4. Cycles Script implementing the Cycle Detection algorithm.
         5. SCC Script implementing the Strongly Connected Components (SCC) algorithm.
         6. Prim Script implementing the Prim's algorithm.
         7. Dijkstra Script implementing the Dijkstra's algorithm.
         8. Bellman-Ford Script implementing the Bellman-Ford algorithm.
      2. Sorting Folder with the algorithms implementing sorting for the ADT List.
         1. Selection Sort Script implementing the Selection Sort algorithm.
         2. Insertion Sort Script implementing the Insertion Sort algorithm.
         3. Shell Sort Script implementing the Shell Sort algorithm.
         4. Merge Sort Script implementing the Merge Sort algorithm.
         5. Quick Sort Script implementing the Quick Sort algorithm.
      3. Trees Folder with the algorithms to manage the ADT Trees.
         1. Traversal Script implementing the Transversal algorithm for binary trees, it includes the preorder, inorder and postorder structure walkthrough.

   3. Data Structures Folder with the main data structures implemented to support the ADTs in the library.

      1. Array List Script implementing the Array List data structure.
      2. Single Linked List Script implementing the Single Linked List data structure.
      3. Double Linked List Script implementing the Double Linked List data structure.
      4. Heap Script implementing the Heap data structure.
      5. Indexed Heap Script implementing the Indexed Heap data structure.
      6. Indexed MinPQ Node Script implementing the Indexed MinPQ Node data structure to support the Indexed Heap implementation.
      7. Separate Chaining Hash Table Script implementing the Separate Chaining Hash Table data structure.
      8. Linear Probing Hash Table Script implementing the Linear Probing Hash Table data structure.
      9. Map Entry Script implementing the Map Entry/Value data structure to support the Hash Table implementation.
      10. Binary Search Tree (BST) Script implementing the Binary Search Tree (BST) data structure for the ADT Ordered Map.
      11. BST Node Script implementing the BST Node data structure to support the Binary Search Tree (BST) data structure.
      12. Red Black Tree (RBT) Script implementing the Red Black Tree (RBT) data structure for the ADT Ordered Map.
      13. RBT Node Script implementing the RBT Node data structure to support the Red Black Tree (RBT) data structure.
      14. Adjacency List Script implementing the Adjacency List data structure for ADT Graph.
      15. Edge Script implementing the Edge data structure to support the Graph's Adjacency List implementation.

   4. Utils Folder with the main utilities implemented to support the ADTs in the library.

      1. Error Handling Script implementing the Error Handling utility for all the libraries.

2. Test Folder with the tests for the library.

   1. List Scripts to evaluate the ADT Lists.
   2. Queue Scripts to evaluate the ADT Queue.
   3. Stack Scripts to evaluate the ADT Stack.
   4. Map Scripts to evaluate the ADT Map.
   5. Ordered Map Scripts to evaluate the ADT Ordered Map.
   6. Binary Search Tree Scripts to evaluate the ADT Binary Search Tree.
   7. MinPQ Scripts to evaluate the ADT Min Priority Queue.
   8. Graph Scripts to evaluate the ADT Graph.

NOTE: DISClib uses the the config.py scripts to configure the library's build path and allows the Python interpreter to find the relative path in any OS condition.

Back to top

Implementation

This library was built with the following technologies:

• Mac OS and Windows 10 for operating system.
• VS code for the IDE.
• Python 3.6 for the programming language.
• Pytest for the testing framework.

As a design principle DISClib minimize the use of Python external libraries in its implementation.

Finally, DISClib works between Python 3.6 and Python 3.9 versions.

Back to top

Getting Started

This section contains the steps to get started with the library. As is the case with any other library, you need to install the library and then import it in your project.

As the library is not Object Oriented, you need to import the library in your project as a module using the following steps in Installation.

Back to top

Prerequisites

As a design principle DISClib minimize the use of Python external libraries in its implementation.

To execute the tests in the Test folder, you need to install the Pytest package.

pip install pytest

Back to top

Installation

For the moment the DISClib is available as a local dependency in your project. To install it you can follow the next steps:

1. Create a new project folder.

2. Clone the repo with the command:

   git clone https://github.com/ISIS1225DEVS/ISIS1225-Lib.git

3. Move the DISClib folder to the project folder.

4. Create a new Python file in the project folder.

5. Import the necessary DISClib ADT modules into your project with the command:

    from DISClib.ADT import list as lt
    from DISClib.ADT import map as mp

6. Start coding!

Back to top

Usage

DISCLib is a library that provides a set of ADT's to support the development and use of algorithms. Its intended as a teaching tool in the course ISIS1225-Estructuras de Datos y Algoritmos.

To check the laboratories repositories, go to the following links:

• ISIS1225-SampleMVC MVC pattern introduction laboratory.
• ISIS1225-SampleConflicts GitHub conflicts solution laboratory.
• ISIS1225-SampleList ADT List laboratory.
• ISIS1225-SampleSorts ADT List sorting algorithms laboratory.
• ISIS1225-sampleMap ADT Map laboratory.
• ISIS1225-SampleCollision ADT Map collision method laboratory.
• ISIS1225-SampleTree ADT Ordered Map (BST and RBT) laboratory.
• ISIS1225-sampleGraph ADT Graph laboratory.
• ISIS1225-SampleAlgorithm ADT Graph algorithms laboratory.
• ISIS1225-Reto1 First Challenge repository.
• ISIS1225-Reto2 Second Challenge repository.
• ISIS1225-Reto3 Third Challenge repository.
• ISIS1225-Reto4 Fourth Challenge repository.

Back to top

Contact and support

For further information and contact, use the following links:

• Official Repository DISClib.
• Repository for Demo and Examples.

If you require further information, please contact us via this email

Back to top

Roadmap

The Road so far led us to complete the following features:

• To include examples for all modules in the repository Demo and Examples.
• To clean some code and make it more readable.
• To standardize the functions and variables names throughout the library.
• To improve the library the documentation.
• To implement the Adjacency Matrix data structure for the ADT Graph.

See the open issues for a full list of proposed features (and known issues).

Back to top

Contributing

Contributions are what make the open-source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this project better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

1. Fork the Project.
2. Create your Feature Branch (git checkout -b feature/AmazingFeature).
3. Commit your Changes (git commit -m 'Add some AmazingFeature').
4. Push to the Branch (git push origin feature/AmazingFeature).
5. Open a Pull Request.

Back to top

License

Copyright 2020, Departamento de sistemas y Computación, Universidad de Los Andes. Developed for the class "ISIS1225 - Estructuras de Datos y Algoritmos" or "ISIS1225 - Data Structure and Algorithms" in english.

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more information go to GNU ORG.

Back to top

Authors and acknowledgment

• Dario Correal is the original author and main developer of the library.
• Santiago Arteaga is a contributor and repository administrator.
• Luis Florez is a contributor and developed examples and tutorials for the library.

Back to top