T is the node type of the graph. Nodes can be anything in all the included examples they are simple objects.
Adds an edge to the graph similarly to DirectedGraph.addEdge but maintains correctness of the acyclic graph.
Thows a CycleError if adding the requested edge would create a cycle.
Adding an edge invalidates the cache of topologically sorted nodes, rather than updating it.
The identity string of the node the edge should run from.
The identity string of the node the edge should run to.
Depth first search to see if one node is reachable from another following the directed edges.
Caveat: This will return false if startNode and endNode are the same node and the is not a cycle or a loop edge connecting them.
The string identity of the node to start at.
The string identity of the node we are attempting to reach.
Returns a specific node given the node identity returned from the insert function
This simply returns all the nodes stored in the graph
An optional function that indicates the sort order of the returned array
Given a starting node this returns a new [[DirectedA]] containing all the nodes that can be reached.
Throws a NodeDoesntExistError if the start node does not exist.
The string identity of the node from which the subgraph search should start.
The indegree of a node is the number of edges that point to it. This will always be an integer.
Throws a NodeDoesntExistError the node does not exist.
The string of the node identity of the node to calculate indegree for.
Inserts a node into the graph and maintains topologic sort cache by prepending the node (since all newly created nodes have an indegree of zero.)
The node to insert
Returns true if there are no cycles in the graph.
This relies on a cached value so calling it multiple times without adding edges to the graph should be O(1) after the first call.
Non-cached calls are potentially expensive, the implementation is based on Kahn's algorithim which is O(|EdgeCount| + |NodeCount|).
This replaces an existing node in the graph with an updated version.
Throws a [[NodeDoesNotExistsError]] if no node with the same identity already exists.
__Caveat_:_ The default identity function means that this will never work since if the node changes it will have a different hash.
The new node that is replacing the old one.
Topologically sort the nodes using Kahn's algorithim. Uses a cache which means that repeated calls should be O(1) after the first call. Non-cached calls are potentially expensive, Kahn's algorithim is O(|EdgeCount| + |NodeCount|). There may be more than one valid topological sort order for a single graph, so just because two graphs are the same does not mean that order of the resultant arrays will be.
An array of nodes sorted by the topological order.
The node to insert or update
The identity string of the node inserted or updated.
Checks if adding the specified edge would create a cycle.
Returns true in O(1) if the graph already contains a known cycle, or if fromNodeIdentity and toNodeIdentity are the same.
The string identity of the node the edge is from.
The string identity of the node the edge is to.
Converts an existing directed graph into a directed acyclic graph.
Throws a CycleError if the graph attempting to be converted contains a cycle.
The source directed graph to convert into a DAG
Generated using TypeDoc
DirectedAcyclicGraph
A DirectedAcyclicGraph is builds on a
DirectedGraphbut enforces acyclicality. You cannot add an edge to a DirectedAcyclicGraph that would create a cycle.