0

I have a directed multigraph of courts "trusting" each other:

    struct TrustedCourt {
        uint256 courtId;
        mapping (uint256 => uint256) limits; // intercourt token => amount
    }

    // truster => trustee
    mapping (uint256 => TrustedCourt[]) internal trustedCourts;

I used a mapping in the struct because I want checking the limit for a given intercourt token to be efficient.

Now it would be desirable to be able also to enumerate all "intercourt tokens" for a given truster and trustee.

We know that Solidity mapping does not support enumeration.

What is the best solution of this problem?

  1. Keep the list of all such intercourt tokens in an additional array struct field?

  2. "Outsource" a solution of this problem to external means like to another contract that would control my contract? (Note that in many cases it would be not necessary to keep a list of such tokens for a particular external controlling contract, so we would implement it only sometimes, when necessary, so saving gas.)

  3. Don't solve it inside the blockchain at all, but allow external software to enumerate such tokens?

  • Note that it is expected that my contract will be usually controlled by external contracts, that would provide such things as voting. – porton Oct 20 '19 at 21:20
0

I picked up on "a directed multigraph". You'll have two-way bindings between vertices. I assume edges may come and go and the same for the vertices themselves. Some storage/gas optimizations are possible if "delete" isn't required.

As far as scope goes, the important thing for a contract is it should safeguard the integrity of the application. That includes referential integrity if it applies. In this case, it sounds like it does.

This generic library handles crud operations on keys. It can simplify and clarify the logical invariants the contract should maintain. It will give you O(1) complexity for random access, the ability to count and iterate and you can use it to enforce referential integrity.

pragma solidity 0.5.8;

// https://github.com/rob-Hitchens/UnorderedKeySet
import "./HitchensUnorderedKeySet.sol";

contract Graph {

    /**
     * Data Layout
     * Support CRUD and referential integrity
     */

    using HitchensUnorderedKeySetLib for HitchensUnorderedKeySetLib.Set;
    HitchensUnorderedKeySetLib.Set vertexSet;

    struct Vertex {
        // vertex properties
        HitchensUnorderedKeySetLib.Set inEdgeSet; // points in
        HitchensUnorderedKeySetLib.Set outEdgeSet; // points out
        mapping(bytes32 => Edge) outEdgeStructs;
    }

    mapping(bytes32 => Vertex) vertexStructs;

    struct Edge {
        // meta properties
        uint limit;
    }

    /**
     * CRUD Ops (partial)
     */

    function insertVertex(bytes32 vertexId) public {
        vertexSet.insert(vertexId); // does not permit duplicates
    }

    function insertEdge(bytes32 vertexFromId, bytes32 vertexToId, uint limit) public {
        require(vertexSet.exists(vertexFromId), "From vertex does not exist.");
        require(vertexSet.exists(vertexToId), "To vertex does not exist.");
        Vertex storage from = vertexStructs[vertexFromId];
        Vertex storage to = vertexStructs[vertexToId];
        from.outEdgeSet.insert(vertexToId); // does not permit duplicate
        to.inEdgeSet.insert(vertexFromId); // does not permit duplicate (redundant)
        from.outEdgeStructs[vertexToId].limit = limit; // set edge properties
    }

    function removeEdge(bytes32 vertexFromId, bytes32 vertexToId) public {
        require(vertexSet.exists(vertexFromId), "From vertex does not exist.");
        require(vertexSet.exists(vertexToId), "To vertex does not exist.");
        Vertex storage from = vertexStructs[vertexFromId];
        Vertex storage to = vertexStructs[vertexToId];
        from.outEdgeSet.remove(vertexToId); // must exist
        to.inEdgeSet.remove(vertexFromId); // must exist
        delete from.outEdgeStructs[vertexToId];
    }

    function removeVertex(bytes32 vertexId) public view {
        require(vertexStructs[vertexId].inEdgeSet.count() == 0, "Cannot delete vertex with incoming edges.");
    }

    /**
     * Carry on with inspectors
     * - vertexCount
     * - vertexAtIndex (iteration)
     * - vertexInCount
     * - vertexInAtIndex (iteration)
     * - vertexOutCount
     * - vertexOutAtIndex (iteration)
     */
}

Hope it helps.

| improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.