README.md

Path-Finder

Path Finder Algorithm for Network Graph

Prerequisites

Path-Finder is written in Python 3 and no external library needed.

The Algorithm

Data Structure

This project based on these 4 class; Container, Node, Route, and main.

Container is a singleton and responsible to create and store Node objects.

Node objects represents unique node on the graph. It stores route objects that visited the node itself. It also evaluates the route with the minimum distance.

Route objects are representing the path that are unique. It contains path data with related node objects.

Process

For path finding algorithm there are a few well-known algorithm. But in this project I aimed to develop a new approach.

This project has 3 main feature:

1. Divide and Conquer
2. Simplifier
3. Infinite Loop Detection

1. Divide amd Conquer

It is the main approach of this path-finder algorithm. When a node has more than one edge, It duplicates the arrived route as much as edge count.

Route and Path Changes Related to Time

T       Route       Path (Visited Nodes)

0       Route #1    -

1       Route #1    1

2       Route #1    1, 2

3       Route #1    1, 2, 4
        Route #2    1, 2, 3

2. Simplifier

If a node have more than one arrived route, it removes all routes but the shortest distance. Thus, it prevents the parabolic rise of number of route objects and increases the performance.

As shown in the graph, at the Node 5, Route #1 and Route #3 arrived. Route #1 has been deleted because Route #3 travels a shorter distance. Another important issue in this section is that Route #1 and Route #3 do not have to reach the Node 5 at the same time. Even if they arrive in different time zones, the related Route is deleted.

Route and Path Changes Related to Time

T       Route       Path (Visited Nodes)

.
.
        
4       Route #1    1, 2, 4, 5
        Route #2    1, 2, 3, ..
        Route #3    1, 2, 3, 5

5       Route #1    (Removed)
        Route #2    1, 2, 3, ..
        Route #3    1, 2, 3, 5, ..

3. Infinite Loop Detection

Avoiding infinite loops was an important part of the project. Therefore, each route object contains a list of nodes it has passed through before. Thus, the Route object is deleted when the same node is visited again.

Usage

You can call run.sh with File Path, Initial Node ID and Target Node ID parameters.

Linux

./run.sh basic.txt 1 8

MacOS

bash run.sh basic.txt 1 8

Sample Graph

There are two samples under the files/sample directory.

Here is the visual of the network graph that sample.txt represent:

Calling Path Finder with Sample Data

bash run.sh file/sample/basic.txt 1 8

Solution

26

Repository

This project available at eminsafa/Path-Finder

License

MIT