Graph <T>

A weighted graph data structure.

Index

Constructors

• constructor

Properties

• adjacencyList
• id

Accessors

• edges
• nodes
• vertices

Methods

• aStar
• addEdge
• addNode
• addNodes
• addVertex
• addVertices
• areNodesConnected
• areVerticesConnected
• bfs
• deleteEdge
• deleteNode
• deleteVertex
• dfs
• dijkstra
• getNeighbors
• getNode
• getVertex
• shortestPathDijkstra
• createGraphFromNodes
• createGraphFromVertices

Constructors

constructor

• new Graph<T>(): Graph<T>

• 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

adjacencyList: Map<G_UUID, Set<G_UUID>>

id

id: G_UUID = ...

Accessors

edges

• get edges(): Set<Edge<T>>

• 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

• get nodes(): Map<G_UUID, Node<T>>

• The set of nodes in the graph, keyed by their UUID.

  The map returned by this property is a shallow copy of the internal map. The nodes in this map are not frozen, and may be modified by the caller.

  ---

  Returns Map<G_UUID, Node<T>>

  A shallow copy of the graph's internal node map.

vertices

• get vertices(): Map<G_UUID, Node<T>>

• The set of vertices in the graph, keyed by their UUID.

  This property is an alias for the "nodes" property, and is provided for convenience when working with graph algorithms that expect a "vertices" property.

  The map returned by this property is a shallow copy of the internal map. The nodes in this map are not frozen, and may be modified by the caller.

  ---

  Returns Map<G_UUID, Node<T>>

  A shallow copy of the graph's internal node map.

Methods

aStar

• aStar(startNode: PositionNode<T>, endNode: PositionNode<T>): { distance: number; path: PositionNode<T>[]; pathSteps: number; skippedNodes: Set<G_UUID> }

• 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 be null.
  • distance: The total distance of the shortest path. If no path is found, this will be Infinity.
  • skippedNodes: A set of all nodes that were skipped during the search (because they were not PositionNodes).

  • distance: number

  • path: PositionNode<T>[]

  • pathSteps: number

  • skippedNodes: Set<G_UUID>

addEdge

• addEdge(from: Node<T>, to: Node<T>, options?: EdgeOptions): Edge<T>[]

• 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

• addNode(data: T, position?: Vector): Node<T> | Vertex<T> | PositionNode<T>

• Adds a new node to the graph with the given data.

  ---

  Parameters

  • data: T

  • optionalposition: Vector

  Returns Node<T> | Vertex<T> | PositionNode<T>

  The newly created node.

addNodes

• addNodes(nodes: T[]): Map<G_UUID, Node<T>>

• Adds multiple new nodes to the graph with the given data.

  ---

  Parameters

  • nodes: T[]

  Returns Map<G_UUID, Node<T>>

  A map of all nodes in the graph, including the newly created ones.

addVertex

• addVertex(data: T): Vertex<T>

• Adds a new vertex to the graph with the given data and returns the newly created node. This method is just an alias for addNode.

  ---

  Parameters

  • data: T

    The data to be stored in the new node.

  Returns Vertex<T>

  The newly created node.

addVertices

• addVertices(nodes: T[]): Map<G_UUID, Node<T>>

• Adds multiple vertices to the graph with the given data.

  This method takes an array of data items, creates new nodes for each item, and adds them to the graph. It utilizes the addNodes method to perform the addition and updates the adjacency list accordingly.

  ---

  Parameters

  • nodes: T[]

    An array of data items to be added as vertices to the graph.

  Returns Map<G_UUID, Node<T>>

  A map of all nodes in the graph, including the newly added vertices.

areNodesConnected

• areNodesConnected(node1: Node<T>, node2: Node<T>): boolean

• Checks if two nodes are connected by an edge.

  ---

  Parameters

  • node1: Node<T>

    The first node to check.

  • node2: Node<T>

    The second node to check.

  Returns boolean

  true if the nodes are connected, false if not.

areVerticesConnected

• areVerticesConnected(node1: Node<T>, node2: Node<T>): boolean

• Determines whether two vertices are directly connected by an edge.

  This method checks if there is a direct connection (edge) between the two specified nodes in the graph by inspecting the adjacency list.

  ---

  Parameters

  • node1: Node<T>

    The first node to check for a connection.

  • node2: Node<T>

    The second node to check for a connection.

  Returns boolean

  true if there is a direct edge connecting node1 and node2, false otherwise.

bfs

• bfs(startNode: Node<T>): G_UUID[]

• 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

• deleteEdge(edge: Edge<T>): void

• 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

• deleteNode(node: Node<T>): Map<G_UUID, Node<T>>

• 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.

deleteVertex

• deleteVertex(node: Node<T>): Map<G_UUID, Node<T>>

• Deletes a vertex from the graph.

  This method removes the specified vertex and all associated edges from the graph by delegating to the deleteNode method. It updates the internal structures to reflect these changes.

  ---

  Parameters

  • node: Node<T>

    The vertex to be deleted from the graph.

  Returns Map<G_UUID, Node<T>>

  A map of all remaining vertices in the graph.

dfs

• dfs(startNode: Node<T>, visited?: Set<string>): G_UUID[]

• 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

• dijkstra(sourcenode: Node<T>): { distance: number; node: Node<T>; previous: Node<T> }[]

• 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 be null.
  • distance: The total distance of the shortest path. If no path is found, this will be Infinity.

getNeighbors

• getNeighbors(node: Node<T>): Node<T>[]

• Gets the neighbors of the given node.

  The returned array contains all of the nodes that are directly connected to the given node.

  ---

  Parameters

  • node: Node<T>

    The node whose neighbors should be retrieved.

  Returns Node<T>[]

  An array of nodes that are directly connected to the given node.

getNode

• getNode(id: G_UUID): Node<T>

• Gets a node by its UUID.

  ---

  Parameters

  • id: G_UUID

    The UUID of the node to be retrieved.

  Returns Node<T>

  The node with the specified UUID, or undefined if no such node exists.

getVertex

• getVertex(id: G_UUID): Node<T>

• Gets a node by its UUID.

  ---

  Parameters

  • id: G_UUID

    The UUID of the node to be retrieved.

  Returns Node<T>

  The node with the specified UUID, or undefined if no such node exists.

shortestPathDijkstra

• shortestPathDijkstra(startingNode: Node<T>, endNode: Node<T>): { distance: number; path: Node<T>[] }

• 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 be null.
  • distance: The total distance of the shortest path. If no path is found, this will be Infinity.

  • distance: number

  • path: Node<T>[]

staticcreateGraphFromNodes

• createGraphFromNodes<T>(nodes: T[]): Graph<T>

• 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.

staticcreateGraphFromVertices

• createGraphFromVertices<T>(vertices: T[]): Graph<T>

• Creates a new graph from an array of vertices, and adds them all to the graph.

  ---

  Type parameters

  • T

  Parameters

  • vertices: T[]

    The array of vertices to add to the graph.

  Returns Graph<T>

  The newly created graph.