topo-strict
Strict topological sorting, with API inspired by topo.
Basic Usage
The basic API is fairly similar to topo
. You can create an instance of
Problem
and add items to it, then solve using the Problem#solve
method:
const Problem = ; const morning = ; morning; morning; morning; console;// [ 'Make toast', 'Pour juice', 'Eat breakfast', 'Nap' ]
The Rules
True to the name, topo-strict
enforces several rules that are not enforced by
topo
, and leverages Nani to produce
detailed errors whenever something goes wrong. The rules are as follows:
-
Strings added to a Problem-- henceforth known as ids-- must be unique, and must not be empty.
-
Strings provided to the
group
option-- henceforth known as group keys-- must also be non-empty and may not share a value with any ids in the Problem. -
Strings provided to the
before
andafter
options-- henceforth known as constraint keys-- need not reference existing ids or group keys at the time they are added, but must do so by the the timesolve
is called.
Violating any of these rules-- or providing non-string values to any of these
options-- will cause a ValidationError
that contains KeyErrors
identifying
all bad keys-- that is, ids, group keys, or constraint keys-- making it easy to
tell exactly what went wrong.
topo
Advantages vs. -
The strict enforcement of the rules above makes
topo-strict
more appropriate for situations where you really want to make sure nothing unexpected ever happens-- where failing fast with detailed errors is preferable-- such as dependency ordering that occurs when a server starts up. -
topo
only allows referencing of group keys throughbefore
andafter
constraints. Any ungrouped items cannot be sorted topologically. This means that in order to make a truly extensible dependency order, you have to specify a group with everything you add, even if you don't intend to add anything else to the group. -
The final order of ids from
topo-strict
is completely independent of insertion order. Instead, a single canonical solution is found by prioritizing ids alphabetically. This is critical if you don't want the order of youradd
calls-- essentially an implementation detail-- to influence the result. -
topo-strict
supports several additional signatures to theadd
method, described below. -
topo-strict
also comes with some features for easily viewing the Problem and the graph that will be used to solve it, also described below. -
topo-strict
does not attempt to solve the problem until you callsolve
, whereastopo
solves it after every single call toadd
. This is unlikely to make a significant difference performance-wise unless you have a huge number ofadd
calls, so it's hardly worth noting. I noted it anyway, though. :)
topo
Disadvantages vs -
topo-strict
does not yet support merging, astopo
does. The rules and validation approach make this feature quite a bit more complicated, so I've put off implementing it until I personally need it for something. I'm happy to accept contributions from anybody who might want it sooner. -
The rules of
topo-strict
are obviously not always appropriate, and in situations where you'd rather be loose and simple you should probably usetopo
. -
topo-strict
has a much larger footprint thantopo
, not least of which because it depends on the whole oflodash
, sotopo
will usually be more appropriate for use in browsers. -
Because
topo-strict
does not attempt to solve the Problem until you callsolve
, it won't detect cycles at the moment you create them, the waytopo
does.
More Stuff
A few more features of topo-strict
will be discussed here. You can read about
anything else in the api docs.
add
Signatures
Alternate When you're adding stuff to a Problem, you can use the signatures demonstrated in Basic Usage above, or you can do these:
// Options-only formproblem; // Shorthand form with multiple ids.problem; // Multiple arrays of ids.problem; // Go crazy with it if you want...problem;
Debugging and Visualization Features
If you want to see a summary of the the whole problem, you can use the
Problem#toString
method:
console;/*ids---Eat breakfastMake toast before: breakfastNap after: breakfast after: prepPour juice before: breakfast groups------breakfast Eat breakfastprep Make toast Pour juice*/
The Problem class also exposes the #toGraph
method, which returns an instance
of Graph
which also implements the #toString
and #solve
methods. This
allows you to preview the directed graph that's used to solve the problem before
solving it:
const morningGraph = morning; console;/*nodes-----Eat breakfastMake toastNapPour juice edges-----from: Eat breakfast, to: Napfrom: Make toast, to: Eat breakfastfrom: Make toast, to: Napfrom: Pour juice, to: Eat breakfastfrom: Pour juice, to: Nap*/ console;// [ 'Make toast', 'Pour juice', 'Eat breakfast', 'Nap' ]
Like Problem#solve
, Problem#toGraph
with throw a ValidationError
if any
constraint keys reference ids or group keys do not exist in the problem, and
like Graph#solve
will throw a CycleError
if a cycle is detected in the
graph.
Both the Problem and Graph classes also expose #toObject
methods, which are
the basis for the #toString
methods. This saves you the trouble of parsing the
above strings, if you're looking to implement your own visualization:
const inspect = ; console;/*{ ids: [ { key: 'Eat breakfast', constraints: [] }, { key: 'Make toast', constraints: [ { type: 'before', key: 'breakfast' } ] }, { key: 'Nap', constraints: [ { type: 'after', key: 'breakfast' }, { type: 'after', key: 'prep' } ] }, { key: 'Pour juice', constraints: [ { type: 'before', key: 'breakfast' } ] } ], groups: [ { key: 'breakfast', ids: [ 'Eat breakfast' ] }, { key: 'prep', ids: [ 'Make toast', 'Pour juice' ] } ] }*/ console;/*{ nodes: [ 'Eat breakfast', 'Make toast', 'Nap', 'Pour juice' ], edges: [ { from: 'Eat breakfast', to: 'Nap' }, { from: 'Make toast', to: 'Eat breakfast' }, { from: 'Make toast', to: 'Nap' }, { from: 'Pour juice', to: 'Eat breakfast' }, { from: 'Pour juice', to: 'Nap' } ] }*/