graph-adt
v0.9.0
Published
Graph ADT library
Downloads
11
Readme
- Motivation
- API
- Tips and gotchas
- Related
Status
- 0.7.0 is fine
- 0.8.0 fails with babel (because of generators? to be investigated)
Motivation
We had trouble finding a library for graph data structure which addresses our requirements. The principal need and motivator for now is model-based testing (MBT): a reactive system is modelled as a state-machine, which itself can be modelled as a multidigraph, or quiver. We could not find libraries which can handle such constructs. To generate input sequences for model testing, we need to examine the associated graph in a certain number of ways. This library aims at gathering such ways.
As such it is not and does not intend to be a all-purpose graph manipulation library. It just has what we need for model-based testing. Typically, the model coverage criteria used in MBT for transition-based models are :
- all paths: Every path traversed at
least once (exhaustive
testing of control structure)
- all transition pairs: Every pair of adjacent
transitions traversed
at least once
- all transitions: Every transition of the model traversed at least once
- all states: Every state is visited at least once
- all one-loop paths: Visit all the loop-free
paths plus all the
paths that loop once
- all round trips: Test each loop (iterate only once), but no need to check all paths preceding or following a loop (transition coverage required)
- all loop-free paths: Every loop-free (no repetition of config/ states) path traversed at least once
- all transition pairs: Every pair of adjacent
transitions traversed
at least once
We currently offer :
- enumeration of all edge paths between two vertices, with a configurable maximum for edge repetition
- generic graph edge search, which can be customized to implement some of the criteria presented thereabove
This was chosen for pragmatic reasons. From this included algorithm, it is possible to implement most of the above-mentioned coverage criteria.
API
Types
/**
* @typedef {Object} Edge Edge must be an object (we use referential equality so this is to avoid surprises with
* equality of native types)
*/
/**
* @typedef {Array<Edge>} EdgePath
*/
/**
* @typedef {Object} Vertex Vertices must be an object (we use referential equality so this is to avoid surprises with
* equality of native types)
*/
/**
* @typedef {Object} EdgeADT
* @property {function(Edge) : Vertex} getEdgeTarget
* @property {function(Edge) : Vertex} getEdgeOrigin
* @property {function(Vertex, Vertex) : Edge} constructEdge
*/
/**
* @typedef {Object} Graph
* @property {function (Vertex) : Array<Edge>} outgoingEdges
* @property {function (Vertex) : Array<Edge>} incomingEdges
* @property {function (Vertex) : Array<Vertex>} getNeighbours
* @property {function (Vertex) : Array<Vertex>} vertices
* @property {function (Vertex) : Array<Vertex>} edges
* @property {function (Vertex) : Array<Vertex>} settings
* @property {function (Edge) : Vertex} getEdgeOrigin
* @property {function (Edge) : Vertex} getEdgeTarget
* @property {function(Vertex, Vertex) : Edge} constructEdge
* @property {function (Vertex) : ()} showVertex
* @property {function (Vertex) : ()} showEdge
* @property {function () : ()} clear free any resources that was used
*/
/**
* @typedef {Object} FindPathSettings
* @property {Number} [maxNumberOfTraversals=1] a number greater or equal to 0. Set to 1 by default
* @property {String} [strategy='BFS'] search strategy : depth-first or breadth-first (default)
*/
/**
* @typedef {() => Store<P>} StoreFactory Store constructor
* @constructor
*/
/**
* @typedef {Object} StoreInterface
* @property {Store<P> | StoreFactory} empty empty store or constructor for an empty store
* @property {function (Array<P>, Store<P>) : Store<P>} add adds a list of values into a store
* @property {function (Store<P>) : {popped, newStore: Store<P>}} takeAndRemoveOne empty store. removes one value
* from the store and returns that value and the new store without that value
* @property {function (Store<P>): Boolean} isEmpty predicate which returns true iff the store is empty
* @template P
*/
/**
* @typedef {Map} GraphTraversalState `graphTraversalState` is shared state between search, result accumulation and
* visiting functions. As such it must be used carefully. Ideally it is not necessary. If it is necessary then only
* one function should modify it while the others read from it. That eliminates the need to think about order of
* function application.
*/
/**
* @typedef {{value:*, isProduced:Boolean}} SearchOutput
*/
/**
* @typedef {Object} SearchSpecs
* @property {function (Edge, Graph, PathTraversalState, GraphTraversalState) : {graphTraversalState : GraphTraversalState, isGoalReached : Boolean, output: SearchOutput} } evaluateGoal predicate which assesses whether a given goal is reached, or if instead the search should continue. To assess the goal, the provided information is the edge being visited, and the current edge traversal state (roughly the sequence of edges visited so far). If the goal is reached, this means we have some results for the search, and those results are aggregated somewhere in the graph traversal state for posterior extraction through `showResults`.
* @property {*} initialGoalEvalState seed for the reducer associated to goal evaluation
* @property {function (GraphTraversalState) : Search<Result>} showResults returns the accumulated results which
* have been stored in the graph traversal state
*/
/**
* @typedef {*} PathTraversalState
*/
/**
* @typedef {{initialPathTraversalState:*, visitEdge : ReducerEdge}} VisitSpecs
*/
/**
* @typedef {function (Edge, Graph, PathTraversalState, GraphTraversalState) : {isTraversableEdge :Boolean, pathTraversalState:PathTraversalState}} ReducerEdge
* function which visit the edge, updates the state of the edge traversal, and evaluates if the visited edge
* should be included in the search (`isTraversableEdge` set to true) or not.
*/
/**
* @typedef {*} Result
*/
Contracts
Both edges and vertices must be objects! The good behaviour of the library is not guaranteed for edges or vertices having native types.
constructGraph :: EdgeADT -> Array -> Array -> Graph
A graph is constructed from its array of edges and its vertices. An edge itself must contain two vertices. A vertex can be anything.
A complete description should be :
- V a set of vertices or nodes,
- A a set of edges or lines,
source :: e -> V
, assigning to each edge its source node,target :: e -> V
, assigning to each edge its target node.
This happens to coincide exactly with the signature of our graph constructor -- though instead of sets, we use arrays.
The array of vertices is mandatory, and must contain any and every vertex part of the graph. This means in particular that no edge can be based on vertices which do not figure in the passed vertex array. This is checked by contract, by means of referential equality.
findPathsBetweenTwoVertices :: FindPathSettings -> Vertex -> Vertex -> Graph -> Array
Finds all paths between two vertices in a graph. Note that a path here is not an array of vertices but an array of edges. This is a requirement as we commonly deal in MBT with graphs with several guards between two states, with same-state transitions, and other circles.
If such paths exist, they are computed and returned in the form of array in which all elements are unique, i.e. there are no two same paths, with sameness defined by referential equality of the contained edges.
It is possible to configure the maximum number of occurrences of a given edge in a path. Sameness is defined by referential equality. The default value is set to 1 (no repetition of a given edge - this ensures loop-free paths). Settings that parameter to a value greater than 1 allows to have some control over the traversal of the graph cycles.
searchGraphEdges :: TraversalSpecs -> Vertex -> Graph -> SearchResults
Search algorithm
We did not bother much with a sophisticated algorithm. A collection of search algorithms can be found in the assets directory of this repository. We used an iterative version of a brute-force enumeration algorithm, adapted for the need of enumerating edges, accounting for loops, cycles, and multi-edges. The algorithm can be found in Enumeration algorithm, p14
Description
The function findPathsBetweenTwoVertices
uses under the hood the search algorithm implemented by
searchGraphEdges
. searchGraphEdges
returns results from the graph search starting from a
given vertex , based on the configuration passed in TraversalSpecs
.
TraversalSpecs
contains three properties (search
, store
, visit
) respectively dictating what are
and how to build search results (for instance a result is a path between given origin and target
and is to be aggregated in an array), the traversal order (for instance breadth-first), and the
traversal criteria (for instance do not pass through the same edge twice).
The search
property contains the following properties : initialGoalEvalState
, evaluateGoal
,
showResults
, respectively specifying :
- the initial value for the search state (generally an empty container of results)
- when a search is successful (
isGoalReached
), what/if to output as a result (output
), and the update of the search state (graphTraversalState
). - the final output of the search. This is generally a data structure containing all results.
The visit
property contains the following properties : initialPathTraversalState
,
visitEdge
, respectively specifying :
- the initial value for the traversal state
- whether a traversal candidate edge should indeed be traversed (
isTraversableEdge
) or alternatively the search should backtrack, and the update of the traversal state (pathTraversalState
).
The store
property contains the following properties :
empty
: empty storeadd
: adds elements to the storetakeAndRemoveOne
: remove an element from the store and returns a store with the same elements except the removed elementisEmpty
: predicate which returns true iff the store is empty
For instance, for the findPathsBetweenTwoVertices
function:
- the store is a queue or a stack according to whether we want a
BFS
orDFS
search visitEdge
accumulates all traversable edges in an array (withinitialPathTraversalState
initially an empty array), forming an edge path. A traversable edge being an edge such that when added to the current edge path, does not feature more than a given number (maxNumberOfTraversals
) of edge repetition.isGoalReached
returns true iff the final edge of the current edge path is the target vertex.graphTraversalState
, initially an empty array (initialGoalEvalState
, accumulates results, i.e . the paths we have found which fulfiil our search criteria). FinallyshowResults
simply outputs the accumulated array.
As such, the searchGraphEdges
is fairly generic, and can implement a large variety of
graph (edge) searches. Among the thing which can be done :
- probabilistic searches, or prefix searches can be done by configuring the
store
property, all else being equal
The invariant part of the function, is that for any traversed edge, the outgoing edges from that edge will be enumerated as potential traversable edges. What is a traversable edge and how those edges are eventually accumulated into search results is the parameterizable part of the function.
Semantics
- we start with initializing the search state, the traversal state and an empty store
- we start the enumeration with adding to the store the outgoing edges of the initial vertex
- for any edge in the store, we removed the edge from the store and visit it
- if the edge is not traversable, we continue reviewing edges in the store
- if the edge is traversable, it is traversed
- we evaluate if the search goal is reached
- if the search goal is reached, we update the search state and possibly compute and output the result of the search
- if the search goal is not reached, we add the outgoing edges for the traversed edge to the store, and update the traversal state
- we continue reviewing edges in the store
- we evaluate if the search goal is reached
Contracts
The following contracts apply : type contracts, graph contracts, edge contracts, vertex contracts.
We could consider it an implicit contract that the search must terminate, i.e. that the search
parameters (in particular isGoalReached
and isTraversableEdge
) have to be configured in a way
that the store eventually returns to being empty. This is not enforced but important as a graph
may have loops in which case the enumeration of edge paths would be infinite.
searchGraphEdgesGenerator
The searchGraphEdgesGenerator
follows the same algorithm as searchGraphEdges
, except for the
fact that when a search result is found, that result is yielded to the function caller.
searchGraphEdgesGenerator
is indeed a generator, which when called returns an iterator. That
iterator, for each next
call will return a new search result, till the enumeration is finished
(emptied store). Note that the generator returns the list of all found results. As usual, the
return value of a generator cannot be retrieved in a for..of
loop. We provide the
getIteratorReturnValue
function to that purpose.
We included this version of the search because :
- for large graphs, or graph featuring loops, the enumeration may be expensive, and we might want
to instead process results one by one, instead of computing them synchronously and process the
whole results
- this is typically the case for testing, where we want to have tests failing as soon as possible
- in particular the enumeration may be infinite, and we might be interested in only some of the results, and want to stop the iteration at discretion
- we can interface it for further processing with :
- transducers (for instance transducers-js)
- iterator combinators for processing (for instance
ixjs
, the pull version ofrxjs
) - property-based testing libraries (jsverify, or jscheck)
Contracts
Same contracts as searchGraphEdges
, except that the implicit contract that the search must
terminate can be relaxed.
Provided searches
For the sake of our needs, we provided two parameter presets (a preset is a
configuration of isTraversableEdge
, and isGoalReached
):
ALL_n_TRANSITIONS
: will reject edge paths which features more thann
repetitions of any given edge. A successful search is the one generating an edge path whose final edge has a given target vertexALL_TRANSITIONS
:ALL_n_TRANSITIONS
with n = 1.
This is specific to our state transducer library and our need to automatically generate test sequences.
In that context, note that ALL_TRANSITIONS
helps enumerating a set of paths (input tests)
which includes all transitions from a given vertex to a target vertex. That set of paths however
is not the minimal set of such paths. It is in fact the maximal set. As there is no unicity of
the minimum set, we chose to enumerate the maximal set and let the user pick from that set the
sequences he favors.
Tests
Tests can be run with npm run test
Examples
Examples can be found in the test directory
Tips and gotchas
- edges which are not reachable from the starting vertex won't be reached. That sounds obvious but it is easy to forget.
- the
GraphTraversalState
can be used to implement early termination of the search. Typicallyvisit
would update some flag in the graph traversal state, andisTraversableEdge
would not produce any further edges after consulting that flag.