Graph <T>
Index
Constructors
constructor
Constructs a new graph data structure.
This constructor initializes an empty graph with no nodes or edges.
Type parameters
- T
Returns Graph<T>
Properties
adjacencyList
id
Accessors
edges
Retrieves the set of edges in the graph.
The returned set is a shallow copy of the internal edge set. Modifications to this set do not affect the graph's internal state.
Returns Set<Edge<T>>
A set containing all edges in the graph.
nodes
Methods
aStar
Finds the shortest path between two nodes in the graph using the A* algorithm.
This method calculates the shortest path from the specified start node to the specified end node in the graph. It returns an object containing the path and the total distance of the path.
Parameters
startNode: PositionNode<T>
The node from which the search for the shortest path begins.
endNode: PositionNode<T>
The node where the search for the shortest path ends.
Returns { distance: number; path: PositionNode<T>[]; pathSteps: number; skippedNodes: Set<G_UUID> }
An object containing:
path: An array of nodes representing the shortest path from startNode to endNode. If no path is found, this will benull.distance: The total distance of the shortest path. If no path is found, this will beInfinity.skippedNodes: A set of all nodes that were skipped during the search (because they were notPositionNodes).
distance: number
path: PositionNode<T>[]
pathSteps: number
skippedNodes: Set<G_UUID>
addEdge
Adds a new edge between two nodes in the graph. If the edge already exists, it does not add a duplicate. The function allows specifying edge options such as weight and directionality. For undirected edges, it creates a duplicate edge in the reverse direction and links both edges as partners.
Parameters
from: Node<T>
The source node of the edge.
to: Node<T>
The target node of the edge.
optionaloptions: EdgeOptions
Optional settings for the edge, including weight and directionality.
Returns Edge<T>[]
An array containing the created edge(s). If the edge is directed, the array contains one edge; if undirected, it contains both the original and the duplicate edge.
addNode
Adds a new node to the graph with the given data.
Parameters
data: T
optionalposition: Vector
Returns Node<T> | PositionNode<T>
The newly created node.
addNodes
areNodesConnected
bfs
Performs a breadth-first search (BFS) on the graph starting from the given node.
This method explores the graph layer by layer, starting from the specified node. It visits all nodes that are directly connected to the start node before moving on to the nodes at the next level of the graph.
Parameters
startNode: Node<T>
The node to start the BFS from.
Returns G_UUID[]
An array of UUIDs representing the nodes that were visited during the search. The order of the nodes in the array corresponds to the order in which they were visited.
deleteEdge
Deletes an edge from the graph.
This method removes the specified edge and its partner edge (if any) from the graph. It updates the internal edge set and edge list accordingly. The source and target nodes of the edge are also updated to reflect the removal of the edge.
Parameters
edge: Edge<T>
The edge to be deleted from the graph.
Returns void
deleteNode
Deletes a node from the graph along with all its associated edges. This method removes the specified node and any edges connected to it from the graph. It updates the internal structures to reflect these changes.
Parameters
node: Node<T>
The node to be deleted from the graph.
Returns Map<G_UUID, Node<T>>
A map of all remaining nodes in the graph.
dfs
Performs a depth-first search (DFS) on the graph starting from the given node.
This method explores the graph by traversing as far as possible along each branch before backtracking. It visits all nodes that are reachable from the start node.
Parameters
startNode: Node<T>
The node to start the DFS from.
optionalvisited: Set<string> = ...
A set of node IDs that have already been visited during the search. This parameter is optional, and defaults to an empty set.
Returns G_UUID[]
An array of UUIDs representing the nodes that were visited during the search. The order of the nodes in the array corresponds to the order in which they were visited.
dijkstra
Finds the shortest path between two nodes in the graph using Dijkstra's algorithm.
This method calculates the shortest path from the specified start node to the specified end node in the graph. It returns an object containing the path and the total distance of the path.
Parameters
sourcenode: Node<T>
Returns { distance: number; node: Node<T>; previous: Node<T> }[]
An object containing:
path: An array of nodes representing the shortest path from startNode to endNode. If no path is found, this will benull.distance: The total distance of the shortest path. If no path is found, this will beInfinity.
getNeighbors
getNode
shortestPathDijkstra
Finds the shortest path between two nodes in the graph using the Dijkstra method
This method calculates the shortest path from the specified start node to the specified end node in the graph. It returns an object containing the path and the total distance of the path.
Parameters
startingNode: Node<T>
The node from which the search for the shortest path begins.
endNode: Node<T>
The node where the search for the shortest path ends.
Returns { distance: number; path: Node<T>[] }
An object containing:
path: An array of nodes representing the shortest path from startNode to endNode. If no path is found, this will benull.distance: The total distance of the shortest path. If no path is found, this will beInfinity.
distance: number
path: Node<T>[]
staticcreateGraphFromNodes
Creates a new graph from an array of nodes, and adds them all to the graph.
Type parameters
- T
Parameters
nodes: T[]
The array of nodes to add to the graph.
Returns Graph<T>
The newly created graph.
A weighted graph data structure.