Add a Basic Graph Utility Library (Graph.sol)

[demoncoder-crypto]

Motivation

OpenZeppelin Contracts provides a rich set of utilities and data structures like EnumerableSet, EnumerableMap, MerkleProof, etc. However, there doesn't appear to be a dedicated, reusable library for representing basic graph structures (nodes and edges) directly on-chain.

While complex graph algorithms are often unsuitable for on-chain execution due to gas costs, certain use cases might benefit from a standardized, gas-conscious way to store and query simple graph relationships. Potential applications could include:

• Simple social graphs (e.g., follow relationships, direct connections)
• On-chain dependency tracking between entities or contracts
• Representing simple state transitions or allowed paths
• Certain DeFi structures requiring tracking of direct links

Having a basic, reusable Graph.sol utility within the library could potentially simplify development for these scenarios and promote a standard approach, similar to how EnumerableSet provides a standard for enumerable sets.

Proposed Solution (Initial Idea)

A potential approach could be an AdjacencyListGraph library using EnumerableSet to manage edges:

import {EnumerableSet} from "@openzeppelin/contracts/utils/structs/EnumerableSet.sol";

library AdjacencyListGraph {
using EnumerableSet for EnumerableSet.UintSet; // Or AddressSet

// Represents the graph structure: node => set of neighbors
struct Graph {
    mapping(uint256 => EnumerableSet.UintSet) _adjacencyList; // Or address => AddressSet
    // Could potentially track node existence separately if needed
}

// --- Potential Functions ---

function addNode(Graph storage graph, uint256 node) internal {
    // Logic to potentially track node existence if isolated nodes are allowed
}

function addEdge(Graph storage graph, uint256 from, uint256 to) internal {
    // Ensure nodes exist if needed?
    graph._adjacencyList[from].add(to);
    // For undirected, add the reverse edge too:
    // graph._adjacencyList[to].add(from);
}

function removeEdge(Graph storage graph, uint256 from, uint256 to) internal {
    graph._adjacencyList[from].remove(to);
    // For undirected, remove the reverse edge too:
    // graph._adjacencyList[to].remove(from);
}

function getNeighbors(Graph storage graph, uint256 node) internal view returns (uint256[] memory) {
    return graph._adjacencyList[node].values();
}

function hasEdge(Graph storage graph, uint256 from, uint256 to) internal view returns (bool) {
    return graph._adjacencyList[from].contains(to);
}

function countNeighbors(Graph storage graph, uint256 node) internal view returns (uint256) {
    return graph._adjacencyList[node].length();
}

// Potentially add functions for nodes using address keys as well.
// More complex functions (e.g., reachability) are likely too gas-intensive.

}

Thank you for considering this proposal.