41–48 of 48 posts
Earlier quoted context omitted.
The array syntax is very offensive: `const a = [3]i32{ 1, 2, 3 };` A set is denoted by braces, not an array.
This is exactly why I find the language unintuitive. I don't understand why they made the choices they made. For example, why curly brackets? I find the rust equivalent much more intuitive `let a: [i32; 3] = [1, 2, 3];`
.{i32, 3} is a valid term in zig.
Earlier quoted context omitted.
That's a great point! Unfortunately Topological Sort generates a linear order, forcing nodes to run one after another. This library attempts to bring some parallel processing into the picture by grouping dependence-free nodes together. This produces a linear batches. {C D E F}, {parentA parentB}, {root} Within a batch, nodes can run parallel. Between batches, they still need to run one after another. What you're aski…
Did you use this library on the advent of code 2024? I'd never heard of topological sorting prior to that problem - and it was real early in the game.
It is actually more commonly implemented than any other algorithm in CS course
Earlier quoted context omitted.
Yes. The core algorithm is like 20 lines of code in the run_algorithm() function. But to make it easier to use, to handle different types of input, and report/query output, etc. take much more. This is the difference between an idea and a product in a loose sense. It gives purpose to my learning process anyway.
You have a typo in the code, run_alogrithm() :)
Earlier quoted context omitted.
That's a great point! Unfortunately Topological Sort generates a linear order, forcing nodes to run one after another. This library attempts to bring some parallel processing into the picture by grouping dependence-free nodes together. This produces a linear batches. {C D E F}, {parentA parentB}, {root} Within a batch, nodes can run parallel. Between batches, they still need to run one after another. What you're aski…
Did you use this library on the advent of code 2024? I'd never heard of topological sorting prior to that problem - and it was real early in the game.
Earlier quoted context omitted.
How are the subsets defined?
At every round of the algorithm, all nodes with 0 in-degree (i.e. they are not depending on anyone) are collected as a dependence-free subset. 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 se…
I believe what you've implemented is equivalent to Kahn's algorithm. Your double buffer is the queue.
Earlier quoted context omitted.
At every round of the algorithm, all nodes with 0 in-degree (i.e. they are not depending on anyone) are collected as a dependence-free subset. 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 se…
Do you define "in degree" as the number of incoming edges from nodes that have not been visited/sorted yet? 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. Go to 2 until the graph is empty.
// A root set consists of nodes depending on no other nodes, i.e.
// nodes whose incoming link count is 0.
The in-degree of a node is the count of the incoming links of the leading nodes that the node is depending on. The in-degree can change as other nodes are removed from the graph.
Kahn's algorithm uses a queue to hold the pending nodes and works on one node at a time. My insight is that it's simpler to treat the root nodes as sets, and to partition the root nodes into the current root set and the next root set, which work nicely with the double-buffer mechanism. As a benefit, the nodes in a root set are dependence-free with regard to the current round and can be used for parallel processing.
Earlier quoted context omitted.
Thanks for the reply. 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/a…
I think at one point they rejected the idea, but I think it was from 2018 or so. The cpp attributes does seem like what I'd want, but yeah c++ compile time code isn't good enough for what I need.
Earlier quoted context omitted.
The array syntax is very offensive: `const a = [3]i32{ 1, 2, 3 };` A set is denoted by braces, not an array.
According to your familiarity yes, but how is this such a problem? It’s easy to get past