📦Graph

data structure ⟩ Graph

🔸 屬性

• .findPath()

• .findShortestPath()

👥 相關

• Queue - used in breadth-first search.

• Stack - used in depth-first search.

• WaitingList - a Stack or Queue, used to unify breadth/depth-first search.

⬇️ 應用

• Mail Robot

📗 參考

• Eloqent JavaScript ⟩ Ch. 7 Project: A Robot ⭐️

• MakeUseOf ⟩ A Guide to the Graph Data Structure

• simplilearn ⟩ Your One-Stop Solution For Graphs In Data Structures

• VisuAlgo ⟩ GRAPH TRAVERSAL (DFS/BFS)

🛠 工具

• npm ⟩ dijkstrajs - Dijkstra's single-source shortest-paths algorithm.

implementations

JS

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

}

Swift

• replit ⟩ Graph (Swift)

// swift