TreaTS

The Route Exploration Algorithm implemented in TypeScript.

Table of Contents

• Project Outline
• Prerequisites
• Getting Started
• Questions & Answers
• License Information

Project Outline

TreaTS is built entirely with the purpose to explore the possibilities of BFS to produce route variations to allow better understanding of a given graph. The idea started back then when I was a nobody (and still) learning the Dart language for the very first time. I got my hands on it and learn a few of it's characteristics within 2 weeks of learning.

I then decided to work on a simple calculator that make use of The Shunting Yard Algorithm. It really blows my mind, thus inspired me to work on something that would perform well to process a queue in cycles. At first I thought I would be foolish to try to solve a problem like this because everyone know that there's no place for such thing like TreaTS, ever. And no, any Shortest Path Finding Algorithm will always win no matter what because there is a real need for it.

But then I learned a few stuff and found some use cases that could possibly render this whole idea of being able to create route variations into something more than allowing us to find the shortest route possible. And for this, I'll work on my thesis further to elaborate on the specifics. For now, I'll keep developing this library further to find every weaknesses and design issues.

Prerequisites

• Node.js version 12 or higher.
• And the rest of the development dependencies that can be found on package.json

Getting Started

Installing

npm install @ronanharris09/treats

Usage

• Transform 2 Dimensional Matrix of Numbers into Pairs

  import { transform } from "@ronanharris09/treats"
  
  const matrix: Array<Array<number>> = [ [...], [...], [...] ];
  const pairs: Array<Pair> = transform(matrix)

• Explore the Transformed Pairs

  import { explore } from "@ronanharris09/treats"
  
  const pairs: Array<Pair> = [ {...}, {...}, {...} ]
  const explored: Array<Pair> = explore(matrix)

• Backtrack the Explored Pairs

  import { split, backtrack } from "@ronanharris09/treats"
  
  const explored: Array<Pair> = [ {...}, {...}, {...} ]
  const preprocess: PairGroup = split(explored)
  const routes: Array<Array<Pair>> = backtrack(preprocess)

Questions & Answers

Most questions below are prepared by myself and are probably not related to the algorithm implemented within.

• What are the main inspiration of the algorithm ?
  Answer : BFS. I like the way how BFS style of path exploration allows for a better understanding of a specific graph.

• How does this library work ?
  Answer : TreaTS are composed of a two main process, one of graph exploration and graph backtrack exploration. Exploration are defined as an array of X->Y pairs representing every cycle of the exploration process itself. Every pair on the queue are added to the visited stack as long as Y is not approaching X and Y is not a known X. The second part is the route creation process that will try to backtrack the exploration result to produce as much route variations available.

• Where can I ask for some other questions ?
  Answer : Please do and make use of the issue board to write your any of your questions. I'll try my best to answer in a timely fashion.

License Information

This project is licensed under GNU General Public License v2.0 only. You may read the full copy of the license at COPYING file, or by visiting https://www.gnu.org/licenses/old-licenses/gpl-2.0-standalone.html. For further clarity, the SPDX-License-Identifier is GPL-2.0-only.

Copyright (C) 2021 Ronan Harris
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; version 2.

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 details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.