README
zuvor
THIS IS ALPHA, UNSTABLE, WORK IN PROGRESS !
simple and reasonably fast implementation of DAGs (directed acyclic graphs) and sets as building blocks for dynamically finding the optimal execution order of interdependent tasks with nondeterministic execution times
a task will run at the earliest possible point when it can run
- is it any good?
- how do i install it?
- Set-API
- Dag-API
- is it fast?
- is it stable?
- how is it implemented?
- how can i contribute?
- license
why?
i had a list of tasks where some tasks needed to run before other tasks.
for example: A before B
, C before A
, D before B
, ...
i needed a programatic way to run those tasks in the most efficient order.
i built vorrang to model and query the underlying partial order:
zuvor gives to the building blocks to do exactly that.
browser?
vorrang can be used to model
- shutdown orders
- task orders
- class hierarchies
- ancestor relationships
- taxonomies
- partial orders
- event orders
- production chains
- dependency graphs
- ...
no dependencies
first let's model the task order:
only works with strings
var Vorrang = require('vorrang');
var dag = new Vorrang()
.before('A', 'B')
.before('C', 'A')
.before('D', 'B');
then i can find out what i can run immediately:
dag.minElements();
// => ['C', 'D']
sweet - we can already start tasks C
and D
.
let's assume C
has finished.
vorrang.minUpperBound(dag, ['C', 'D'])
// => ['A']
nice - we can start A
now!
you get the idea...
what can i do with it?
is it stable?
it has a large testsuite!
there are probably bugs.
if you find one i appreciate it if you make an issue.
is it fast?
the current focus is on functionality and correctness rather than performance.
i did not optimize prematurely. i chose the data types carefully. its fast enough for my use case. its probably fast enough for your use case.
if you need something faster and have an idea definitely send me an email or make an issue.
query performance memory usage
it currently uses too much memory
how is it implemented?
here's the code its just x lines
parents
children
ancestors
descendants
in
out
upstream
downstream
how can i contribute?
if you need a function that is not in the API just make an issue and we can discuss and how to implement it best.
i appreciate it if you open an issue first before
API
-> run(options)Promise
run will call callback
once for every id in ids
that is not in done
.
call them
options:
ids
anArray
orSet
of ids to runcallback
aFunction
that is called for each id that is not indone
- can return a promise
graph
aGraph
(optional) that models the dependencies/order between theids
done
an optionalSet
(defaultnew Set()
) that contains- ids that are done are added to the set
- can be used to blacklist
ids
- things that are already done are not run
pending
an optionalSet
(defaultnew Set()
) that contains the ids that have been called and have returned a promise that is not yet resolvedids
in this set will not be called. can be used to blacklistids
.
reversed
aBoolean
(optional, defaultfalse
) whether to treat thegraph
(if present) in reverse orderstrict
an optionalBoolean
(defaultfalse
)debug
strict ignore orderings that dont exist
order between some of them
run returns a promise that is resolved when all things have been run
Set
follows the ECMA6 set API where sensible.
new Set(Nothing or Array or Set)
-> Set
create a set: var emptySet = new Set();
// or
var setFromArgs = new Set(1, 2, 3);
// or
var setFromArray = new Set([1, 2, 3]);
// or
var clonedSet = new Set(setFromArray);
O(n) where n = number of elements in argument array or set
.size
= Integer
number of elements in the set: new Set().size; // -> 0
new Set(1, 2, 3).size; // -> 3
O(1)
.values()
or .keys()
-> Array
return an array of all the elements in the set: new Set().values(); // -> []
new Set(1, 2, 3).values(); // -> [1, 2, 3]
new Set(1, 2, 3).keys(); // -> [1, 2, 3]
O(n) where n = number of elements in the set
.toString()
-> String
return a string representation of the set: new Set().toString(); // -> '#{}'
new Set(1, 2, 3).toString(); // -> '#{1 2 3}'
O(n) where n = number of elements in the set
.equals(Set or Array)
-> Boolean
return whether two sets contain the same elements: new Set().equals(new Set()); // -> true
new Set().equals(new Set(1, 2, 3)); // -> false
var set = new Set(1, 2, 3);
set.equals(new Set(1, 2)); // -> false
set.equals(new Set(1, 2, 3)); // -> true
set.equals(set); // -> true
set.equals([1, 2, 3]); // -> true
set.equals([1, 2]); // -> false
best case if size differs is O(1). worst case is O(n) where n = number of elements in the set
.has(Value)
-> Boolean
return whether a value is in the set: var set = new Set(1, 2, 3);
set.has(1); // -> true
set.has(4); // -> false
O(1)
.add(Value or Array or Set)
-> Set
add elements to the set and return set: var set = new Set();
set.add(1);
// add side effects original set!
set.values(); // -> [1]
set.add(2, 3);
set.values(); // -> [1, 2, 3]
set.add([4, 5]);
set.values(); // -> [1, 2, 3, 4, 5]
set.add(new Set([6, 7]));
set.values(); // -> [1, 2, 3, 4, 5, 6, 7]
// add can be chained
set
.add(8)
.add(9)
.add(10);
set.values(); // -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
O(1) for a single value. O(n) for a set (array) where n = number of elements in the set (array)
.delete(Value or Array or Set)
-> Set
delete elements from the set and return set: var set = new Set(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
set.delete(1);
// delete side effects original set!
set.values(); // -> [2, 3, 4, 5, 6, 7, 8, 9, 10]
set.delete(2, 3);
set.values(); // -> [4, 5, 6, 7, 8, 9, 10]
set.delete([4, 5]);
set.values(); // -> [6, 7, 8, 9, 10]
set.delete(new Set([6, 7]));
set.values(); // -> [8, 9, 10]
// delete can be chained
set
.delete(8)
.delete(9)
.delete(10);
set.values(); // -> []
O(1) for a single value. O(n) for a set (array) where n = number of elements in the set (array)
.clone()
-> Set
return a new set that has the same elements as the set: var set = new Set(1, 2, 3);
var clone = set.clone();
set.equals(clone); // -> true
O(n) where n = number of elements in the set
.clear()
-> Set
delete all elements from the set and return set: var set = new Set(1, 2, 3);
set.size; // -> 3
set.clear();
set.size; // -> 0
O(1)
Graph
Value
= String
or Number
new Graph
-> Graph
create a graph: var graph = new Graph();
O(1)
.add(from Value, to Value)
-> Graph
add an edge and return graph: var graph = new Graph()
.add('a', 'b')
.add('b', 'c')
.add('a', 'c');
O(1)
a
or path from a
to b
exists: .has(a Value, [b Value])
-> Boolean
return whether node var graph = new Graph()
.add('a', 'b')
.add('b', 'c')
graph.has('a'); // -> true
graph.has('d'); // -> false
graph.has('a', 'b'); // -> true
graph.has('b', 'a'); // -> false
// transitive path: a to c via b
graph.has('a', 'c'); // -> true
whether node exists: O(1)
if direct edge between a and b exists: O(1)
if a transitive path between a and b exists: worst case O(n * m) where n is the number of edges in the path and m is the max number of edges connected to any node in the graph.
.values()
or .keys()
-> Array
return an array of all the nodes in the graph: new Graph().values(); // -> []
new Graph()
.add('a', 'b')
.values(); // -> ['a', 'b']
new Graph()
.add('a', 'b')
.keys(); // -> ['a', 'b']
O(n) where n = number of nodes in the graph
.edges()
-> Array
return an array of all the edges in the graph: new Graph() .edges(); // -> []
new Graph()
.add('a', 'b')
.edges(); // -> [['a', 'b']]
O(n) where n = number of edges in the graph
.parentless()
-> Array
return nodes that have no parents (no incoming edges): new Graph()
.add('a', 'b')
.parentless(); // -> ['a']
O(n) where n = number of nodes in the graph
.childless()
-> Array
return nodes that have no children (no outgoing edges): new Graph()
.add('a', 'b')
.childless(); // -> ['b']
O(n) where n = number of nodes in the graph
.whereAllParentsIn(Array or Set)
-> Array
return nodes whose parents are all in array: var graph = new Graph()
.add('a', 'b')
.add('a', 'c')
.add('c', 'd')
.add('b', 'd')
graph.whereAllParentsIn(['a']); // -> ['b', 'c']
// nodes in the source array are not in the output array
graph.whereAllParentsIn(['a', 'b']); // -> ['c']
graph.whereAllParentsIn(new Set('a', 'b', 'c')); // -> ['d']
worst case: O(n * m) where n = number of elements in the array/set and m = max number of parents of any node in the array/set
.whereAllChildrenIn(Array or Set)
-> Array
return nodes whose children are all in array: var graph = new Graph()
.add('a', 'b')
.add('a', 'c')
.add('c', 'd')
.add('b', 'd')
graph.whereAllChildrenIn(['d']); // -> ['c', 'b']
// nodes in the source array are not in the output array
graph.whereAllChildrenIn(['d', 'b']); // -> ['c']
graph.whereAllChildrenIn(new Set('d', 'b', 'c')); // -> ['a']
worst case: O(n * m) where n = number of elements in the array/set and m = max number of children of any node in the array/set
license: MIT
TODO
handle strictness
- build a scenario where that is a problem
- in graph but not in ids and blockings children that depend on it
test edge cases of the run function
document run function in readme
use zuvor run function from blaze for shutdown
finish readme
- read api again
- description
- question sections
- example
example.js (taken from integration test)
npm publish
publish
make sure travis is working
uses and includes a set and a graph datatype
where an order exists only for some services
you can use it for
tasks are run as soon as they are ready to run