# Efficient Solidity storage pattern for a directional weighted graph

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?

• Note that in solidity, storage pointers cannot be stored in storage. Dec 16, 2019 at 18:08
• Instead of pointer, you can use an index to an array which stores the actual records. Then use a mapping in order to map the index of each node to an array of the indexes of the nodes that this node is connected to. Dec 16, 2019 at 18:15
• In order to add weights, instead of mapping each index to an array of indexes, map it to an array of tuples (structures), where each tuple contains an index and a weight. Dec 16, 2019 at 18:16
• Do you need to support multigraph (several edges with the same origin and target)? Dec 27, 2019 at 11:09
• See my answer below (without multigraph support). Multigraph support could be added, but for additional gas cost. Dec 27, 2019 at 11:47

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
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);
}
}

contract GraphTest {

using GraphLib for GraphLib.Graph;
GraphLib.Graph userGraph;

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

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

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;
}

require(userSet.exists(sourceId), "GraphTest: Unknown follower.");
require(userSet.exists(targetId), "GraphTest: Unknown target.");
userGraph.insertEdge(toBytes32(sourceId), toBytes32(targetId), importance);
}

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

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;
}

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;
}

// 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);
}

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)));
}

}
}
``````

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.

• Pull requests welcomed with gratitude: github.com/rob-Hitchens/GraphLib.git Dec 30, 2019 at 19:36
• Thank you very much for the response! The bounty shall be awarded on the first day of 2020. Happy new year! :) Dec 31, 2019 at 15:59
• Happy new year to you! If you find a bug or a reason to extend or make a variant that works a little differently, consider a pull request at the repo above. Maybe this turns into something useful to others. Dec 31, 2019 at 20:40
``````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);
}
}
``````

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
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.