# Graph

[data structure](/web/appendix/data.md) ⟩ Graph

{% tabs %}
{% tab title="🔸 屬性" %}

* [.findPath()](/web/appendix/data/graph/.findpath.md)
* [.findShortestPath()](/web/appendix/data/graph/.findshortestpath.md)
  {% endtab %}

{% tab title="👥 相關" %}

* [Queue](/web/appendix/data/queue.md) - used in [**breadth-first search**](/web/appendix/data/graph/bfs.md).
* [Stack](/web/appendix/data/stack.md) - used in [**depth-first search**](/web/appendix/data/graph/dfs.md).
* [WaitingList](/web/appendix/data/waitinglist.md) - a Stack or Queue, used to unify breadth/depth-first search.
  {% endtab %}

{% tab title="⬇️ 應用" %}

* [Mail Robot](/web/appendix/data/graph/ex/robot.md)
  {% endtab %}

{% tab title="📗 參考" %}

* [ ] Eloqent JavaScript ⟩ [Ch. 7 Project: A Robot](https://eloquentjavascript.net/07_robot.html) ⭐️ 
* [ ] MakeUseOf ⟩ [A Guide to the Graph Data Structure](https://www.makeuseof.com/graph-data-structure/)
* [ ] simplilearn ⟩ [Your One-Stop Solution For Graphs In Data Structures](https://www.simplilearn.com/tutorials/data-structure-tutorial/graphs-in-data-structure)
* [ ] VisuAlgo ⟩ [GRAPH TRAVERSAL (DFS/BFS)](https://visualgo.net/en/dfsbfs?slide=1) 
  {% endtab %}

{% tab title="🛠 工具" %}

* npm ⟩ [dijkstrajs](https://www.npmjs.com/package/dijkstrajs) - Dijkstra's single-source shortest-paths algorithm.
  {% endtab %}
  {% endtabs %}

## implementations

{% tabs %}
{% tab title="JS" %}

* replit > [Graph (js)](https://replit.com/@pegasusroe/Graph-js#Graph/Graph.js)

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

💈範例：

```javascript
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);
    });

}
```

{% endtab %}

{% tab title="Swift" %}

* replit ⟩ [Graph (Swift)](https://replit.com/@pegasusroe/Graph-class#Graph/Graph/Graph.swift) 

```swift
// swift
```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lochiwei.gitbook.io/web/appendix/data/graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.