📦Graph

data structure ⟩ Graph

implementations

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 };

💈範例：

PreviousWaitingListNext.findPath()

Last updated

Was this helpful?