directed-acyclic-graphs

4熱度

2回答

在DAG G中，具有非負加權邊，您如何找到G中兩個頂點之間的最大權重路徑？謝謝你們！

2熱度

2回答

我有一個無環的有向圖。我想以確保如果邊（v1，v2）在圖中，然後是level（v1）> level（v2）的方式爲每個頂點分配級別。如果（v1，v2）和（v3，v2）在圖中，level（v1）= level（v3），我也會喜歡它。此外，可能的級別是離散的（不妨將它們視爲自然數）。理想的情況是，當（v1，v2）在圖中並且從v1到v2沒有其他路徑時，該級別（v1）=級別（v2）+ 1，但有時這對於其他

1熱度

2回答

尋找一個乾淨而高效的算法來檢查和關閉「樹」的元素（實際上是一個DAG）

這不是一項家庭作業。在外觀上它看起來像一棵樹，但所有葉子都是唯一的（在數據庫中有唯一的ID）。它們之上的層次結構有點任意。每個複選框有3個狀態：開，關和部分。葉子只能被檢查或不被檢查。孩子的狀態應該推動父母的狀態。點擊複選框應該「切換」它，並向上或向下傳播必要的更改。如果您點擊部分選中的父級，則應該完全檢查。每個孩子都有一個指向列表的指針（如果必須的話，我可以將更改爲一組）。每個父母都有一個按字

5熱度

3回答

這個算法是如何在一個定向圓周圖上尋找最大路徑的？

自從一段時間以來，我正在使用一種運算複雜度爲O（V + E）的算法來查找從A點到B點的定向圓周圖上的最大路徑，這包括執行洪泛填充以查找哪些節點是可從筆記A訪問，每個節點有多少「父母」（來自其他節點的邊緣）。然後，我做了一個BFS，但是隻有在我已經使用過所有「父母」時才「激活」一個節點。 queue <int> a int paths[] ; //Number of paths that go t

11熱度

1回答

定向樹中從一個節點到另一個節點的所有可能路徑

我使用python binding到igraph來表示有向樹。我想找到從該圖中的一個節點到另一個節點的所有可能路徑。不幸的是，我在igraph中找不到準備使用的函數來執行這個任務？ EDIT 上的路徑無限數目的關注我說的是該圖實際上是一個有向非循環圖（DAG）與單個根。它代表了一個單向的級聯事件，在級聯的各個級別上，可以分裂或連接在一起。正如我所說，這是一個單向圖。還規定圖形不包含任何循環。由於

5熱度

2回答

將工作流DAG轉換爲並行資源分配的算法？

說我有一個圖，其中節點是各種工作負荷和邊緣是工作負荷之間的依賴性。（這是一個DAG，因爲週期性的依賴關係必須不存在。）我也有一組誰能夠執行工作多個代理。一些工作量品種，可給予的任何試劑，其它必須考慮到特定代理，以及其他必須的中間代理的特定組給予一種藥劑。如何分配工作負載，即：，直到其所有攔截的工作量都完成任何工作負載提供給代理最短的時間才能完成總工作量圖。（請注意，最小化劑空閒時間總

10熱度

3回答

合併兩個DAG的高效算法

我有兩個加權的DAG（有向無環圖），需要將它們合併爲一個，因此我可以得到一個拓撲排序（在某些情況下它可能超過兩個）。問題是這些圖是非循環的，但可以一起形成一個循環。此外，圖形很大（100k +節點，500k +邊緣）。有沒有一種巧妙的方法來合併圖表？「同時」遍歷所有圖的算法同樣好。編輯：通過「合併」我的意思是這兩個圖的所有邊緣和頂點組合在一起（當然保留的權重），如果他們不創造週期。如果邊緣

2熱度

1回答

已加入加載/渴望加載sqlalchemy中的整個（子）圖形

比方說，我有一個Task對象，它可以依賴於其他Tasks。有沒有辦法明智地急於/連接加載所有給定的任務子任務？ class Task(DeclarativeBase): __tablename__ = 'task' task_id = Column(Integer, primary_key=True) name = Column(String, unique=Tru

2熱度

2回答

能夠將系統的依賴關係映射爲DAG（有向無環圖）有什麼好處？

如果我將一組對象的依賴關係組織成一個DAG，那麼在什麼情況下比另一個數據結構（如BDD（二元決策圖））更可取？

2熱度

1回答

如何在Java中爲DAG結構創建迭代器包裝？

我想要一個數據結構的迭代器。現在我不知道數據結構是什麼，可能它是一個DAG（有向無環圖），但也許它也可能是一個鏈表。所以我想把它包裝到一個迭代器中，現在不要考慮特定的數據結構。我知道如何訪問一個DAG使用遞歸般的遊客，但我不能想出一個簡單幹淨的結構實現迭代方法next()和hasNext()。在迭代器內部，我創建了一個當前節點實例，並對所有子節點進行循環遍歷，然後返回父節點。一個'已經訪