This little library is packed with the following features:
- Building dependency graph from dependency data.
- Performing topological sort on the dependency graph.
- Generating dependence-free subsets for parallel processing.
- Cycle detection and cycle reporting.More on topic for the project though, did you have any project ideas for this? I think I could use this for my opencv node editor, I just did the naive method of marking all outputs dirty as their inputs nodes got reprocessed. I assume this would fix the potential problem of recomputing a node twice? I also see you mention "Cycle detection and cycle reporting." but what specifically happens if I do have a cycle? Does it just give up or is it something like best effort?
I implemented topological sort for bringing up and shutting down OS services in order like 20 years ago, but it was like a quick and dirty way doing it and never formally as a published library. I do it this time because it's a well understood topic so I can concentrate on learning the ropes of Zig and package publishing while doing something useful. And I go the extra miles to find dependence free subsets for parallel processing and to detect cycles.
> I assume this would fix the potential problem of recomputing a node twice?
Yes. Topological sort is perfect for laying out the path of computation tasks to avoid redoing things.
> "Cycle detection and cycle reporting." but what specifically happens if I do have a cycle? Does it just give up or is it something like best effort?
It will keep going as a best effort when cycles are detected. It will produce a partial topological sorted result and a set of cyclic nodes.
I like the language intention but I can't get past the syntax.
For syntax there are a few things that I'm iffy on, but nothing that I'd consider a deal breaker. I found it very easy to read right out of the gate, which is basically the only thing I need to really learn a new language (probably the only reason I haven't learned rust yet.)
I totally understand how those two features could be useful.
For the parameter name feature, I can't imagine a strong reason for not implementing it (I mean, apart of "we have other stuff to prioritize").
For the tag I could see an attribute system like in C++ [0]
On a tangential topic, I believe that's exactly the Pandora box of meta-programming.
[0] https://en.cppreference.com/w/cpp/language/attributes#Explan...
For what it's worth, I use Rust daily and I don't really care about memory issue. It's nice that it comes with the package, but it's not why I do it. Believe it or not, the borrow checker is first and foremost why I enjoy writing Rust. It's such a brilliant idea I don't understand why it's not more widely used. A helpful compiler and a good (if imperfect) crate ecosystem are probably 2nd and 3rd.
Consider, e.g., how in TypeScript object literals ({ a: b, c: d, e }), object types ({ a: b; c: d; }) and object destructuring ({ a, c, e } = … ) can all look very similar. Same thing for lambdas ((a: b) => b) and function types ((a: b) => b). Also, additional parentheses are needed to prevent the compiler from mistaking an object literal ({ … }) for a function body ({ … }) when it is returned in a lambda expression. In short: Some of TypeScript's syntactic constructs are heavily overloaded and their meaning depends on the context.
For an example of proneness to errors, consider that in Nix function calls (<function name> <param1> <param2> …) and lists ([<item1> <item 2> …]) look almost the same and it's very easy to confuse the two and mess up, e.g.
``` let foo = [ item1 myFunction "arg1" "arg2" item3 ] ```
defines a list with 5 items, not 3, due to missing parentheses around the function call.
2. how do you feel about array initialization in C?
3. you can think of {...} as defining memory regions, curlies around code are defining "a memory block of instructions"
I find the rust equivalent much more intuitive `let a: [i32; 3] = [1, 2, 3];`
.{i32, 3} is a valid term in zig.
For example, with this input:
$ cat data.file
root: parentA parentB
parentA: C D
parentB: E F
$ ./zig-out/bin/toposort-cli --data data.file
Processing succeeded.
Topologically sorted sets: [ { C D E F } { parentA parentB } { root } ]
Topologically sorted list: [ C D E F parentA parentB root ]
Nodes: [ root parentA parentB C D E F ]
Dependency tree:
[ C D E F ]
C -> [ parentA ]
parentA -> [ root ]
root ->
D -> [ parentA ]
parentA -> [ root ]
root ->
E -> [ parentB ]
parentB -> [ root ]
root ->
F -> [ parentB ]
parentB -> [ root ]
root ->
How would I use the API of this package to detect and start the task `parentA` as soon as `C` and `D` are finished? I guess when a task is finished, I can ask for the list of dependent tasks, and for each of them, check if all of their dependencies are finished, and if so start the task. But this real-world need feels un-met; it feels odd to me to focus on the sorted sets instead of more practical scheduling.
That is kind of doing Kahn's algorithm iteratively during the build. It would be cool to try and optimize that for maximum performance.
{C D E F}, {parentA parentB}, {root}
What you're asking for is to partition the dependency graph according to node dependency with minimum span.
{ {C D} parentA } \
{ {E F} parentB } - {root}
{ {C D S} parentA } \
{ {E F S} parentB } - {root}
For now, you can send notification to a dependent when the leading task finishes. E.g. When C finishes, notifies parentA. When D finishes, notifies parentA. When parentA notices that all its leading tasks have done, it can start.
The library can help in maintaining the dependency relationship and let the task query its leaders and dependents.
For task running, it would be a separate library using the TopoSort library and specifically geared toward scheduling tasks.
It is actually more commonly implemented than any other algorithm in CS course
In JavaScript:
function toposort(graph = { a: ['b', 'c'], b: ['d'] }) {
const order = [];
const visited = new Map();
function dfs(node) {
const status = visited.get(node);
if (status === 1) throw new Error("Cycle found.");
if (status === 2) return;
visited.set(node, 1); // In progress.
const adjacent = graph[node] ?? [];
for (const neighbor of adjacent) dfs(neighbor);
visited.set(node, 2); // Done.
order.unshift(node); // Reverse post order.
}
for (const node in graph) {
if (!visited.has(node)) dfs(node);
}
return order;
}https://docs.python.org/3/library/graphlib.html
I haven't used it yet, I'd be curious if anyone has
The purpose of adding it to the standard library was to implement linear MRO for classes: https://bugs.python.org/issue17005
I run it in production for many customers. It's great to have this in the std lib.
Not as common as array sort. But still common.
Unsure how this is defined (*) but graph cutting approaches to concurrent task scheduling is both pessimistic (poor utilization of available resources) and (iirc) NP-hard, so you pay an big cost upfront.
On the other hand, if you know the indegree/outdegree of each node at the time they are visited (meaning the graph is static) you can run Kahn's algorithm concurrently and put each node into a shared work queue. You can optimize that further by having per-thread work queues and stealing between them. Depending on what the nodes represent there are even more optimizations and heuristics, concurrent task scheduling is a hard problem.
* imagine the graph
(a, b) (a, c) (b, d) (c, d)
Is it possible to get nodes b and c in parallel "subsets" in your library?
Topologically sorted sets: [ { d } { b c } { a } ]
Topologically sorted list: [ d b c a ]
Nodes: [ a b c d ]
Dependency tree:
[ d ]
d -> [ b c ]
b -> [ a ]
a ->
c -> [ a ]
a ->
They serve as the root set to the rest of the graph for the current round. The depending nodes reached from root set have their in-degree decremented. When their in-degrees reach 0, they are added to the next root set.
I'm using double-buffering to maintain the current root set for processing and to collect the next root set for the next round, instead of using a queue as in Kahn's algorithm. At the end of the round, I simply swap the double-buffers. It's very efficient. When the next root set is empty, all nodes have been processed.
I believe what you've implemented is equivalent to Kahn's algorithm. Your double buffer is the queue.
// This is a variant to the Kahn's algorithm, with additions on
// finding dependence-free subsets and finding the cyclic nodes.
//
// This algorithm iteratively finds out the root sets of the graph.
// 1. Find the first root set of the graph.
// 2. Remove the nodes of the root set from the graph.
// 3. Find the next root set, until graph is empty.
// A root set consists of nodes depending on no other nodes, i.e.
// nodes whose incoming link count is 0.FWIW we had to build a related lib in TypeScript: https://github.com/okcontract/graph as part of the runtime of https://github.com/okcontract/cells
Testing 1000000 items, 1-to-1 chaining dependency.
Add dependency 1000000 items. Time: 93ms, 10645885 items/s, 93 ns/item
Sort 1000000 items. Time: 113ms, 8795778 items/s, 113 ns/item
Testing 1000000 items, 1-to-4 chaining dependency.
Add dependency 1000000 items. Time: 87ms, 11428323 items/s, 87 ns/item
Sort 1000000 items. Time: 44ms, 22508986 items/s, 44 ns/item
Testing 1000000 items, 1-to-10 chaining dependency.
Add dependency 1000000 items. Time: 102ms, 9748793 items/s, 102 ns/item
Sort 1000000 items. Time: 31ms, 31707077 items/s, 31 ns/item
Testing 1000000 items, 1-to-10 chaining dependency, with max_range set.
Add dependency 1000000 items. Time: 25ms, 39460028 items/s, 25 ns/item
Sort 1000000 items. Time: 31ms, 31633556 items/s, 31 ns/item