Creates a new Graph instance with the same shape but with a reduced
number of nodes and edges. Each instance of multiple nodes and edges in a
chain with no forks is converted into a single edge, where the removed
nodes are converted into inner locations of the new edge. In particular,
the new graph will have no nodes of degree 2 except for nodes with only
one edge connecting to themselves. This may significantly increase the
speed of certain calculations, such as getShortestPath.
A newly created edge will have the lowest ID of the edges which were combined to form it, where numbers are considered lower than strings.
A new coalesced Graph instance.
All the edges present in this graph, in the order that they were originally provided to Graph.create.
All the nodes present in this graph, in the order that they were originally provided to Graph.create.
Returns the closest point on the graph to a given location. This requires the graph to have a spatial index. To enable this, first use withClosestPointMesh to obtain a new graph instance with an index enabled. Calling this method on a graph with no index will throw.
A location.
The point on the graph closest to the given location, up to a precision determined by the graph's mesh.
A list of new Graph instances, each representing a single
connected component of this instance.
An edge ID.
The Edge associated with the given ID, or undefined if none
exists. Note that the type signature is a lie (it claims to be
non-nullable). This is for convenience. Lookup will usually be of known
edge IDs, and this is consistent with the typings for index lookup in
objects.
Returns the Cartesian coordinates of the point a certain distance along an edge. Does not throw on out-of-bounds distances. Instead negative distances return the start of the edge and distances greater than the length return the end of the edge. This is to avoid unexpected behavior due to floating-point imprecision issues.
A point specified as a certain distance along an edge.
The Cartesian coordinates of the given point.
A node ID.
The Node associated with the given ID, or undefined if none
exists. Note that the type signature is a lie (it claims to be
non-nullable). This is for convenience. Lookup will usually be of known
node IDs, and this is consistent with the typings for index lookup in
objects.
Given an edge and one of its endpoints, return the other endpoint. Throws if either of the IDs is nonexistent, or if the node is not an endpoint of the edge.
The node which is the other endpoint of the edge with the given ID.
Does preprocessing to enable getClosestPoint by creating a spatial index of points along the graph.
How fine the mesh should be. Lower precision is more
accurate but takes more time to precompute and more memory. As a
rule-of-thumb, getClosestPoint will be accurate to within precision
distance.
A new Graph instance with a spatial index enabled.
Helper function for computing progress down a path after advancing along it for a given distance. If the distance is greater than the total length of the path, then advances to the end of the path. Throws on negative distances.
A list of locations representing a path.
A distance down the path.
A new list of locations representing the remaining part of
locations after advancing distance along the path.
Returns a new path obtained by truncating the given path by the provided distance. That is, the start point of the path moves forward, and any nodes and edges that it passes are dropped. Throws an error if distance is negative.
A path.
A distance to travel along the path.
The remaining portion of path after traveling distance along
it.
A list of nodes.
A list of edges.
A new Graph instance with the specified nodes and edges.
Generated using TypeDoc
A graph composed of Nodes and Edges, representing 2-D spatial points and links between them. Provides methods for reading and analyzing its data.
The graph and all its data are immutable. No method will modify the
Graphinstance on which it is called, although some will return new instances.New
Graphinstances are created using Graph.create, which takes SimpleNodes and SimpleEdges as arguments. Upon construction, the graph creates corresponding Node and Edge instances which contain additional information. AllGraphmethods will return theseNodes rather than the originalSimpleNodes, and likewise for edges.Example usage:
import Graph from "graphs-and-paths"; const nodes = [ { id: "A", location: { x: 0, y: 0 } }, { id: "B", location: { x: 3, y: 0 } }, { id: "C", location: { x: 0, y: 4 } } ]; const edges = [ { id: "AB", startNodeId: "A", endNodeId: "B" }, { id: "BC", startNodeId: "B", endNodeId: "C" }, { id: "CA", startNodeId: "C", endNodeId: "A" } ]; const graph = Graph.create(nodes, edges); graph.getNode("A"); // { id: "A", location: { x: 0, y: 0 }, edgeIds: ["AB", "CA"] } graph.getLocation("AB", 2); // { x: 2, y: 0 } graph.getShortestPath( { edgeId: "CA", distance: 3 }, { edgeId: "BC", distance: 1 } ).locations; // [ // { x: 0, y: 1 }, // { x: 0, y: 0 }, // { x: 3, y: 0 }, // { x: 2.4, y: 0.8 } // ]