graphnode.ts

export class GraphNode<T> {
    private readonly $item: T;
    private readonly $children: GraphNode<T>[] = [];
    private readonly $parents: GraphNode<T>[] = [];

    public constructor(item: T) {
        this.$item = item;
    }
    
    public get item(): T {
        return this.$item;
    }

    public addParent(node: GraphNode<T>): GraphNode<T> {
        this.$parents.push(node);
        return this;
    }

    public addChild(node: GraphNode<T>): GraphNode<T> {
        this.$children.push(node);
        return this;
    }

    public *children(): Iterable<T> {
        for (const child of this.$children) {
            yield child.$item;
        }
    }

    public *parents(): Iterable<T> {
        for (const parent of this.$parents) {
            yield parent.$item;
        }
    }

    public *descendants(): Iterable<T> {
        for (const child of this.$children) {
            yield child.$item;
        }

        for (const child of this.$children) {
            yield* child.children();
        }
    }

    public *ancestors(): Iterable<T> {
        for (const parent of this.$parents) {
            yield parent.$item;
        }

        for (const parent of this.$parents) {
            yield* parent.ancestors()
        }
    }

    public hasChildren(): boolean {
        return this.$children.length > 0;
    }

    public hasParents(): boolean {
        return this.$parents.length > 0;
    }
}

test.ts

import { GraphNode } from './index';

interface Index<T = string[]> {
    [key: string]: T | undefined;
}

interface Link {
    id: string;
    parent: string;
    child: string;
}

interface Store<T> {
    items: Index<T>;

    links: Index<Link>;
    linksByChild: Index;
    linksByParent: Index;
}

interface Item {
    id: string;
    name: string;
}

function makeStore($items: Item[], $links: Link[]): Store<Item> {
    const items: Index<Item> = {};
    const links: Index<Link> = {};
    const linksByChild: Index = {};
    const linksByParent: Index = {};

    for (const item of $items) {
        items[item.id] = item;
    }

    for (const link of $links) {
        links[link.id] = link;

        const linksByChildIndex = linksByChild[ link.child ] || [];
        linksByChildIndex.push(link.id);
        linksByChild[link.child] = linksByChildIndex;

        const linksByParentIndex = linksByParent[ link.parent ] || [];
        linksByParentIndex.push(link.id);
        linksByParent[link.parent] = linksByParentIndex;
    }

    return {
        items,
        links,
        linksByChild,
        linksByParent
    }
}

const ITEMS: Item[] = [
    { id: 'top-1', name: 'Top 1' },
    { id: 'top-2', name: 'Top 2' },

    { id: 'a', name: 'A' },
    { id: 'b', name: 'B' },
    { id: 'c', name: 'C' },

    { id: 'l-1', name: 'L1' },
    { id: 'l-2', name: 'L2' },
    { id: 'l-3', name: 'L3' },
    { id: 'l-4', name: 'L4' },

    { id: 'x-1', name: 'X1' },
    { id: 'x-2', name: 'X2' },
    { id: 'x-3', name: 'X3' },
    { id: 'x-4', name: 'X4' },
    { id: 'x-5', name: 'X5' },
    { id: 'x-6', name: 'X6' },

    { id: 'z-01', name: 'Z01'},
    { id: 'z-02', name: 'Z02'},
    { id: 'z-03', name: 'Z03'},
    { id: 'z-04', name: 'Z04'},
    { id: 'z-05', name: 'Z05'},
    { id: 'z-06', name: 'Z06'},
    { id: 'z-07', name: 'Z07'},
    { id: 'z-08', name: 'Z08'},
    { id: 'z-09', name: 'Z09'},
    { id: 'z-10', name: 'Z10'},
    { id: 'z-11', name: 'Z11'},
    { id: 'z-12', name: 'Z12'},
    { id: 'z-13', name: 'Z13'},
    { id: 'z-14', name: 'Z14'},
    { id: 'z-15', name: 'Z15'},
    { id: 'z-16', name: 'Z16'},
    { id: 'z-17', name: 'Z17'},
    { id: 'z-18', name: 'Z18'},
    { id: 'z-19', name: 'Z19'},
    { id: 'z-20', name: 'Z20'},
    
    { id: 'g-1', name: 'Group 1'}
];

function makeIdGet(prefix: string = '') {
    let id = 0;
    return () => `${prefix}-${++id}`;
}

let linkId = makeIdGet('link');
const LINKS: Link[] = [
    { id: linkId(), parent: 'top-1', child: 'a' },
    { id: linkId(), parent: 'top-1', child: 'b' },
    { id: linkId(), parent: 'top-2', child: 'b' },
    { id: linkId(), parent: 'top-2', child: 'c' },

    { id: linkId(), parent: 'a', child: 'l-1' },
    { id: linkId(), parent: 'b', child: 'l-1' },
    { id: linkId(), parent: 'b', child: 'l-2' },
    { id: linkId(), parent: 'c', child: 'l-2' },

    { id: linkId(), parent: 'a', child: 'l-3' },
    { id: linkId(), parent: 'c', child: 'l-4' },

    { id: linkId(), parent: 'l-3', child: 'x-1' },
    { id: linkId(), parent: 'l-1', child: 'x-2' },
    { id: linkId(), parent: 'l-1', child: 'x-3' },
    { id: linkId(), parent: 'l-2', child: 'x-4' },
    { id: linkId(), parent: 'l-2', child: 'x-5' },
    { id: linkId(), parent: 'l-4', child: 'x-6' },

    { id: linkId(), parent: 'l-4', child: 'z-01' },
    { id: linkId(), parent: 'l-4', child: 'z-02' },
    { id: linkId(), parent: 'l-4', child: 'z-03' },
    { id: linkId(), parent: 'l-4', child: 'z-04' },
    { id: linkId(), parent: 'l-4', child: 'z-05' },
    { id: linkId(), parent: 'l-4', child: 'z-06' },
    { id: linkId(), parent: 'l-4', child: 'z-07' },
    { id: linkId(), parent: 'l-4', child: 'z-08' },
    { id: linkId(), parent: 'l-4', child: 'z-09' },
    { id: linkId(), parent: 'l-4', child: 'z-10' },

    { id: linkId(), parent: 'l-4', child: 'z-11' },
    { id: linkId(), parent: 'l-4', child: 'z-12' },
    { id: linkId(), parent: 'l-4', child: 'z-13' },
    { id: linkId(), parent: 'l-4', child: 'z-14' },
    { id: linkId(), parent: 'l-4', child: 'z-15' },
    { id: linkId(), parent: 'l-4', child: 'z-16' },
    { id: linkId(), parent: 'l-4', child: 'z-17' },
    { id: linkId(), parent: 'l-4', child: 'z-18' },
    { id: linkId(), parent: 'l-4', child: 'z-19' },
    { id: linkId(), parent: 'l-4', child: 'z-20' },

    { id: linkId(), parent: 'g-1', child: 'z-11' },
    { id: linkId(), parent: 'g-1', child: 'z-12' },
    { id: linkId(), parent: 'g-1', child: 'z-13' },
    { id: linkId(), parent: 'g-1', child: 'z-14' },
    { id: linkId(), parent: 'g-1', child: 'z-15' },
    { id: linkId(), parent: 'g-1', child: 'z-16' },
    { id: linkId(), parent: 'g-1', child: 'z-17' },
    { id: linkId(), parent: 'g-1', child: 'z-18' },
    { id: linkId(), parent: 'g-1', child: 'z-19' },
    { id: linkId(), parent: 'g-1', child: 'z-20' },
];

const store = makeStore(ITEMS, LINKS);

interface KeyedGraphNodes<T> {
    [key: string]: GraphNode<T>;
}
function buildTree<T extends { id: string }>(store: Store<T>): KeyedGraphNodes<T> {
    const nodes: { [key: string]: GraphNode<T> } = {}

    const items: T[] = Object.keys(store.items)
        .map(id => store.items[id])
        .filter((o?: T): o is T => o != null)

    for (const item of items) {
        nodes[item.id] = new GraphNode(item);
    }

    const links: Link[] = Object.keys(store.links)
        .map(id => store.links[id])
        .filter((o?: Link): o is Link => o != null);

    for (const link of links) {
        const child = nodes[link.child];
        const parent = nodes[link.parent];
        
        child.addParent(parent);
        parent.addChild(child);
    }

    return nodes;
}

const tree = buildTree(store);

// console.log(tree);

// console.log(...tree['top-1'].descendants());
// console.log(...tree['x-2'].ancestors());

// console.log();

// console.log([...tree['z-10'].ancestors()].map(i => i.name).join(', '))
// console.log([...new Set(tree['z-10'].ancestors())].map(i => i.name).join(', '))

for (const key of Object.keys(tree)) {
    const node = tree[key];

    console.log(node.item.name, [...node.ancestors()].map(i => i.name).join(', '));
}

console.log();
console.log();

for (const key of Object.keys(tree)) {
    const node = tree[key];

    console.log(node.item.name, [...new Set(node.ancestors())].map(i => i.name).join(', '));
}