๐ฆGraph
data structure โฉ Graph
Queue - used in breadth-first search.
Stack - used in depth-first search.
WaitingList - a Stack or Queue, used to unify breadth/depth-first search.
npm โฉ dijkstrajs - Dijkstra's single-source shortest-paths algorithm.
implementations
replit > Graph (js)
const { log } = console;
const { Queue } = require('./Queue.js');
const { WaitingList } = require('./WaitingList.js');
// โญ Graph
// 2022.12.29 - 13:44 - first version
// โ: mutating
// -----------------------------------------------------------------
// ๐ฆ Graph.edgesToAdjacencyList()
// -----------------------------------------------------------------
// ๐ธ .heads - "start" nodes of edges
// ๐ธ ,tails - "end" nodes of edges
// ๐ธ .nodes - all nodes
// ๐น .neighborsOf() - neighbors of a node
// ๐น .addEdge() โ - (mutating)
// ๐น .areNeighbors() - check if two nodes are neighbors
// -----------------------------------------------------------------
// ๐น .findShortestPath() - shortest path between twe nodes
// ๐น .distance()
// -----------------------------------------------------------------
// ๐น .toString()
// ๐น .findPath() - can choose to use breadth-first or depth-first search
//
class Graph {
#adjacencyList;
// ๐ธ store edges (adjacency list)
//
// {
// A: { B: 1, C: 1 },
// B: { A: 1, C: 1 },
// }
//
#edges = Object.create(null);
// ------------
// tools
// ------------
// ๐ฆ Graph.edgesToAdjacencyList()
// [[ 'A', 'B' ], [ 'A', 'C' ]] -> { A: ['B', 'C'], B: ['A'], C: ['A'] }
static edgesToAdjacencyList(edges) {
// adjacency list
const list = Object.create(null);
edges.forEach(([start, end]) => {
if (!list[start]) list[start] = [];
if (!list[end]) list[end] = [];
if (!list[start].includes(end)) list[start].push(end);
if (!list[end].includes(start)) list[end].push(start);
});
return list;
}
// โญ constructor
//
// new Graph({ A: ['B','C','P'], B: ['A','T'] })
//
constructor(adjacencyList) {
this.#adjacencyList = adjacencyList;
for (const [start, ends] of Object.entries(adjacencyList)) {
ends.forEach(end => {
this.addEdge(start, end);
this.addEdge(end, start);
});
}
}
// ------------
// nodes
// ------------
// ๐ธ .heads
get heads() {
return new Set(Object.keys(this.#edges));
}
// ๐ธ tails
get tails() {
return new Set(Object.values(this.#edges).flatMap(obj => Object.keys(obj)));
}
// ๐ธ .nodes
get nodes() {
return new Set([...this.heads, ...this.tails]);
}
// ๐น .neighborsOf()
neighborsOf(start) {
return Object.keys(this.#edges?.[start] ?? {});
}
// ------------
// edges
// ------------
// ๐น .addEdge()
addEdge(start, end) {
if (!this.#edges[start]) this.#edges[start] = Object.create(null);
this.#edges[start][end] = 1; // default weight of edge
}
// ๐น .areNeighbors()
areNeighbors(start, end) {
return (this.#edges?.[start]?.[end]) ? true : false;
}
// ---------------------
// search algorithms
// ---------------------
// ๐น .findShortestPath()
findShortestPath(start, target, { debug = false }={}) {
const queue = new Queue(); // (queue) nodes to visit
const path = Object.create(null); // (dict) save paths to nodes (self included)
// put `start` node into queue
queue.enqueue(start);
path[start] = [start]; // save path to `start`
// while queue is not empty
while (!queue.isEmpty) {
// debug
if (debug) {
queue.log();
log(path);
};
// pick first node (front) from queue
const front = queue.dequeue();
// if target is found, return path.
if (front === target) return path[front];
// else add unexplored neighbors to queue
const unexplored = this
.neighborsOf(front)
.filter(node => !queue.isExplored(node));
for (let child of unexplored) {
queue.enqueue(child);
path[child] = path[front].concat(child); // save path to child
}
}
// queue is empty, no possible path.
return null;
}
// ๐น .distance()
distance(v1, v2) {
return (this.findShortestPath(v1, v2)?.length ?? Infinity) - 1;
}
// ------------
// debug
// ------------
// ๐น .toString()
toString() {
return Object.entries(this.#adjacencyList)
.map(([start, ends]) => `${start}: [${ends}]`)
.join('\n');
}
// ๐น .findPath()
findPath(start, target, {
// log debug info if true
debug = false,
// search mode:
// โข 'breadth-first': shortest (default)
// โข 'depth-first'
mode = 'breadth-first',
} = {}) {
// choose stack or queue for waiting list
const waitinglistMode = {
'breadth-first': 'queue',
'depth-first': 'stack',
};
// nodes waiting to be explored
const waitingList = new WaitingList(waitinglistMode[mode]);
let current = null; // currently examined node
const visited = Object.create(null); // visited nodes (a dictionary)
const parent = Object.create(null); // parents of each node in path
// enqueue node
function enqueue(node) {
waitingList.enqueue(node); // put node in queue
visited[node] = true; // mark it as visited
parent[node] = current; // save its parent (`current`)
}
// initial setup
enqueue(start); // put `start` in queue
// debug
let i = 0;
const line = '-'.repeat(20);
// 1. while the queue is not empty
while (!waitingList.isEmpty) {
// debug info
if (debug) {
log(`[${i}] ${line}`);
log(`current: ${current}`);
log(waitingList.toString());
log(`visited: ${Object.keys(visited)}`);
i += 1;
}
// pick and examine first node in queue
current = waitingList.dequeue();
// 1.1 if `current` is `target`, path is found.
if (current === target) {
// construct the path
let node = target; // by starting at `target`
let path = [target];
// and following the parents back to `start`.
while (node = parent[node], node !== null) {
path.push(node);
}
return path.reverse();
}
// 1.2 `current` is not `target`,
// add unvisited neighbors to `queue`
this.neighborsOf(current)
.filter(node => !visited[node])
.forEach(node => enqueue(node));
}
// 2. `queue` empty and `target` not found,
// no path from `start` to `target`.
return null;
}
}
// export
module.exports = { Graph };๐็ฏไพ๏ผ
const { log } = console;
// โญ import
const { Graph } = require('../DataStructure/Graph.js');
// ---------------------------------------------------------------------------
function test_Graph() {
// โญ roads
const roads = [
"Alice's House-Bob's House", "Alice's House-Cabin",
"Alice's House-Post Office", "Bob's House-Town Hall",
"Daria's House-Ernie's House", "Daria's House-Town Hall",
"Ernie's House-Grete's House", "Grete's House-Farm",
"Grete's House-Shop", "Marketplace-Farm",
"Marketplace-Post Office", "Marketplace-Shop",
"Marketplace-Town Hall", "Shop-Town Hall"
];
// edges
const edges = roads.map(s => s.split('-').map(s => s[0]));
// [
// [ 'A', 'B' ], [ 'A', 'C' ],
// [ 'A', 'P' ], [ 'B', 'T' ],
// [ 'D', 'E' ], [ 'D', 'T' ],
// [ 'E', 'G' ], [ 'G', 'F' ],
// [ 'G', 'S' ], [ 'M', 'F' ],
// [ 'M', 'P' ], [ 'M', 'S' ],
// [ 'M', 'T' ], [ 'S', 'T' ]
// ]
// โญ nodes (dictionary)
const nodeName = Object.create(null);
roads
.flatMap(s => s.split('-').map(s => [s[0], s]))
.forEach(([char, name]) => {
if (!nodeName[char]) nodeName[char] = name;
});
// {
// A: "Alice's House",
// B: "Bob's House",
// C: 'Cabin',
// P: 'Post Office',
// T: 'Town Hall',
// D: "Daria's House",
// E: "Ernie's House",
// G: "Grete's House",
// F: 'Farm',
// S: 'Shop',
// M: 'Marketplace'
// }
// โญ adjacency list
const list = Graph.edgesToAdjacencyList(edges);
// {
// A: [ 'B', 'C', 'P' ],
// B: [ 'A', 'T' ],
// C: [ 'A' ],
// P: [ 'A', 'M' ],
// T: [ 'B', 'D', 'M', 'S' ],
// D: [ 'E', 'T' ],
// E: [ 'D', 'G' ],
// G: [ 'E', 'F', 'S' ],
// F: [ 'G', 'M' ],
// S: [ 'G', 'M', 'T' ],
// M: [ 'F', 'P', 'S', 'T' ]
// }
// โญ graph
const graph = new Graph(list);
;[
// graph
// -----------------
`graph.toString()`,
// A: [B,C,P]
// B: [A,T]
// C: [A]
// P: [A,M]
// T: [B,D,M,S]
// M: [P,T,F,S]
// D: [T,E]
// S: [T,G,M]
// E: [D,G]
// G: [E,F,S]
// F: [G,M]
`graph.areNeighbors('A', 'B')`, // true
`graph.areNeighbors('A', 'D')`, // false
`graph.nodes`,
// Set(11) { 'A', 'B', 'C', 'P', 'T', 'D', 'E', 'G', 'F', 'S', 'M' }
// graph.findPath('M', 'E', { debug: true, mode: 'depth-first' }),
// graph.findPath('M', 'E', { debug: false }),
// breadth-first: [ 'M', 'F', 'G', 'E' ]
// depth-first : [ 'M', 'S', 'G', 'E' ]
`graph.findShortestPath('M', 'A', {debug: false})`, // [ 'M', 'P', 'A' ]
`graph.findShortestPath('G', 'C')`, // [ 'G', 'F', 'M', 'P', 'A', 'C' ]
`graph.findShortestPath('M', 'X')`, // null
`graph.distance('M', 'E')`, // 3
`graph.distance('G', 'A')`, // 4
`graph.distance('M', 'X')`, // Infinity
`graph.distance('X', 'M')`, // Infinity
].forEach(cmd => {
const value = eval(cmd);
log(value);
});
}replit โฉ Graph (Swift)
// swiftLast updated