Mutable DAG in Dgraph

Users Dgraph
1

I’m wondering if it’s possible to maintain a mutable directed acyclic graph built on Dgraph. Whenever a new edge is to be added I need to make sure that it isn’t going to create a cycle. I’d be comfortable doing this on a single database instance, but with a distributed system I’m worried about race conditions, e.g. if I try and add an edge from node A to node B, and far away at a similar time someone adds an edge from node B to node A.

2 
const dgraph = require('dgraph-js');
const grpc = require('grpc');

// Initialize Dgraph client
const dgraphClientStub = new dgraph.DgraphClientStub('localhost:9080', grpc.credentials.createInsecure());
const dgraphClient = new dgraph.DgraphClient(dgraphClientStub);

class MutableDAG {
    constructor() {
        this.client = dgraphClient;
    }

    async addEdge(from, to) {
        // Check for cycle before adding the edge
        if (await this.detectCycle(from, to)) {
            console.error("Adding this edge would create a cycle.");
            return false;
        }

        try {
            const txn = this.client.newTxn();
            await txn.mutate({
                setJson: {
                    uid: "_:" + from,  // Assuming from and to are string identifiers for nodes
                    edge: {
                        uid: "_:" + to
                    }
                },
                commitNow: true  // Commit immediately to avoid holding transaction open
            });
            console.log(`Edge added from ${from} to ${to}`);
            return true;
        } catch (error) {
            console.error("Failed to add edge:", error);
            return false;
        }
    }

    async detectCycle(start, end) {
        let visited = new Set();
        let stack = [start];
        let hasCycle = false;

        while (stack.length > 0 && !hasCycle) {
            const current = stack.pop();
            if (current === end) {
                hasCycle = true;
                break;
            }

            if (!visited.has(current)) {
                visited.add(current);
                // Query Dgraph for all edges from the current node
                const query = `
                query {
                    q(func: uid("${current}")) {
                        edge {
                            uid
                        }
                    }
                }`;
                
                try {
                    const res = await this.client.newTxn().query(query);
                    const edges = res.getJson().q[0].edge || [];

                    for (const edge of edges) {
                        stack.push(edge.uid.slice(2)); // Remove the '_:' prefix
                    }
                } catch (error) {
                    console.error("Failed to query for edges:", error);
                    return true; // Assume cycle to be safe (fail-safe approach)
                }
            }
        }
        return hasCycle;
    }
}

// Usage:
(async () => {
    const dag = new MutableDAG();
    await dag.addEdge('nodeA', 'nodeB');  // Should work if no cycle detected
    // await dag.addEdge('nodeB', 'nodeA');  // Should not work if it creates a cycle
})();