Graph
Types
AStarResult
The result of doing an A* search.
| Property | Type |
|---|---|
| cost | number The total cost of tranversing the path. |
| path | Array<Graph.Vertex<T>> On success, contains the path of vertices. |
| status | Graph.AStarStatus Whether the search was successful, timed out, or if there was no path found. |
EdgeDescriptor
A descriptor for a graph edge. Used when adding edges to a graph.
| Property | Type |
|---|---|
| dst | Graph.Vertex<T> The destination vertex. |
| src | Graph.Vertex<T> The source vertex. |
| weight? | number | undefined The weight of the edge. |
VertexDescriptor
A descriptor for a graph vertex. Used when adding vertices to a graph.
| Property | Type |
|---|---|
| data | T Any user data to be associated with this vertex |
| id | string The id that can be used to lookup this vertex in the graph |
VertexIdDescriptor
A descriptor for a graph vertex when no extra data will be associated with each vertex. Used when adding vertices to a graph.
| Property | Type |
|---|---|
| id | string The id that can be used to lookup this vertex in the graph |
Enumerations
AStarStatus
The status of an A* search.
| Member | Value |
|---|---|
| NO_END_VERTEX | "astar.status.no_end" The end vertex was not found in the graph. |
| NO_PATH | "astar.status.no_path" No path was found. |
| NO_START_VERTEX | "astar.status.no_start" The start vertex was not found in the graph. |
| SUCCESS | "astar.status.success" A path was found. |
| TIMEOUT | "astar.status.timeout" A path wasn't found in the time specified. |
Methods
cloneGraph
Clone a graph, creating new vertices and edges.
Doesnt clone any of the vertices' .data.
const graph = mpSdk.Graph.createDirectedGraph();
// ... setup graph vertices and edges
const clone = sdk.Graph.cloneGraph(graph);
| Parameter | Type |
|---|---|
| graph | Graph.IDirectedGraph<T> the directed graph to clone |
Returns: Graph.IDirectedGraph<T>
createAStarRunner
Bundle
Create a "runner" for the A* algorithm around a graph, and start and end vertices.
The runner encapsulates the details of the graph and search, caches the results of A*,
and provides a way to subscribe to potential changes in the path signifying that the results of Graph.AStarRunner.exec may have changed.
const graph = mpSdk.Graph.createDirectedGraph();
// ... setup graph vertices and edges
const start = graph.vertex('start');
const end = graph.vertex('end');
const aStarRunner = mpSdk.Graph.createAStarRunner(graph, start, end);
const result = aStarRunner.exec();
| Parameter | Type |
|---|---|
| graph | Graph.IDirectedGraph<T> The graph to traverse |
| start | Graph.Vertex<T> The start vertex. |
| end | Graph.Vertex<T> The end vertex. |
| options? | Partial<Graph.SearchOptions<T>> An optional heuristic function. |
Returns: Graph.IAStarRunner<T>
A runner for A* that can execute the search or be subscribed to.
createDirectedGraph
Bundle
Create an empty graph data structure.
const graph = mpSdk.Graph.createDirectedGraph();
| Parameter | Type |
|---|---|
| onDispose? | () => void An optional callback to be called when [`IDirectedGraph.dispose`](#IDirectedGraph.dispose) is called |
Returns: Graph.IDirectedGraph<T>
findCycle
Bundle
Find a cycle in a graph.
const graph = mpSdk.Graph.createDirectedGraph();
// assuming graph has edges A -> B, B -> C, C -> D, D -> B
// should find the cycle [B, C, D]
const cycle = sdk.Graph.findCyle(graph);
| Parameter | Type |
|---|---|
| graph | Graph.IDirectedGraph<T> the directed graph to search for a cycle |
Returns: Iterable<Graph.Vertex<T>>
an Iterable of vertices that represent a found cycle or [] if none were found
findCycles
Bundle
Find multiple cycles in a graph. Note: If a vertex is in multiple cycles, only one will be reported.
const graph = mpSdk.Graph.createDirectedGraph();
// assuming graph has edges A -> B, B -> C, C -> A, D -> E, E -> D
// should find cycles [A, B, C], and [D, E]
const cycle = sdk.Graph.findCyle(graph);
| Parameter | Type |
|---|---|
| graph | Graph.IDirectedGraph<T> the directed graph to search for cycles |
Returns: Iterable<Iterable<Graph.Vertex<T>>>
an iterbale of iterables (like an array of arrays) of vertices