Path-finding Animations of Proposed Algorithms

[vicennial]

Algorithms

• [x] Breadth First Search
  • [x] Binary Breadth First Search
  • [x] Edward Moore's Algorithm

Terminology

Node Color	Meaning
No color	Node has not been found yet.
Grey	Node found and added to queue but hasn’t been processed yet.
Blue	Node is currently being processed.
Red	Node has been processed (But might be processed again in the future).
Green	Node is part of optimal path.

[vicennial]

Breadth First Search

Query

SELECT * FROM BreadthFirstSearch(‘ SELECT id, source, target, cost, reverse_cost FROM edge_table ’ , 1, 12, directed := false);

Source = 1, Target = 12

Animation

[vicennial]

Binary Breadth First Search

Set Up Additional Table

DROP TABLE IF EXISTS road_works; CREATE TABLE road_works( id INT PRIMARY KEY NOT NULL, source INT NOT NULL, target INT NOT NULL, road_work INT NOT NULL, reverse_road_work INT NOT NULL );

INSERT INTO road_works VALUES (1,1,2,0,0),(2,2,3,-1,1),(3,3,4,-1,0),(4,2,5,0,0),(5,3,6,1,-1),(6,7,8,1,1),(7,8,5,0,0),(8,5,6,1,1),(9,6,9,1,1),(10,5,10,1,1),(11,6,11,1,-1),(12,10,11,0,-1),(13,11,12,1,-1),(14,10,13,1,1),(15,9,12,0,0),(16,4,9,0,0),(17,14,15,0,0),(18,16,17,0,0);

Query

SELECT * FROM BinaryBreadthFirstSearch(‘ SELECT et.id, et.source, et.target, rw.road_work as cost, rw.reverse_road_work as reverse_cost FROM edge_table et, road_works rw WHERE et.source = rw.source AND et.target = rw.target; ’ , 8, 12, directed := false);

Source = 8, Target = 12

Additional Terminology

Edge Color	Meaning
Blue	Edge does not have ongoing road work. It is considered to have a weight of zero by the algorithm.
Red	Edge has ongoing road work. It is considered to have a weight of one by the algorithm.

Animation

[vicennial]

Edward Moore's Algorithm

Set Up Data

DROP TABLE IF EXISTS sample_edge_table;

CREATE TABLE sample_edge_table( id INT PRIMARY KEY NOT NULL, source INT NOT NULL, target INT NOT NULL, cost REAL NOT NULL, reverse_cost REAL NOT NULL );

INSERT INTO sample_edge_table VALUES (1,1,2,'Infinity',2),(2,3,2,-3,'Infinity'),(3,3,4,'Infinity',6),(4,2,5,5,'Infinity'),(5,3,6,'Infinity',5),(6,7,8,3,'Infinity'),(7,8,5,'Infinity',7),(8,5,6,'Infinity',4),(9,6,9,'Infinity',-1),(10,5,10,2,'Infinity'),(11,6,11,'Infinity',-2),(12,10,11,'Infinity',-3),(13,11,12,'Infinity',-2),(14,10,13,'Infinity',5),(15,9,12,'Infinity',6),(16,4,9,3,'Infinity');

Query

SELECT * FROM EdwardMoore(‘ SELECT id, source, target, cost, reverse_cost FROM sample_edge_table ’ , 12, 8, directed := true);

Source = 12, Target = 8.

Animation