I'm currently trying to build an interactive technology tree for Stellaris. Which normally doesn't come with a tree view. Stellaris is like Civilization 5, where the tree isn't actually a tree, as it has cycles.Take Civilization 5, Writing is a parent to Philosophy, and Drama and Poetry, which are both parents to Theology. This makes the following graph:          Philosophy        TheologyWriting  Drama and Poetry In the example above, Writing is a root of the graph, which is the first column, and so has a level of 0. Philosophy, and Drama and Poetry are level 1, and Theology is level 2.And so I build the following to build the graph data structure to later display this. This is mainly intended to take an easy to read node list with possible parents and children links in them, and build the graph for me.I've not used TypeScript before, and so tried my best with the type system, however I'm unsure if I've used it correctly. Especially with sub classing the graph and the node.interface IBuildNode<TValue> {    id: string;    data?: TValue;    parents?: Array<string>;    children?: Array<string>;}interface INode<TValue> {    id: string;    data: TValue;    parents: {[key: string]: INode<TValue>};    children: {[key: string]: INode<TValue>};    _default: boolean;    Delete(): void;    AddParent(parent: INode<TValue>): void;    AddChild(child: INode<TValue>): void;}class GraphNode<TValue> implements INode<TValue> {    id: string;    data: TValue;    parents: {[key: string]: INode<TValue>};    children: {[key: string]: INode<TValue>};    _default: boolean;    constructor(id: string,                data: any = null,                default_: boolean = true) {        this.id = id;        this.data = data;        this.parents = {};        this.children = {};        this._default = default_;    }    AddParent(parent: INode<TValue>): void {        this.parents[parent.id] = parent;        parent.children[this.id] = this;    }    AddChild(child: INode<TValue>): void {        this.children[child.id] = child;        child.parents[this.id] = this;    }    Delete(): void {        for (let parent in this.parents) {            delete this.parents[parent].children[this.id];        }        for (let child in this.children) {            delete this.children[child].parents[this.id];        }    }}class Graph<TValue> {    private nodes: {[key: string]: INode<TValue>};    constructor(nodes: IBuildNode<TValue>[] = [],                wipeDefault: boolean = true) {        this.nodes = {};        for (let node of nodes) {            let gNode = this.GetDefaultNode(node.id);            gNode.data = node.data;            gNode._default = false;            for (let parent of (node.parents || [])) {                this.GetDefaultNode(parent).AddChild(gNode);            }            for (let child of (node.children || [])) {                this.GetDefaultNode(child).AddParent(gNode);            }        }        if (wipeDefault) {            for (let nodeId of this.GetDefaultIds()) {                this.DeleteNode(nodeId);            }        }    }    protected BuildNode(nodeId: string) : INode<TValue> {        return new GraphNode<TValue>(nodeId);    }    GetNode(nodeId: string) : INode<TValue> {        if (this.nodes.hasOwnProperty(nodeId)) {            return this.nodes[nodeId];        }        return null;    }    GetDefaultNode(nodeId: string) : INode<TValue> {        if (this.nodes.hasOwnProperty(nodeId)) {            return this.nodes[nodeId];        }        let node = this.BuildNode(nodeId);        this.nodes[nodeId] = node;        return node;    }    DeleteNode(nodeId: string) : void {        this.nodes[nodeId].Delete();        delete this.nodes[nodeId];    }    GetDefaultIds() : Array<string> {        let ret : Array<string> = [];        for (let nodeId in this.nodes) {            let node = this.nodes[nodeId];            if (node._default) {                ret.push(nodeId);            }        }        return ret;    }    GetDefault() : Array<INode<TValue>> {        let ret : Array<INode<TValue>> = [];        for (let nodeId in this.nodes) {            let node = this.nodes[nodeId];            if (node._default) {                ret.push(node);            }        }        return ret;    }    GetRoots() : Array<INode<TValue>> {        let ret : Array<INode<TValue>> = [];        for (let nodeId in this.nodes) {            let node = this.nodes[nodeId];            if (Object.keys(node.parents).length == 0) {                ret.push(node);            }        }        return ret;    }}class TreeNode<TValue> extends GraphNode<TValue> {    level: number;    parents: {[key: string]: TreeNode<TValue>};    children: {[key: string]: TreeNode<TValue>};    constructor(id: string,                data: any = null,                default_: boolean = true) {        super(id, data, default_);        this.level = 0;    }    SetLevel(): void {        let level: number = -1;        for (let parentId in this.parents) {            let parent = this.parents[parentId];            level = Math.max(level, parent.level);        }        level++;        this.level = level;        for (let childId in this.children) {            let child = this.children[childId];            if (child.level >= level) {                child.SetLevel();            }        }    }    AddParent(parent: INode<TValue>): void {        super.AddParent(parent);        this.SetLevel();    }    AddChild(child: TreeNode<TValue>): void {        super.AddChild(child);        child.SetLevel();    }    Delete(): void {        for (let parentId in this.parents) {            delete this.parents[parentId].children[this.id];        }        for (let childId in this.children) {            let child = this.children[childId];            delete child.parents[this.id];            child.SetLevel();        }    }}class TreeGraph<TValue> extends Graph<TValue> {    protected BuildNode(nodeId: string) : INode<TValue> {        return new TreeNode<TValue>(nodeId);    }}let graph : IBuildNode<string>[] = [    {        id: '0',        data: 'Writing'    },    {        id: '1',        data: 'Philosophy',        parents: ['0']    },    {        id: '2',        data: 'Drama and Poetry',        parents: ['0']    },    {        id: '3',        data: 'Theology',        parents: ['1', '2']    }];let treeGraph = new TreeGraph(graph);console.debug(treeGraph.GetNode('0'));console.debug(treeGraph.GetNode('1'));console.debug(treeGraph.GetNode('2'));console.debug(treeGraph.GetNode('3'));console.debug(treeGraph.GetRoots());
Implementing a 'TreeGraph' which extends a normal graph
graph;typescript
Calling this a tree isn't quite correct. The term you are looking for is a directed graph. Generally one would accordingly not talk about parent and child but precedessor and successor or incoming and outgoing nodes.As such talking about Levels is also possibly not the best naming here. What it represents is the maximum amount of nodes on a path to the node you see. Maybe longestPath would be better for a general structure...Generally speaking: the code you use looks well structured and clean to me, though not optimized for performance.That's just fine as is. One thing I personally wouldn't do is the IBuildNode interface. I'd instead expose additional constructors.Another thing I'd do differently is the type of the node-id. This may be overzealous, but I prefer numerical ids for about everything. Finally the methods GetRoots(), GetDefaultIds() and GetDefault() all return information that I would precompute when modifying the graph. Also there are no comments on this, which makes maintenance needlessly difficult :)