Skip to content
Snippets Groups Projects
graph.ts 9.55 KiB
import { Node, NodeData, SimNodeData } from "./node";
import { Link, LinkData, SimLinkData } from "./link";
import { NodeType, NodeTypeData } from "./nodetype";
import { SerializableItem } from "../serializableitem";

export interface Coordinate2D {
    x: number;
    y: number;
}

export interface Coordinate3D extends Coordinate2D {
    z: number;
}

export interface GraphData {
    nodes: NodeData[];
    links: LinkData[];
    objectGroups?: NodeTypeData[];
}

export interface SimGraphData {
    nodes: SimNodeData[];
    links: SimLinkData[];
    objectGroups: NodeTypeData[];
}

export interface GraphContent {
    nodes: Node[];
    links: Link[];
    objectGroups?: NodeType[];
}

/**
 * Basic graph data structure.
 */
export class Graph
    extends SerializableItem<GraphData, SimGraphData>
    implements GraphContent
{
    public nodes: Node[];
    public links: Link[];
    public objectGroups: NodeType[];
    private defaultGroup: NodeType;
    public initialized: boolean;

    public idToObjectGroup: Map<number, NodeType>;
    private idToNode: Map<number, Node>;
    private idToLink: Map<number, Link>;

    protected nextNodeId = 0;
    protected nextLinkId = 0;
    protected nextObjectGroupId = 0;

    /**
     * Creates a new Graph object.
     * Make sure the nodes and links are connected to the correct objects before calling this method!
     */
    constructor(data?: GraphContent) {
        super(0);

        if (data === undefined) {
            this.initialized = false;
            return;
        }
        this.reset();

        Object.assign(this, data);
        this.initializeIdGeneration();
        this.createDefaultObjectGroupIfNeeded();
        this.objectGroups.forEach((group) =>
            this.idToObjectGroup.set(group.id, group)
        );
        this.nodes.forEach((node) => {
            this.idToNode.set(node.id, node);
        });
        this.links.forEach((link) => {
            this.idToLink.set(link.id, link);
        });

        this.updateNodeData();
    }

    protected reset() {
        this.nodes = [];
        this.links = [];
        this.objectGroups = [];
        this.idToObjectGroup = new Map<number, NodeType>();
        this.idToNode = new Map<number, Node>();
        this.idToLink = new Map<number, Link>();
    }

    private initializeIdGeneration() {
        this.nextNodeId = Math.max(
            Math.max(...this.nodes.map((node) => node.id)) + 1,
            0
        );
        this.nextLinkId = Math.max(
            Math.max(...this.links.map((link) => link.id)) + 1,
            0
        );
        this.nextObjectGroupId = Math.max(
            Math.max(...this.objectGroups.map((group) => group.id), 0)
        );
    }

    public toJSONSerializableObject(): GraphData {
        return {
            nodes: this.nodes.map((node) => node.toJSONSerializableObject()),
            links: this.links.map((link) => link.toJSONSerializableObject()),
            objectGroups: this.objectGroups.map((group) =>
                group.toJSONSerializableObject()
            ),
        };
    }

    public toHistorySerializableObject(): SimGraphData {
        return {
            nodes: this.nodes.map((node) => node.toHistorySerializableObject()),
            links: this.links.map((link) => link.toHistorySerializableObject()),
            objectGroups: this.objectGroups.map((group) =>
                group.toHistorySerializableObject()
            ),
        };
    }

    public fromSerializedObject(data: GraphData | SimGraphData): Graph {
        this.reset();

        data.objectGroups.forEach((group) => this.createObjectGroup(group));
        this.initializeIdGeneration(); // This is necessary to prevent the default group from overwriting an existing group
        this.createDefaultObjectGroupIfNeeded();

        data.nodes.forEach((node) => this.createNode(node));
        data.links.forEach((link) => this.createLink(link.source, link.target));

        this.updateNodeData();
        this.initializeIdGeneration();

        return this;
    }

    private createDefaultObjectGroupIfNeeded() {
        const defaultGroup = this.objectGroups.find(
            (group) => group.name == "Default"
        );
        if (defaultGroup == undefined) {
            this.defaultGroup = this.createObjectGroup({
                id: ++this.nextObjectGroupId,
                name: "Default",
                color: "#000000",
            });
        } else {
            this.defaultGroup = defaultGroup;
        }
    }

    /**
     * Updates the graph data structure to contain additional values.
     * Creates a 'neighbors' and 'links' array for each node object.
     */
    private updateNodeData(): Link[] {
        this.nodes.forEach((node) => {
            node.links = [];
            node.neighbors = [];
        });

        this.links.forEach((link) => {
            const a = link.source;
            const b = link.target;
            a.neighbors.push(b);
            b.neighbors.push(a);
            a.links.push(link);
            b.links.push(link);
        });
        return this.links;
    }

    public removeFloatingNodes() {
        this.nodes = this.nodes.filter((node) => node.neighbors.length > 0);
    }

    public node(id: number): Node {
        return this.idToNode.get(id);
    }

    public nodeType(id: number): NodeType {
        return this.idToObjectGroup.get(id);
    }

    public link(id: number): Link {
        return this.idToLink.get(id);
    }

    private addNode(node: Node) {
        if (this.idToNode.has(node.id)) {
            node.id = ++this.nextNodeId;
        }
        this.nodes.push(node);
        this.idToNode.set(node.id, node);
    }

    public createNode(data?: NodeData | SimNodeData): Node {
        const node = new Node();
        node.fromSerializedObject(data);
        const group = this.idToObjectGroup.get(data.type);
        node.type = group != undefined ? group : this.defaultGroup;
        node.neighbors = [];
        node.links = [];
        this.addNode(node);
        return node;
    }

    public createLink(source: number, target: number): Link {
        if (source === target) {
            console.warn(
                "Attempting to create a link where source equals target"
            );
            return;
        }

        const sourceNode = this.idToNode.get(source);
        const targetNode = this.idToNode.get(target);

        if (sourceNode === undefined || targetNode === undefined) {
            console.warn("Tried to create a link between nonexisting nodes!");
            return;
        }

        const link = new Link(sourceNode, targetNode);
        sourceNode.links.push(link);
        targetNode.links.push(link);
        this.addLink(link);
        return link;
    }

    public createObjectGroup(data: NodeTypeData): NodeType {
        const group = new NodeType(data.name, data.color);
        group.id = data.id;
        this.addObjectGroup(group);
        return group;
    }

    private addObjectGroup(group: NodeType) {
        if (this.idToObjectGroup.has(group.id)) {
            console.warn(
                "Replacing id of object group. Node association to groups might not be correct."
            );
            group.id = ++this.nextObjectGroupId;
        }

        this.objectGroups.push(group);
        this.idToObjectGroup.set(group.id, group);
    }

    private addLink(link: Link) {
        if (this.idToLink.has(link.id)) {
            link.id = ++this.nextLinkId;
        }
        this.links.push(link);
        this.idToLink.set(link.id, link);
    }

    public deleteLink(id: number): boolean {
        // Remove link from node data structures
        const link = this.idToLink.get(id);
        link.source.links = link.source.links.filter((l) => l.id != id);
        link.target.links = link.target.links.filter((l) => l.id != id);

        // Remove link from graph data structures
        this.links = this.links.filter((l: Link) => l.id != id);
        this.idToLink.delete(id);
        return true;
    }

    public deleteNode(id: number): boolean {
        const node = this.idToNode.get(id);
        this.idToNode.delete(id);

        for (const link of node.links) {
            this.deleteLink(link.id);
        }
        this.nodes = this.nodes.filter((n: Node) => n.id !== id);
        return true;
    }

    public deleteNodeType(id: number): boolean {
        if (this.objectGroups.length <= 1) {
            // Do not allow to delete the last node type.
            return false;
        }

        const nodeType = this.idToObjectGroup.get(id);
        this.idToObjectGroup.delete(id);

        for (const node of this.nodes) {
            if (node.type.id === nodeType.id) {
                node.type = this.objectGroups[0];
            }
        }
        this.objectGroups = this.objectGroups.filter(
            (group) => group.id !== id
        );
        return true;
    }

    public view(
        nodeTypes: Map<number, boolean>,
        linkTypes?: Map<number, boolean>
    ): Graph {
        // Filter nodes depending on type
        const nodes = this.nodes.filter((l) => nodeTypes.get(l.type.id));

        // Filter links depending on type
        let links;
        if (linkTypes === undefined) {
            links = this.links;
        } else {
            links = this.links.filter((l) => linkTypes.get(l.type.id));
        }

        // Filter links which are connected to an invisible node
        links = links.filter(
            (l) =>
                nodeTypes.get(l.source.type.id) &&
                nodeTypes.get(l.target.type.id)
        );

        return new Graph({
            nodes: nodes,
            links: links,
            objectGroups: this.objectGroups,
        });
    }
}