Options
All
  • Public
  • Public/Protected
  • All
Menu

Class ListGraph<T>

A Graph implementation based on an Adjacency list. In its current implementation, it is weighted (with a default value of 1, allowing to not care about it if it is not needed), and can be optionnaly directed if specified in the constructor options.

Type parameters

  • T

Hierarchy

  • ListGraph

Implements

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Properties

Private data

data: Map<string, Vertex<T>> = new Map<string, Vertex<T>>()

The data source containing all vertices and edges, using a Map as adjacency list.

Private defaultWeight

defaultWeight: number = 1

The default weight value to add to the edges.

defaultvalue

1

Private isDirected

isDirected: boolean = false

Whether edges should be added in both direction.

defaultvalue

false

Accessors

order

  • get order(): number

  • The number of vertices.

    Returns number

size

  • get size(): number

  • The number of edges.

    Returns number

Methods

addEdge

  • addEdge(from: string, to: string, weight?: number): boolean

  • Adds an edge between two vertices with an optional weight. The order of from and to parameters only matters if the graph is directed. It fails if a vertex is not found or when trying to add an already existing edge.

    Parameters

    • from: string

      The origin vertex of the edge.

    • to: string

      The destination vertex of the edge.

    • Default value weight: number = this.defaultWeight

      The edge weight.

    Returns boolean

    true or false if insertion failed.

addVertex

  • addVertex(id: string, value: T): boolean

  • Adds a new vertex, referenced with a unique id, of given value. If the given id is already used, the insertion is aborted.

    Parameters

    • id: string

      The vertex ID. Must be unique

    • value: T

      The vertex value.

    Returns boolean

    true or false if it failed to insert.

addVertices

  • addVertices(...vertices: [string, T][]): number

  • Adds new vertices from given tuples [id, value]

    Parameters

    • Rest ...vertices: [string, T][]

      The tuples separated by a comma

    Returns number

    The number of added vertices.

Private checkEdgeOps

  • checkEdgeOps(from: string, to: string): { dstVertex: undefined | Vertex<T>; isSafeAdd: boolean; isSafeRem: boolean; srcVertex: undefined | Vertex<T> }

  • Internal helper providing recurrent checks on a specific edge before performing an operation.

    Parameters

    • from: string

      The origin vertex of the edge.

    • to: string

      The destination vertex of the edge.

    Returns { dstVertex: undefined | Vertex<T>; isSafeAdd: boolean; isSafeRem: boolean; srcVertex: undefined | Vertex<T> }

    {

    srcVertex: (Vertex) Vertex match for from

    dstVertex: (Vertex) Vertex match for to

    isSafeAdd: (boolean)

    isSafeRem: (boolean)

    }

    • dstVertex: undefined | Vertex<T>
    • isSafeAdd: boolean
    • isSafeRem: boolean
    • srcVertex: undefined | Vertex<T>

edges

  • Returns an array of all edges.

    Returns Edge[]

    An array of Edge.

get

  • get(id: string): Vertex<T> | undefined

  • Retrieves the vertex corresponding to given id.

    Parameters

    • id: string

      The vertex id.

    Returns Vertex<T> | undefined

    • The matching Vertex or undefined if not found.

getEdge

  • getEdge(from: string, to: string): Edge | undefined

  • Retrieves an edge connecting two vertices. The parameters order only matter in the case of a directed graph.

    Parameters

    • from: string

      The origin vertex id.

    • to: string

      The destination vertex id.

    Returns Edge | undefined

    • The matching Edge or undefined if not found.

getEdgeWeight

  • getEdgeWeight(from: string, to: string): number | undefined

  • Retrieves the edge between two vertices and returns its weight. The order of from and to parameters only matters if the graph is directed. It fails if no edge is found (missing vertex or vertices not connected).

    Parameters

    • from: string

      The origin vertex of the edge.

    • to: string

      The destination vertex of the edge.

    Returns number | undefined

    The weight value of the edge or undefined if it failed to retrieve the edge.

reduce

  • Reduces all vertices to a single value using the ginven reduce function.

    Type parameters

    • R

    Parameters

    • reduce: ReduceFunction<Vertex<T>, R>

      The ReduceFunction to apply on each vertex.

    • initialValue: R

      The starting value.

    Returns R

    The value resulting of the result function.

removeEdge

  • removeEdge(from: string, to: string): boolean

  • Removes the edge between two vertices. The order of from and to parameters only matters if the graph is directed. It fails if a vertex is not found or when trying to remove an inexistent edge.

    Parameters

    • from: string

      The origin vertex of the edge.

    • to: string

      The destination vertex of the edge.

    Returns boolean

    true or false if it failed to remove an edge.

removeVertex

  • removeVertex(id: string): boolean

  • Removes vertex qith given id and its related edges.

    Parameters

    • id: string

      id of the vertex to be removed.

    Returns boolean

    true or false if the vertex is not found.

resetVertex

  • resetVertex(id: string): boolean

  • Removes all related edges to a vertex. Its value persists.

    Parameters

    • id: string

      id if the vertex to be removed.

    Returns boolean

    true or false if the vertex is not found.

setDefaultWeight

  • setDefaultWeight(weight: number): void

  • Sets the default weight on edge insertion to the given value.

    Parameters

    • weight: number

      The replacing weight value .

    Returns void

setEdgeWeight

  • setEdgeWeight(from: string, to: string, weight: number): boolean

  • Retrieves the edge between two vertices and sets its weight. The order of from and to parameters only matters if the graph is directed. It fails if no edge is found (missing vertex or vertices not connected).

    Parameters

    • from: string

      The origin vertex of the edge.

    • to: string

      The destination vertex of the edge.

    • weight: number

    Returns boolean

    true or false if it failed to retrieve the edge.

shortestPath

  • Returns an array of Vertex<T> representing the steps of the shortest path from position from to position to. It uses Dijktsra's algorithm.

    Parameters

    • from: string

      The starting vertex id.

    • to: string

      The destination vertex id.

    • Optional filter: FilterFunction<Vertex<T>>

      An optional filter function applied on vertices to restrict or not their usage.

    Returns Vertex<T>[]

    An array of Vertex<T>

traverseBFS

  • Parameters

    Returns void

traverseDFSRecursive

  • Parameters

    Returns void

vertices

  • Returns an array of all vertices.

    Returns Vertex<T>[]

    An array of Vertex.

walk

  • walk(callback: (vertex: Vertex<T>, id: string) => void): void

  • Executes a callback on each vertex.

    Parameters

    • callback: (vertex: Vertex<T>, id: string) => void

      The callback to execute on each vertex.

        • (vertex: Vertex<T>, id: string): void

        • Parameters

          • vertex: Vertex<T>
          • id: string

          Returns void

    Returns void

Generated using TypeDoc