Skip to main content

Graph<N>

A Graph is a data structure consisting of nodes that can be connected through edges. Each node has a unique value or identifier. Edges can be directed, in which case we will call it an Arrow Graph, or undirected, in which case we will call it an Edge Graph. Furthermore, edges and arrows can also have values, in which case we call it a Valued Graph.

Exports

The @rimbu/core package exports the following abstract Graph TypeScript types:

NameDescription
Graph<N>An type-invariant immutable graph of node type N
ValuedGraph<N,V>An type-invariant immutable valued graph of node type N and edge type V
VariantGraph<N>An type-variant immutable graph of node type N
VariantValuedGraph<N,V>An type-variant immutable graph of node type N and edge type V

Graph types

Rimbu offers TypeScript implementations for many types of immutable graphs, the main characteristics being valued or non-valued, and directed or undirected:

Edge propertyNon-valuedValued
DirectedArrowGraph<N>ArrowValuedGraph<N, V>
UndirectedEdgeGraph<N>EdgeValuedGraph<N, V>

Arrow Graph

Properties of an Arrow Graph (directed graph) in Rimbu:

  • An Arrow Graph consists of 0 or more nodes, and 0 or more arrows
  • Each node in an Arrow Graph has a unique value
  • Each arrow has a start node, and an end node
  • An arrow can connect a node to itself, but only once
  • Two different arrows cannot have the same start node AND end node

Arrow Graphs are useful when instances of one entity type have a directional relation. In an arrow graph, A -> B does not imply B -> A.

info

Examples of Arrow Graph applications are:

  • A site's web pages and links between them
  • Public transit stops and connections (some may be one-way)

Edge Graph

An Edge graph (undirected graph) has the following properties:

  • An Edge Graph consists of 0 or more nodes, and 0 or more edges
  • Each node in an Edge Graph has a unique value
  • Each edge has 2 nodes indicating a bi-directional connection without direction
  • An edge can connect a node to itself, but only once
  • Two different edges cannot have the same 2 nodes even if the nodes are in reverse order

Edge Graphs are useful when instances of one entity type have a bidirectional relation if they are related. In an edge graph, A -> B also implies that B -> A.

info

Examples of Edge Graph applications are:

  • A group of persons where connections indicate that those persons are friends.
  • Distances between cities

Abstract Graph types

To support a large variety of use cases, there are quite a number of abstract graph types available. These cannot be used to construct Graphs, but the can be convenient when writing generic code operating on Graphs.

Non-valued Graph types

Here is an overview of the available concrete non-valued graph types. The concrete types have constructor methods to create graph instances.

Valued Graph types

Here is an overview of the available concrete valued graph types. The concrete types have constructor methods to create graph instances.