DirectedGraph

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(vertices: string[], edges: [string, string][]): DirectedGraph

• Parameters

  • vertices: string[]

  • edges: [string, string][]

  Returns DirectedGraph

Properties

adjacencyList

adjacencyList: Record<string, string[]>

edges

edges: [string, string][]

size

size: number

vertices

vertices: string[]

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(): string[][]

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

  ---

  Returns string[][]

getStronglyConnectedComponents

• getStronglyConnectedComponents(): string[][]

• 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 string[][]

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

removeVertex

• removeVertex(vertex: string): DirectedGraph

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

  ---

  Parameters

  • vertex: string

    The vertex to remove

  Returns DirectedGraph

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

subgraphFromVertices

• subgraphFromVertices(vertices: string[]): DirectedGraph

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

  ---

  Parameters

  • vertices: string[]

    The vertices to keep

  Returns DirectedGraph

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