Namespace Directed

Directed graphs

Graph vertices (ie. nodes) connect to each other along edges. This is 'directed' in that connections are not necessarily mutual. A can connect to B without B connecting to A.

Connections can have an optional weight, defaulting to 1.

Example: Creating a directed graph A connects to B and C; B connects to C. C has edges.

let g = Directed.graph(
 { from: `a`, to: [`b`, `c`] },
 { from: `b`, to: `c` }
 );

Graphs do not store data directly, only the relation between vertices. Each vertex has an id, so to associate data, use a map along with the graph.

Functions

adjacentVertices: Iterate over all the vertices connected to context vertex
areAdjacent: Returns true if a->b or b->a
bfs: Iterates over vertices from a starting vertex in an bread-first-search
clone: Clones the graph. Uses shallow clone, because it's all immutable
connect: Connect from -> to. Same as connectWithEdges, but this version just returns the graph.
connectTo: Make a connection between two vertices with a given weight. It returns the new graph as wll as the created edge.
connectWithEdges: Connect from -> to. Same as connect except you get back the edges as well.
createVertex: Create a vertex with given id
dfs: Iterates over vertices from a starting vertex in an depth-first-search
disconnect: Returns a mutation of graph, with a given edge removed.
distance: Returns the weight of an edge, or 1 if undefined.
distanceDefault: Default distance computer. Uses weight property of edge, or 1 if not found.
dumpGraph: Return a string representation of the graph for debug inspection
edges: Iterate over all the edges in the graph
get: Returns Vertex under key, or undefined if not found.
getCycles: Get all the cycles ('strongly-connected-components') within the graph Read more
getOrCreate: Gets a vertex by id, creating it if it does not exist.
getOrFail: Gets a vertex by id, throwing an error if it does not exist
graph: Create a graph
graphFromVertices: Create a graph from an iterable of vertices
hasKey: Returns true if graph contains key.
hasNoOuts: Returns true if vertex has no outgoing connections
hasOnlyOuts: Returns true if vertex only has the given list of vertices. Returns false early if the length of the list does not match up with vertex.out
hasOut: Returns true if vertex has an outgoing connection to the given vertex.
isAcyclic: Returns true if the graph contains is acyclic - that is, it has no loops
pathDijkstra: Compute shortest distance from the source vertex to the rest of the graph.
toAdjacencyMatrix: Returns the graph connections as an adjacency matrix
topologicalSort: Topological sort using Kahn's algorithm. Returns a new graph that is sorted
transitiveReduction: Returns a new graph which is transitively reduced. That is, redundant edges are removed
updateGraphVertex: Updates a vertex by returning a mutated graph
vertexHasOut: Returns true if vertex has an outgoing connection to the supplied id or vertex.
vertices: Iterate over all the vertices of the graph

Type Aliases

ConnectOptions: Options for connecting vertices
DirectedGraph: Directed graph. Immutable.
DistanceCompute
Edge: Edge. Immutable.
Vertex: Vertex. These are the nodes of the graph. Immutable.

Namespace Directed

Example: Creating a directed graph A connects to B and C; B connects to C. C has edges.

Functions

Type Aliases

Settings

On This Page