Solidity

有向加權圖的高效 Solidity 儲存模式

  • December 31, 2019

我希望我的圖形節點每個都有一個資料結構和 0 個或更多指向其他節點的指針。

它需要有效地在兩個現有節點之間插入新節點。

我應該使用映射、數組還是兩者的組合？

提前致謝！

我認為你可以做得比從這樣的事情開始更糟糕：

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;

}

我應該使用映射、數組還是兩者的組合？

這個庫使用了兩者的組合。“集合”將是僅用於涵蓋重要問題的 ID。您還將使用映射來儲存節點結構本身。為有關這些節點的數據設置 ID 列表和映射結構。

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

這為您提供了一個直截了當的資料結構，允許使用 Set 上的 .insert() 和 .remove() 方法有效地添加和刪除父母和孩子。維護內部參照完整性將是您的責任，因此您在添加子項時，請轉到子項並添加相應的父項。刪除時也要覆蓋兩側 - 如果孩子被移除，則訪問孩子並移除父母。

您將不得不建構函式來添加和刪除節點以及創建和刪除連接，但資料結構本身似乎是一個好的開始。我為此類索引管理往往變得非常忙碌的情況創建了庫。

希望能幫助到你。

更新

我決定多玩一點，因為有賞金。

不要因長度而氣餒。有一個處理圖形問題的庫和一個為使用者和關注者使用該庫的應用程序。

鑑於表面測試，它並不意味著作為一個經過徹底測試的方案。沒有保修。

希望GraphTest.sol表明，當繁忙的功能被解除安裝到可靠的庫時，應用程序契約可以很簡短。圖表有點固執己見，您可能需要針對實際應用程序調整以下規則。

  1. 可以添加沒有邊的節點（孤兒）
  2. 只能在存在的節點之間添加邊。
  3. 一個節點只有在它連接的所有邊都被刪除後才能被刪除。
  4. 邊緣權重可以調整。
  5. 可以去除邊緣。
  6. 可以刪除節點。
  7. 如果請求的節點或邊不存在，視圖函式將恢復，但“exists()”和“count()”函式是安全的，因此無需越界。

該安排針對完整性、完整性和可讀性進行了優化。如果出現以下情況，則有機會優化 SSTORE 運營：

  1. 完整性約束被放寬。
  2. 不需要迭代/列舉節點和邊。
  3. 不需要刪除節點和邊。

關閉支持不需要從中擠出更多氣體的功能的儲存。

創建一個新的邊緣是最昂貴的操作，大約 250K gas。天然氣成本是規模不變的。

測試非常基礎：

  1. 創建 0x35…，愛麗絲
  2. 創建 0x14…，鮑勃
  3. 0x14… 跟隨 0x35…
  4. 檢查，2 個使用者，Alice 有一個關注者，Bob 關注了一個使用者
  5. Alice 的第一個追隨者是 Bob
  6. Bob 的第一個追隨者是 Alice
  7. Alice 和 Bob 都不能被刪除
  8. Bob 可以取消關注 Alice
  9. Alice 和 Bob 都可以刪除
  10. 檢查員會隨時返回準確的資訊。

腳註：

  1. 圖書館使用bytes32鑰匙，因為它是最通用的。當我想出一個測試案例時，我選擇了使用者並決定使用address. 在這種情況下，庫本身可以（應該）重構，address而不是使用我侵入測試案例的類型轉換。
  2. 按權重順序列舉以下/關注者可能很有用。如果客戶端的基於事件的方案不夠用，則可以建構二叉樹或鍊錶來有效地處理這些問題。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)));
   }
}

腳註： GraphTest 中的狀態更改函式require()用於檢查“節點是否存在”之類的內容，並在無效請求時生成應用感知錯誤。這不是絕對必要的，因為如果請求不合邏輯的內容，GraphLib 將恢復。區別在於：

  • 使用者可能理解的錯誤與可能看起來遲鈍的錯誤消息。
  • 多層方法是一個不會處理錯誤請求的庫和一個永遠不應該發出無效請求的應用程序。

如果針對氣體進行優化，則一項檢查就足夠了。我會將其保留在庫級別，以確保應用程序/開發人員的監督不能破壞參照完整性，並可能嘗試將通用消息更改為對最終使用者提供更多資訊的內容。

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

在這裡，如何在由邊連接的兩個節點之間插入一個新節點：

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

如果您需要儲存與節點和/或邊關聯的其他數據（如權重），只需使用如下外部映射：

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

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

請注意，沒有添加/刪除節點的功能。該圖假定始終存在2^256節點，因此您可以使用任何uint值作為節點 ID 而無需顯式添加它。

引用自：https://ethereum.stackexchange.com/questions/78333

相關問答

Solidity

如何處理動態大小的字元串數組？

  • February 13, 2022
檢視問答
Solidity

為什麼類型字節為每個元素浪費 31 個字節的空間？

  • December 17, 2021
檢視問答
Solidity

儲存 SHA-256 64 字節字元串

  • November 17, 2021
檢視問答
Solidity

合約可以發出多少個事件以及它可以擁有多少個映射是否有限制？

  • April 20, 2021
檢視問答
Solidity

在查詢大量但固定數量的結構（數組或映射）時，使用什麼更好？

  • March 25, 2021
檢視問答
Solidity

在 Solidity 中推送到數組的不同部分

  • March 17, 2021
檢視問答