用於表示部分順序的C/C++圖形界面

Question

在我的代碼中，我使用了一個表示有向無環圖的類。我自己編寫了代碼，並不難。但後來我意識到我的應用程序有更多要求：圖必須是傳遞減少的，即部分訂單的唯一表示。每次用戶在圖形的可視GUI表示上進行拖放或剪切/複製/粘貼時，都必須經過驗證並適應此要求。現在事情變得更加複雜。所以我確實計劃瞭如何安全地執行所有圖表操作等，但是在我深入瞭解代碼之前，我想知道：

是否存在用於部分訂單的已知C/C++接口？ （最好是C++）

我發現了許多很多圖庫，但我已經有了我的簡單非循環圖。我找不到任何專門處理傳遞減少的圖（我不需要鄰接矩陣，數據來自用戶，所以在這裏效率會很低......這是一個用於用戶數據的小圖，而不是用於數學使用）

我正在尋找一個接口，它會自動檢測不必要的連接並將它們刪除，做測試以查看節點複製/移動操作是否是有效的partial-order-wise，即保留部分屬性訂單等

Answer 1

就我所知，通常程序在用於非數學目的時有自己的圖類。發生這種情況是因爲圖表可能比線性容器（如STL容器（矢量，列表等））複雜得多。

由於您在數學或算法領域沒有任何特殊需求（您的案例中的搜索算法將是一個簡單的循環，在大多數情況下，您不需要更多，而且當然不是（過早）優化案例）。如果你這樣做，你有boost :: graph，但我懷疑它會讓事情變得更復雜而不是幫助你。

所以我說，寫一個好的圖/節點類，如果它足夠好並且爲通用目的而寫，我們都可以從中受益。沒有人回答這個問題，因爲真的沒有符合您需求的現有公共代碼。編寫好的自由代碼一次，然後可以在任何地方使用。祝你好運。

P.S你自己的搜索算法可能比爲通用圖形庫編寫的算法快得多，例如， boost :: graph，因爲您可以利用已知的特定圖形的限制和規則，從而使分割快得多。例如，在一個傳遞簡化的圖中，如果A是B的父親，那麼A也不能有b作爲非子孩子的後代（例如grand-child），所以您可以使用這些知識來優化您的搜索。您付費的價格在更改圖表時會進行大量測試，但是由於搜索/掃描速度會變得更快，因此您會獲得很多回報。

Answer 2

我會建議添加一個部分順序驗證方法。編輯時，將整個圖形的副本應用於一個副本，然後進行驗證。如果通過，請保留修改後的副本。如果未通過，請恢復至保存的副本。

也許驗證器可能會找到所有底層節點，爲每個底層節點構建其祖先的多集（如果您稱它們爲後代），並檢查重複的條目。如果您期望只有小圖，我會恢復爲搜索遞歸。