From Graph to Dependency order
MODIFY
WalletWasabi.Tests/UnitTests/NBitcoinTests.cs
WalletWasabi.Tests/UnitTests/NBitcoinTests.cs
@@ -51,6 +51,17 @@ namespace WalletWasabi.Tests.UnitTests
Assert.Equal(2, graph.Skip(1).First().Children.Count()); // tx1 has two children tx3 and tx4
Assert.Equal(1, graph.Last().Children.Count()); // tx2 has only one children tx7
Assert.Equal(2, graph.Last().Children.Single().Parents.Count()); // tx7 has two parents tx2 and tx6
+
+ var txs = graph.OrderByDependency().ToArray();
+ Assert.Equal(8, txs.Count());
+ Assert.Equal(tx0, txs[0]);
+ Assert.Equal(tx1, txs[1]);
+ Assert.Equal(tx2, txs[2]);
+ Assert.Equal(tx3, txs[3]);
+ Assert.Equal(tx4, txs[4]);
+ Assert.Equal(tx5, txs[5]);
+ Assert.Equal(tx6, txs[6]);
+ Assert.Equal(tx7, txs[7]);
}
private static (Transaction, Coin[]) CreateTransaction(params Coin[] coins)

MODIFY
WalletWasabi/Extensions/NBitcoinExtensions.cs
WalletWasabi/Extensions/NBitcoinExtensions.cs
@@ -347,7 +347,45 @@ namespace NBitcoin
}
}
}
- return lookup.Values.Where(x => !x.Parents.Any());
+ var nodes = lookup.Values;
+ return nodes.Where(x => !x.Parents.Any());
+ }
+
+ public static IEnumerable<Transaction> OrderByDependency(this IEnumerable<TransactionDependencyNode> roots)
+ {
+ var parentCounter = new Dictionary<TransactionDependencyNode, int>();
+
+ void Walk(TransactionDependencyNode node)
+ {
+ if (!parentCounter.ContainsKey(node))
+ {
+ parentCounter.Add(node, node.Parents.Count());
+ foreach(var child in node.Children)
+ {
+ Walk(child);
+ }
+ }
+ }
+
+ foreach(var root in roots)
+ {
+ Walk(root);
+ }
+
+ var nodes = parentCounter.Where(x => x.Value == 0).Select(x=>x.Key).Distinct().ToArray();
+ while(nodes.Any())
+ {
+ foreach(var node in nodes)
+ {
+ yield return node.Transaction;
+ parentCounter.Remove(node);
+ foreach(var child in node.Children)
+ {
+ parentCounter[child] = parentCounter[child] - 1;
+ }
+ }
+ nodes = parentCounter.Where(x => x.Value == 0).Select(x=>x.Key).Distinct().ToArray();
+ }
}
}
}

From Graph to Dependency order