Table of Contents generated with DocToc
Creating a graph and populating it with nodes and edges; the node labels
appear in natural order (
LTSORT.add g, a, b meaning that
b depends on
been done first):
LTSORT = require 'ltsort'graph = LTSORTnew_graph loners: noLTSORTadd graph'buy books''do some reading'LTSORTadd graph'buy books''go home'LTSORTadd graph'buy food''cook'LTSORTadd graph'buy food''go home'LTSORTadd graph'buy food''have a coffee'LTSORTadd graph'cook''eat'LTSORTadd graph'do some reading''go to exam'LTSORTadd graph'eat''do some reading'LTSORTadd graph'eat''go to exam'LTSORTadd graph'fetch money''buy books'LTSORTadd graph'fetch money''buy food'LTSORTadd graph'go home''cook'LTSORTadd graph'go to bank''fetch money'LTSORTadd graph'have a coffee''go home'tasks = LTSORTgroup graph
tasks is now a list of lists:
'go to bank''fetch money''buy books''buy food''have a coffee''go home''cook''eat''do some reading''go to exam'
which tells me that I'd have to cook before you eat, that I can only buy foods and books with some money on my hands, but that buying foods and books can happen in any order, and so on.
Create a new graph object.
settings, if used, may be an object containing a single named
loners, which should be
false; it is only relevant for
LTSORT.group, for which see below. Alternatively,
may be a graph itself, in which case a copy of that graph will be returned.
@add graph, lhs, relation = null, rhs = null
Add a node or an edge to the graph. Possible forms are:
LTSORT.add graph, 'A'—add a node labelled
Ato the graph.
LTSORT.add graph, 'A', 'B'—add an edge to the graph that states that node
Amust precede node
Bwill be added implicitly if not already present in the graph.
@populate graph, elements
elements to the
elements should be a list of strings
and pairs of strings; single strings will be registered as nodes and pairs
of strings will be interpreted as precedent/consequent pairs. For example:
graph = LTSORTnew_graphelements ='A''X''B''X''F''X''Y''X''Z'LTSORTpopulate graphelements
@delete graph, name
Remove the node identified by
graph. Currently, only nodes
that have no precedents (i.e. root nodes, including unconnected ('lone') nodes)
may be deleted. This is used by
@has_node graph, name
graph has a node labelled with
graph has any nodes at all.
@is_lone_node graph, name
Return whether the node labelled
name is a 'lone' node (i.e. one without precedents
and without consequents; a node that is not part of any edge). Will throw an error
graph doesn't have a node labelled
@find_lone_nodes graph, root_nodes = null
Return a list of all lone nodes in the graph.
@find_root_nodes graph, loners = null
Return a list of all root nodes in the graph (i.e. those nodes that have no precedents /
depend on nothing else in the graph). If
loners is given and true, that list will
include lone nodes; if it is given and false, that list will exclude lone nodes. If
loners is not given, the graph's
loners property will be used instead.
Linearity of a given dependency graph measures how well the dependency relations in a graph determine an ordering of its nodes. For a graph that defines a unique, single chain of antecedents and consequents, linearity will be 1; for a graph that defines only nodes and no dependency edges, linearity will be zero; for all other kind of graphs, linearity will be close to the inverse of the average group length.
Linerarity is directly related to how many groups (of mutually independent nodes) there are in the graph
and how many nodes they contain; for example, here are the results of the
LTSORT.group graph method and
the respective linearity values:
'A' 'B' 'C'1
Return a list with node labels, ordered such that all consequents come after their
precedents. In other words, in a graph where edges represent dependencies and
where a given task
y depends on task
x having been finished, its
linearization will spell out one way in which to perform actions such that all
x come before any of their dependent tasks
y. For example:
graph = LTSORTnew_graphelements ='A''X''B''X''F''X''Y''X''Z''δ''B''Z''Ψ''Ψ''Ω''Z''Ω''β''A''α''β'LTSORTpopulate graphelementstasks = LTSORTlinearize graph
tasks now equals
(although the exact placement of some nodes such as
F is not guaranteed). Going
through the precedence rules given, we can ascertain this result is 'sufficiently
good' to base a step-by-step procedure upon:
α ⇒ βwas specified, and, indeed,
βin the linearization.
A ⇒ Xand
B ⇒ Xwere specified, and, indeed, both
X, and they indeed come after
δ ⇒ B ⇒ Xwas specified, and, indeed,
Xappear in that order.
@group graph, loners = null
LTSORT.linearize, but return a list of lists instead. Using the same
setup as shown above, but using
LTSORT.group instead of
tasks = LTSORTgroup graph
Each element in the list represents a number of steps that may be performed in
any order or in parallel (i.e. tasks that are independent of each other). Here
we have created the graph with an (implicit) setting
loners: true, which
causes lone tasks to be singled out as the first (possibly empty) list; had we
created the graph with
loners: false (or called
LTSORT.group graph, false), the first group of tasks would have become
[ 'F', 'δ', 'α' ].
Observe that (1) the ordering of nodes within each group is not defined;
it may or may not change when nodes and edges are added in a different order;
(2) tasks appear as soon as possible in the listing, meaning that there's
a chance that a given task could be accomplished later than indicated here. As
LTSORT.linearize, the result given is just one possible solution to
the constraints given, and not necessarily the only one.