Graph work

graph.ts

interface NodeMapping {
    [index: number]: {
        [index: number]: string
    }
}

class Graph {
    private graph: {[index: string]: string[]};

    constructor(labels: string[], map: NodeMapping, edges: [number, number][][])
    {
        this.graph = {};

        labels.forEach((label: string) => {
            this.graph[label] = []
        });

        edges.forEach((edge: [number, number][]) => {
            let a = edge[0];
            let b = edge[1];

            let vertexA = map[a[0]][a[1]]
            let vertexB = map[b[0]][b[1]]

            if (vertexA && vertexB) {
                this.graph[vertexA].push(vertexB)
            }
        });
    }

    getGraph()
    {
        return this.graph;
    }

    dfs(start: string)
    {
        let visited = {[start]: true};
        let path: {[x: string]: string} = {}

        this.graph[start].forEach((adjNode) => {
            if (!visited[adjNode]) {
                this.dfsExecute(adjNode, start, visited, path)
            }
        })

        return path;
    }

    bfs(start: string)
    {
        let visited = {[start]: true};
        let path: {[x: string]: string} = {}
        let nodes = [start];
        let bfsPath = [start];

        while(nodes.length > 0) {
            let nextNode = nodes.shift()

            if(!nextNode) {
                break;
            }

            this.graph[nextNode].forEach((adjNode) => {
                if (!visited[adjNode]) {
                    visited[adjNode] = true;

                    if (nextNode) {
                        bfsPath.push(adjNode);
                        nodes.push(adjNode);
                        path[adjNode] = nextNode;
                    }
                }
            })
        }

        return path;
    }

    dfsExecute(current: string, previous:string, visited: {[x: string]: boolean}, path: {[x: string]: string})
    {
        visited[current] = true;
        path[current] = previous;

        this.graph[current].forEach((adjNode) => {
            if (!visited[adjNode]) {
                this.dfsExecute(adjNode, current, visited, path)
            }
        })
    }

    getDfsPath(start: string, finish: string)
    {
        let dfs = this.dfs(start);
        let path: string[] = [];
        let current = finish;


        while(current !== start)
        {
            path.push(current);
            current = dfs[current];
        }

        if (path[0] !== start) {
            return [];
        }
 
        return path.reverse();
    }

    getBfsPath(start: string, finish: string)
    {
        let bfs = this.bfs(start);
        let path: string[] = [];
        let current = finish;

        while(current !== undefined)
        {
            path.push(current);
            current = bfs[current];
        }

        if (path[path.length - 1] !== start) {
            return [];
        }

        return path.reverse();
    }

    hasCircularReference()
    {
        let marked: {[x: string] : boolean} = {}
        let inStack: {[x: string] : boolean} = {}

        let dfsSearch = (node: string) => {
            marked[node] = true;
            inStack[node] = true;

            let nodes =  this.graph[node];

            for(let i = 0; i < nodes.length; i++) {
                let adjNode = nodes[i]

                if (!marked[adjNode]) {
                    if (dfsSearch(adjNode)) {
                        return true;
                    }
                }
                else if (inStack[node]) {
                    return true
                }
            }

            marked[node] = false;
            return false;
        }

        return dfsSearch(Object.keys(this.graph)[0]);
    }

    topologicalSort(start: string)
    {
        let marked: {[x: string]: boolean} = {}
        let postorder: string[] = [];

        let dfs = (node: string) => {
            marked[node] = true

            this.graph[node].forEach((adjNode) => {
                if (!marked[adjNode]) {
                    dfs(adjNode);
                }
            })

            postorder.push(node)
        }

        dfs(start);
        return postorder.reverse();
     }
}

class Node {
    private coordinates: [number, number];
    public label: string;

    constructor(label: string, coordinates: [number, number])
    {
        this.label = label;
        this.coordinates = coordinates;
    }
}

let labels: string[] = [];

let nodes: {
    [index: number]: {
        [index: number]: string
    }
} = {}

for(let i = 0; i < 15; i++) {
    if (nodes[Math.floor(i / 5)] === undefined) {
        nodes[Math.floor(i / 5)] = {[i % 5]: i.toString()}
    } else {
        nodes[Math.floor(i / 5)][i % 5] = i.toString();
    }

    labels.push(i.toString());
}

let edges: [number, number][][] = [
    [
        [0,0],[0,1]
    ],
    [
        [0,1], [0,2]
    ],
    [
        [0,2], [0,3]
    ],
    [
        [0,3], [0,4]
    ],
    [
        [0,0], [1,0]
    ],
    [
        [1,0], [1,1]
    ],
    [
        [1,0], [2,0]
    ],
    [
        [1,1], [2,1]
    ],
    [
        [2,1], [2,2]
    ],
    [
        [2,2], [2,3]
    ],
    [
        [2,3], [2,4]
    ],
    [
        [0,2], [1,2]
    ],
    [
        [1,2], [2,2]
    ],
    [
        [0,3], [1,3]
    ],
    [
        [0,4], [1,4]
    ],
    [
        [1,4], [2,4]
    ]
]

let graph = new Graph(labels, nodes, edges);

// console.log(graph.getBfsPath('0', '14'));
// console.log(graph.getBfsPath('14', '0'));
// console.log(graph.getBfsPath('0', '8'));
// console.log(graph.hasCircularReference());
console.log(graph.topologicalSort('0'));