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.

[Amxx]

Hello @demoncoder-crypto

The usecase for onchain graph representation are unclear to me. If they exist, I'm not sure a generalised structure would fit these (possibly widelly different) cases. Before jumping to an implementation, we would like to understand real usecases. We usually don't add complexe or expensive datastructure on a wild guess that someone may someday need it to do onchain something that is today done offchain.