Tsort

It involves picking a sequence of tasks to complete. They have a given ideal order but some tasks are dependent on others, and this often conflicts with the ideal order. My strategy is to get the top priority task done ASAP. But I still needed to order the prerequisites for the top priority task...

Wayne Conrad Wayne Conrad I wonder if a topological sort would be good for that. Ruby has a topo. sort built in, which is kinda cool.

Jan Dvorak Jan Dvorak 15:56 oh?

Wayne Conrad Wayne Conrad One of my apps uses it for just that purpose. Let me get something more useful for you.

Jan Dvorak Jan Dvorak A general topological sort isn't hard - always pick a task you can do at random. But it's not super-efficient at getting the top-priority task done quickly.

Wayne Conrad Wayne Conrad ruby-doc.org/stdlib-2.4.1/… I have an app that does a topo sort but also considers priority. Let me see how I did that.

Jan Dvorak Jan Dvorak Nice. I'll take a look.

https://ruby-doc.org/stdlib-2.4.1/libdoc/tsort/rdoc/TSort.html

I have an app that does a topo sort but also considers priority. Let me see how I did that.

Jan Dvorak Jan Dvorak Nice. I'll take a look. Can I include a module into the top scope?

Wayne Conrad Wayne Conrad 58k Yes. each_node = lambda do |&block| @klasses.sort_by(&:priority).each(&block) end each_child = lambda do |node, &block| node.dependencies.each(&block) end a = TSort.tsort(each_node, each_child, &block) Ruby's topo. sort is stable, so just sort the nodes by priority first.

Jan Dvorak Jan Dvorak 16:01 Nice. Now, some of the tasks I have require a certain number of other tasks to be completed first but they aren't particular in which ones.

Wayne Conrad Wayne Conrad By the way, if you go to use that, I'm not sure about the last arg to TSort.tsort (&block). That might be a goof and is unneeded. @JanDvorak That's special! I guess the each_child lambda could just order dependencies at random and slice off a certain number of them.

Jan Dvorak Jan Dvorak That was my previous strategy, but it isn't optimal.

Wayne Conrad Wayne Conrad Confirmed: a = TSort.tsort(each_node, each_child, &block) should be a = TSort.tsort(each_node, each_child) topo. sort is one of my Ruby secret weapons. I use it often in order to make myself look amazing.

Jan Dvorak Jan Dvorak Let's say A requires B and C, B being more important. B only requires any task to be completed first, C requires D specifically. E will be chosen to satisfy B, but D is better as it will be needed later anyways.

Wayne Conrad Wayne Conrad So B has dependent tasks (prerequesites), but as long as any one of them is done, the prerequisite is met?

Jan Dvorak Jan Dvorak 16:07 B can be satisfied by any task at all.

Wayne Conrad Wayne Conrad I wonder if there's something done by each task that should be broken out into its own task that is a prereq. for every other task.