Efficient Solidity storage pattern for a directional weighted graph

Question

I would like my graph's nodes to each have a struct of data and 0 or more pointers to other nodes.

It needs to be efficient for insertions of new nodes in between two existing nodes.

Should I use mappings, arrays, a combination of both?

Thanks in advance!

Answer 1

I think you could do worse than to start with something like this:

pragma solidity 0.5.14;

import "./HitchensUnorderedKeySet.sol";

contract DirectedGraph {

    using HitchensUnorderedKeySetLib for HitchensUnorderedKeySetLib.Set;

    HitchensUnorderedKeySetLib.Set nodeIds;

    struct NodeStruct {
        HitchensUnorderedKeySetLib.Set parents; // in
        HitchensUnorderedKeySetLib.Set children; // out
        uint weight;
        uint data1; // etc, carry on ... 
    }

    mapping(bytes32 => NodeStruct) nodeStructs;

}

Should I use mappings, arrays, a combination of both?

This library uses a combination of both. The "Sets" will be the ids only to cover important concerns. You will also use a mapping to store the node structs themselves. Sets for the ID lists and mapped structs for data about those nodes.

https://github.com/rob-Hitchens/UnorderedKeySet

That gives you a straight-forward data structure that allows efficient addition and removal of parents and children with the .insert() and .remove() methods on the Sets. It will your responsibility to maintain internal referential integrity, so you whan you add a child, go to the child and add the corresponding parent. Cover both sides when deleting, as well - if a child is removed, then visit the child and remove the parent.

You will have to build out functions to add and remove nodes and create and remove joins but the data structure itself seems like a good start. I made the library for cases like this where the management of indexes tends to get really busy.

Hope it helps.

UPDATE

I decided to play a little more since there's a bounty.

Don't be discouraged by the length. There's a library that attends to the graph concerns and an app that uses the library for users and followers.

Given the superficial testing, it's not meant to pose as a thoroughly tested scheme. No warranty.

Hopefully GraphTest.sol shows that application contracts can be brief when the busy functions are offloaded to dependable libraries. The Graph is a little opinionated and you might need to adjust the following rules for a real-world application.

1. A node can be added with no edges (orphan)
2. An edge can only be added between nodes that exist.
3. A node can only be removed after all edges it connects to are removed.
4. Edge weights can be adjusted.
5. Edges can be removed.
6. Nodes can be removed.
7. View functions will revert if the requested nodes or edges don't exist, but there are "exists()" and "count()" functions that are safe, so there is no need to wander out of bounds.

The arrangement is optimized for completeness, integrity and readability. There are opportunities to optimize SSTORE operations if:

1. Integrity constraints are relaxed.
2. Iterating/enumerating nodes and edges isn't needed.
3. Removing nodes and edges isn't needed.

Knock down the storage that supports functionality that isn't needed to squeeze more gas out of it.

Creating a new edge is the most expensive operation, about 250K gas. Gas costs are scale-invariant.

Testing was pretty basic:

1. Create 0x35..., Alice
2. Create 0x14..., Bob
3. 0x14... follows 0x35...
4. Check, 2 users, Alice has one follower, Bob is following one user
5. Alice's 1st follower is Bob
6. Bob's first following is Alice
7. Neither Alice or Bob can be deleted
8. Bob can unfollow Alice
9. Alice and Bob can both be deleted
10. Inspectors return accurate information as you go.

Footnotes:

1. The Library uses bytes32 for keys as it is the most versatile. When I was conjuring up a use-case for the test, I settled on users and decided to use address. The library itself could be (should be) refactored for address in such a case instead of using the type conversions I hacked into the test case.
2. It might be useful to enumerate the following/followers in weight order. It would be possible to build binary trees or linked lists to efficiently look after that if a client-side, event-based scheme isn't sufficient. https://github.com/rob-Hitchens/OrderStatisticsTree

pragma solidity 0.5.14;

import "./HitchensUnorderedKeySet.sol";

// It would be possible to refactor for a version that uses address keys to avoid the type conversions in the test application. 
// Also possible to trim storage with relaxed integrity checks.

library GraphLib {

    using HitchensUnorderedKeySetLib for HitchensUnorderedKeySetLib.Set;

    struct EdgeStruct {
        bytes32 source;
        bytes32 target;
        uint weight;
    }

    struct NodeStruct {
        HitchensUnorderedKeySetLib.Set sourceEdgeSet; // in
        HitchensUnorderedKeySetLib.Set targetEdgeSet; // out
    }

    struct Graph {
        HitchensUnorderedKeySetLib.Set nodeSet;
        HitchensUnorderedKeySetLib.Set edgeSet;
        mapping(bytes32 => NodeStruct) nodeStructs;
        mapping(bytes32 => EdgeStruct) edgeStructs;
    }

    function insertNode(Graph storage g, bytes32 nodeId) internal {
        g.nodeSet.insert(nodeId);
    }

    function removeNode(Graph storage g, bytes32 nodeId) internal {
        NodeStruct storage n = g.nodeStructs[nodeId];
        require(n.sourceEdgeSet.count() == 0, "Graph: Remove source edges first.");
        require(n.targetEdgeSet.count() == 0, "Graph: Remove target edges first.");
        g.nodeSet.remove(nodeId);
        delete g.nodeStructs[nodeId];
    }

    function insertEdge(Graph storage g, bytes32 sourceId, bytes32 targetId, uint weight) internal returns(bytes32 edgeId) {
        require(g.nodeSet.exists(sourceId), "Graph: Unknown sourceId.");
        require(g.nodeSet.exists(targetId), "Graph: Unknown targetId.");
        edgeId = keccak256(abi.encodePacked(sourceId, targetId));
        EdgeStruct storage e = g.edgeStructs[edgeId];
        g.edgeSet.insert(edgeId);
        NodeStruct storage s = g.nodeStructs[sourceId];
        NodeStruct storage t = g.nodeStructs[targetId]; 
        s.targetEdgeSet.insert(edgeId);
        t.sourceEdgeSet.insert(edgeId);        
        e.source = sourceId;
        e.target = targetId;
        e.weight = weight;
    }

    function updateEdge(Graph storage g, bytes32 sourceId, bytes32 targetId, uint weight) internal {
        bytes32 edgeId = keccak256(abi.encodePacked(sourceId, targetId));
        require(g.edgeSet.exists(edgeId), "Graph: Unknown edge.");
        EdgeStruct storage e = g.edgeStructs[edgeId];
        e.weight = weight;
    }

    function removeEdge(Graph storage g, bytes32 sourceId, bytes32 targetId) internal {
        bytes32 edgeKey = keccak256(abi.encodePacked(sourceId, targetId));
        g.edgeSet.remove(edgeKey);
        delete g.edgeStructs[edgeKey];
        NodeStruct storage s = g.nodeStructs[sourceId];
        NodeStruct storage t = g.nodeStructs[targetId];
        s.targetEdgeSet.remove(edgeKey);
        t.sourceEdgeSet.remove(edgeKey);
    }

    function insertBetween(Graph storage g, bytes32 newNodeId, bytes32 sourceId, bytes32 targetId, uint sourceWeight, uint targetWeight) internal {
        removeEdge(g, sourceId, targetId);
        insertEdge(g, sourceId, newNodeId, sourceWeight);
        insertEdge(g, newNodeId, targetId, targetWeight);
    }  

    // View functioos

    function edgeExists(Graph storage g, bytes32 edgeId) internal view returns(bool exists) {
        return(g.edgeSet.exists(edgeId));
    }

    function edgeCount(Graph storage g) internal view returns(uint count) {
        return g.edgeSet.count();
    }

    function edgeAtIndex(Graph storage g, uint index) internal view returns(bytes32 edgeId) {
        return g.edgeSet.keyAtIndex(index);
    }

    function edgeSource(Graph storage g, bytes32 edgeId) internal view returns(bytes32 sourceId, uint weight) {
        require(edgeExists(g, edgeId), "Graph: Unknown edge.");
        EdgeStruct storage e = g.edgeStructs[edgeId];
        return(e.source, e.weight);
    } 

    function edgeTarget(Graph storage g, bytes32 edgeId) internal view returns(bytes32 targetId, uint weight) {
        require(edgeExists(g, edgeId), "Graph: Unknown edge.");
        EdgeStruct storage e = g.edgeStructs[edgeId];
        return(e.target, e.weight);
    } 

    // Nodes

    function nodeExists(Graph storage g, bytes32 nodeId) internal view returns(bool exists) {
        return(g.nodeSet.exists(nodeId));
    }

    function nodeCount(Graph storage g) internal view returns(uint count) {
        return g.nodeSet.count();
    }

    function node(Graph storage g, bytes32 nodeId) internal view returns(uint sourceCount, uint targetCount) {
        require(g.nodeSet.exists(nodeId), "Graph: Unknown node.");
        NodeStruct storage n = g.nodeStructs[nodeId];
        return(n.sourceEdgeSet.count(), n.targetEdgeSet.count());
    }

    function nodeSourceEdgeAtIndex(Graph storage g, bytes32 nodeId, uint index) internal view returns(bytes32 sourceEdge) {
        require(g.nodeSet.exists(nodeId), "Graph: Unknown node.");
        NodeStruct storage n = g.nodeStructs[nodeId];
        sourceEdge = n.sourceEdgeSet.keyAtIndex(index);
    }

    function nodeTargetEdgeAtIndex(Graph storage g, bytes32 nodeId, uint index) internal view returns(bytes32 targetEdge) {
        require(g.nodeSet.exists(nodeId), "Graph: Unknown node.");
        NodeStruct storage n = g.nodeStructs[nodeId];
        targetEdge = n.targetEdgeSet.keyAtIndex(index);
    }
}

import "./HitchensUnorderedAddressSet.sol";

contract GraphTest {

    using GraphLib for GraphLib.Graph;
    using HitchensUnorderedAddressSetLib for HitchensUnorderedAddressSetLib.Set;
    GraphLib.Graph userGraph;

    struct UserStruct {
        string name;
        // carry on with app concerns
    }

    HitchensUnorderedAddressSetLib.Set userSet;
    mapping(address => UserStruct) private userStructs;

    function newUser(address userId, string memory name) public {
        userSet.insert(userId);
        userStructs[userId].name = name;
        userGraph.insertNode(toBytes32(userId));
    }

    function removeUser(address userId) public {
        userGraph.removeNode(toBytes32(userId)); // this will not be permited while edges exist, so iterate over unfollow until permissible.
        delete userStructs[userId];
        userSet.remove(userId);
    }

    function updateUser(address userId, string memory name) public {
        require(userSet.exists(userId), "GraphTest: Unknown user.");
        userStructs[userId].name = name;
    }

    function follow(address sourceId, address targetId, uint importance) public {
        require(userSet.exists(sourceId), "GraphTest: Unknown follower.");
        require(userSet.exists(targetId), "GraphTest: Unknown target.");
        userGraph.insertEdge(toBytes32(sourceId), toBytes32(targetId), importance);
    }

    function unfollow(address sourceId, address targetId) public {
        require(userSet.exists(sourceId), "GraphTest: Unknown follower.");
        require(userSet.exists(targetId), "GraphTest: Unknown target.");
        userGraph.removeEdge(toBytes32(sourceId), toBytes32(targetId));
    }

    function adjustFollow(address sourceId, address targetId, uint importance) public {
        userGraph.updateEdge(toBytes32(sourceId), toBytes32(targetId), importance);
    }

    // view functions

    function userCount() public view returns(uint count) {
        count = userSet.count();
    }

    function userAtIndex(uint index) public view returns(address userId) {
        userId = userSet.keyAtIndex(index);
    }

    function userInfo(address userId) public view returns(string memory name, uint followerCount, uint followingCount) {
        require(userSet.exists(userId), "GraphTest: Unknown user.");
        (followerCount, followingCount) = userGraph.node(toBytes32(userId));
        name = userStructs[userId].name;
    }

    function userFollowerAtIndex(address userId, uint index) public view returns(address followerId, uint importance) {
        require(userSet.exists(userId), "GraphTest: Unknown user.");
        bytes32 edgeId = userGraph.nodeSourceEdgeAtIndex(toBytes32(userId), index);
        (bytes32 source, uint weight) = userGraph.edgeSource(edgeId);
        importance = weight;
        followerId = toAddress(source);
    }

    function userFollowingAtIndex(address userId, uint index) public view returns(address followingId, uint importance) {
        require(userSet.exists(userId), "GraphTest: Unknown user.");
        bytes32 edgeId = userGraph.nodeTargetEdgeAtIndex(toBytes32(userId), index);
        (bytes32 target, uint weight) = userGraph.edgeTarget(edgeId);
        importance = weight;
        followingId = toAddress(target);
    }

    // Debugging

    /*

    function edgeCount() public view returns(uint) {
        return userGraph.edgeCount();
    }

    function edgeAtIndex(uint index) public view returns(bytes32) {
        return userGraph.edgeAtIndex(index);
    }

    function edge(bytes32 edgeId) public view returns(bytes32 sourceId, bytes32 targetId, uint weight) {
        (sourceId, targetId, weight) = userGraph.edge(edgeId);
    }

    function edgeIdHelper(address source, address target) public pure  returns(bytes32 edgeId) {
        return(keccak256(abi.encodePacked(toBytes32(source), toBytes32(target))));
    }

    */

    // pure functions, because the graph was set up for bytes32 keys

    function toBytes32(address a) private pure returns(bytes32) {
        return bytes32(uint(uint160(a)));
    }

    function toAddress(bytes32 b) private pure returns(address) {
        return address(uint160(uint(b)));
    }
}

Footnote: The state-changing functions in GraphTest use require() to check things like "node exists" and generate app-aware errors on invalid requests. That isn't strictly necessary since GraphLib will revert if something illogical is requested. The difference is:

• an error the user is likely to understand versus an error message that might seem obtuse.
• The multilayered approach is a library that will not process a bad request and an app that should never make an invalid request.

If optimizing for gas, one check is sufficient. I would keep it at the library level to ensure an app/dev oversight cannot munge up referential integrity and maybe try to change the generic messages to something more informative to an end-user.

Answer 2

library GraphLibrary {
  struct Graph {
    mapping (uint => mapping (uint => uint)) edges;
    mapping (uint => uint) sourceNodes;
    mapping (uint => uint) targetNodes;
    uint lastEdgeID;
  }

  function addEdge (Graph storage _graph, uint _sourceNodeID, uint _targetNodeID) external returns (uint) {
    require (_graph.edges [_sourceNodeID][_targetNodeID] == 0);

    uint edgeID = ++_graph.lastEdgeID;

    _graph.edges [_sourceNodeID][_targetNodeID] = edgeID;
    _graph.sourceNodes [edgeID] = _sourceNodeID;
    _graph.targetNodes [edgeID] = _targetNodeID;

    return edgeID;
  }

  function deleteEdge (Graph storage _graph, uint _sourceNodeID, uint _targetNodeID) external {
    uint edgeID = _graph.edges [_sourceNodeID][_targetNodeID];

    require (edgeID != 0);

    delete _graph.sourceNodes [edgeID];
    delete _graph.targetNodes [edgeID];
    delete _graph.edges [_sourceNodeID][_targetNodeID];
  }

  function deleteEdge (Graph storage _graph, uint _edgeID) external {
    require (_edgeID != 0);

    uint sourceNodeID = _graph.sourceNodes [_edgeID];
    uint targetNodeID = _graph.targetNodes [_edgeID];

    require (_graph.edges [sourceNodeID][targetNodeID] == _edgeID);

    delete _graph.sourceNodes [_edgeID];
    delete _graph.targetNodes [_edgeID];
    delete _graph.edges [sourceNodeID][targetNodeID];
  }
}

Here how one could insert a new node between two nodes connected by an edge:

contract Foo {
  using GraphLibrary for GraphLibrary.Graph;

  GraphLibrary.Graph public graph;

  // Insert node `c` betweeen nodes `a` and `b`.
  function insertNode (uint a, uint b, uint c) public {
    graph.deleteEdge (a, b);
    graph.addEdge (a, c);
    graph.addEdge (c, b);
  }
}

In case you need to store additional data (like weight) associated with nodes and/or edges, just use external mappings like this:

// Node ID to node payload mapping
mapping (uint => NodePayload) nodePayloads;

// Edge ID to edge payload mapping
mapping (uint => EdgePayload) edgePayloads;

Note, that there are no functions to add/remove nodes. The graph assumes that there are always 2^256 nodes, so you may use any uint value as node ID without adding it explicitly.

Answer 3

The general advice in solidity for these kind of problem is to divide the storage of node-data from the node- topology network description. This means that any new node data should be added to a simple list (i.e. a dynamic array) and that the network of connection should be managed by a different structure. A mapping where the address is the node number in the array and the argument is the address of a dynamic list of nodes connected to that node is often used and is easy to update when a new node is added or deleted. In particular you should understand that if a node is to be deleted, you can simply update the connections and leave the node unconnected. Your application should be the compass used to find the direction for the topology design and for the access-to-each-node primitives. We can not be more specific here.