DirectedGraph <T>

A class representing a directed graph. The graph consists of string nodes, and edges defined by string to/from 2-tuples

Index

Constructors

• constructor

Properties

• adjacencyList
• edges
• size
• vertices

Methods

• buildAdjacencyList
• findCycles
• getStronglyConnectedComponents
• removeVertex
• subgraphFromVertices

Constructors

constructor

• new DirectedGraph<T>(vertices, edges): DirectedGraph<T>

• Parameters

  • vertices: T[]

  • edges: [T, T][]

  Returns DirectedGraph<T>

Properties

adjacencyList

adjacencyList: Record<string, string[]>

edges

edges: [T, T][]

size

size: number

vertices

vertices: T[]

Methods

buildAdjacencyList

• buildAdjacencyList(): Record<string, string[]>

• Constructs and sets the adjacency list for this graph based on its edge definitions

  ---

  Returns Record<string, string[]>

  • The adjacency list for the graph

findCycles

• findCycles(): T[][]

• Finds all simple cycles in this graph using Johnson's algorithm (see https://epubs.siam.org/doi/10.1137/0204007)

  ---

  Returns T[][]

getStronglyConnectedComponents

• getStronglyConnectedComponents(): T[][]

• Calculates the strongly connected components of the graph using Tarjan's strongly connected components algorithm. See https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

  ---

  Returns T[][]

  • An array containing the strongly connected components of this graph, each represented as an array of vertex numbers

removeVertex

• removeVertex(vertex): DirectedGraph<T>

• Creates a new subgraph of this graph by removing a given vertex, along with all edges attached to that vertex

  ---

  Parameters

  • vertex: T

    The vertex to remove

  Returns DirectedGraph<T>

  • The subgraph of this graph obtained by removing the given vertex and all attached edges

subgraphFromVertices

• subgraphFromVertices(vertices): DirectedGraph<T>

• Creates a new subgraph of this graph by keeping only the given vertices and any edges between them

  ---

  Parameters

  • vertices: T[]

    The vertices to keep

  Returns DirectedGraph<T>

  • The subgraph of this graph obtained by only keeping the given vertices and any edges between them