Options
All
  • Public
  • Public/Protected
  • All
Menu

Class Graph<K, V>

Type parameters

  • K

  • V

Hierarchy

  • Graph

Index

Constructors

constructor

  • new Graph<K, V>(vertices: Map<K, V>, edges: Edge<K>[]): Graph<K, V>
  • Type parameters

    • K

    • V

    Parameters

    • vertices: Map<K, V>
    • edges: Edge<K>[]

    Returns Graph<K, V>

Properties

Private Readonly adjList

adjList: AdjList<K>

Methods

dijkstra

  • dijkstra(source: K): [Map<K, number>, Map<K, null | K>]
  • Run Dijkstra's pathfinding algorithm on the graph

    Parameters

    • source: K

      ID of the vertex to start from

    Returns [Map<K, number>, Map<K, null | K>]

    [totalWeightToVertex, predecessor]

    • totalWeightToVertex stores the sum of the weights along the edges from source to any vertex in the graph. If the weight is Infinity, there does not exist a path from source to that vertex.
    • predecessor represents the vertex before any vertex in the graph along the fastest path from source. It can be used to find the path from source to any vertex by repeatedly finding the vertex before until reaching source. If the predecessor is null, the vertex either is source or has no path from source.

getIdsAndVertices

  • getIdsAndVertices(): [K, V][]
  • Get all vertex IDs and their associated vertices

    Returns [K, V][]

getNeighbors

  • getNeighbors(v: K): K[]
  • Get vertices that have an edge from v

    Parameters

    • v: K

      ID of the vertex to find the neighbors of

    Returns K[]

getVertex

  • getVertex(p: K): Option<V>
  • Parameters

    • p: K

    Returns Option<V>

getWeight

  • getWeight(v: K, u: K): Option<number>
  • Get the weight of an edge between two vertices

    Parameters

    • v: K

      ID of the edge's starting vertex

    • u: K

      ID of the edge's ending vertex

    Returns Option<number>

    Some(weight) if the edge exists, None if not. Keep in mind that directed edges are one-way, so the order of u and v can affect the return value.

pathFromPrev

  • pathFromPrev(src: K, dest: K, prev: Map<K, null | K>): Option<K[]>
  • Generate a path of neighboring vertices to a destination from a prev map

    Parameters

    • src: K

      Original start of the path

    • dest: K

      Destination to find the path to

    • prev: Map<K, null | K>

      Map from vertex to previous vertex

    Returns Option<K[]>

Static Private addDirectedEdge

  • addDirectedEdge<K>(adjList: AdjList<K>, from: K, to: K, weight: number): void
  • Type parameters

    • K

    Parameters

    • adjList: AdjList<K>
    • from: K
    • to: K
    • weight: number

    Returns void

Static Private addEdgeTo

  • addEdgeTo<K>(adjList: AdjList<K>, __namedParameters: Edge<K>): void
  • Modifies an adjacency list to add an edge

    Type parameters

    • K

    Parameters

    • adjList: AdjList<K>

      Adjacency list to add the edge to

    • __namedParameters: Edge<K>

    Returns void

Generated using TypeDoc