Arborescence.Abstractions 0.16.2

Abstractions — Arborescence Graph Library

This package provides graph-related abstractions. These abstractions fall into two groups: interfaces and concepts.

Interfaces are direct contracts for algorithms, constraints on their type parameters. The most important ones are:

IOutNeighborsAdjacency<TVertex, TNeighbors>
{
    TNeighbors EnumerateOutNeighbors(TVertex vertex);
}

IHeadIncidence<TVertex, TEdge>
{
    bool TryGetHead(TEdge edge, out TVertex head);
}

IOutEdgesIncidence<TVertex, TEdges>
{
    TEdges EnumerateOutEdges(TVertex vertex);
}

Note that IGraph<TVertex, TEdge> is not such a primary abstraction. Utility interfaces are not directly used as type constraints in algorithms. They simply group primary interfaces together, and may be convenient for users to implement.

IGraph<TVertex, TEdge> :
    ITailIncidence<TVertex, TEdge>,
    IHeadIncidence<TVertex, TEdge> { }

IForwardIncidence<TVertex, TEdge, TEdges> :
    IHeadIncidence<TVertex, TEdge>,
    IOutEdgesIncidence<TVertex, TEdges> { }

The library treats the term graph in a specific sense. The closest analog in mathematics is the notion of a quiver^Q — a directed graph[^DG] where loops and multiple edges between two vertices are allowed.

Let's look at an example of four airports (Omsk, London, Istanbul, Taipei) and five flights between them:

        BA676
  ┌───────>───────┐             EVA5288
  │     TK1980    │      TK24     ┌─>─┐
[LHR]─────>─────[IST]─────>─────[TPE] │
  └───────<───────┘               └───┘
        BA677

[OMS]

The same in Graphviz notation:

digraph Flights {
  rankdir=LR
  node [shape=box fontname="Times-Italic"]
  OMS // Omsk
  LHR // London
  IST // Istanbul
  TPE // Taipei
  edge [fontname="Monospace"]
  LHR -> IST [label="BA676"]
  LHR -> IST [label="TK1980"]
  IST -> LHR [label="BA677"]
  IST -> TPE [label="TK24"]
  TPE -> TPE [label="EVA5288"]
}

Here common restrictions of simple directed graphs are relaxed:

• parallel edges like BA676 and TK1980 are permitted,
• antiparallel edges like TK1980 and BA677 are also fine,
• nothing special about loops like edge EVA5288[^EVA],
• isolated vertices like OMS are allowed too.

The edges are not treated as a set of ordered pairs of vertices. Instead, they are described in terms of two incidence functions tail and head mapping the edges to their endpoints. In the example above, the tail function is defined as { BA676 ↦ LHR, TK1980 ↦ LHR, BA677 ↦ IST, TK24 ↦ IST, EVA5288 ↦ TPE }.

There are two distinct notions of multiple edges:

• Without their own identity[^EWO]: the identity of an edge is defined solely by the two vertices it connects. Let's ignore for now the flight ids in the figure above. Then outgoing edges of vertex LHR would be two entries of the same endpoints pair: ⟨LHR, IST⟩ and ⟨LHR, IST⟩ again.
• With their own identity[^EWI]: edges are primitive entities just like vertices. In this case, the outgoing edges of vertex LHR are two different independent edges BA676 and TK1980, which just occasionally happen to have the same endpoints.

Another useful function maps the vertex to its outgoing edges, making a graph traversable. It must be consistent with the incidence function:
∀ v ∀ e   e ∈ out-edges(v) ⇔ v = tail(e)

Together these functions form a scheme:

        ┌   tail : E → V?
Graph   ┤
        └   head : E → V?       ┐
                                ├   Forward Incidence
            out-edges : V → [E] ┘

The adjacency interface provides access to the neighbors of a vertex in a graph. In some contexts there is only concern for the vertices, while the edges are not important.

Basic usage

We start with the simpler abstraction of an adjacency graph, where the edges (flights) are of no interest, only the connected vertices (airports).

using NeighborEnumerator = System.ArraySegment<string>.Enumerator;

public sealed class FlightAdjacencyGraph :
    IOutNeighborsAdjacency<string, NeighborEnumerator>
{
    private readonly Dictionary<string, string[]> _neighborsByAirport;

    private FlightAdjacencyGraph(
        Dictionary<string, string[]> neighborsByAirport) =>
        _neighborsByAirport = neighborsByAirport;

    public NeighborEnumerator EnumerateOutNeighbors(string vertex) =>
        _neighborsByAirport.TryGetValue(vertex, out string[]? neighbors)
            ? new ArraySegment<string>(neighbors).GetEnumerator()
            : ArraySegment<string>.Empty.GetEnumerator();

    public static FlightAdjacencyGraph Create()
    {
        Dictionary<string, string[]> neighborsByAirport = new(3)
        {
            { "LHR", new[] { "IST", "IST" } },
            { "IST", new[] { "LHR", "TPE" } },
            { "TPE", new[] { "TPE" } }
        };
        return new(neighborsByAirport);
    }
}

Where can we fly from Istanbul?

var adjacencyGraph = FlightAdjacencyGraph.Create();
NeighborEnumerator istanbulNeighborEnumerator =
    adjacencyGraph.EnumerateOutNeighbors("IST");
while (istanbulNeighborEnumerator.MoveNext())
    Console.WriteLine(istanbulNeighborEnumerator.Current);

Expected output is:

LHR
TPE

The second example demonstrates an incidence graph. Let's consider only the digits of the flight ids for simplicity, so we could encode them as integers: 676 instead of BA676, 1980 instead of TK1980, and so on.

using EdgeEnumerator = System.ArraySegment<int>.Enumerator;

public sealed class FlightIncidenceGraph :
    IGraph<string, int>, IForwardIncidence<string, int, EdgeEnumerator>
{
    private readonly Dictionary<int, string> _destinationByFlight;
    private readonly Dictionary<string, int[]> _flightsByOrigin;
    private readonly Dictionary<int, string> _originByFlight;

    private FlightIncidenceGraph(
        Dictionary<int, string> originByFlight,
        Dictionary<int, string> destinationByFlight,
        Dictionary<string, int[]> flightsByOrigin)
    {
        _originByFlight = originByFlight;
        _destinationByFlight = destinationByFlight;
        _flightsByOrigin = flightsByOrigin;
    }

    public EdgeEnumerator EnumerateOutEdges(string vertex) =>
        _flightsByOrigin.TryGetValue(vertex, out int[]? flights)
            ? new ArraySegment<int>(flights).GetEnumerator()
            : ArraySegment<int>.Empty.GetEnumerator();

    public bool TryGetTail(int edge, [MaybeNullWhen(false)] out string tail) =>
        _originByFlight.TryGetValue(edge, out tail);

    public bool TryGetHead(int edge, [MaybeNullWhen(false)] out string head) =>
        _destinationByFlight.TryGetValue(edge, out head);

    public static FlightIncidenceGraph Create()
    {
        Dictionary<int, string> originByFlight = new(5)
        {
            { 676, "LHR" }, { 1980, "LHR" }, { 677, "IST" }, { 24, "IST" }, { 5288, "TPE" }
        };
        Dictionary<int, string> destinationByFlight = new(5)
        {
            { 676, "IST" }, { 1980, "IST" }, { 677, "LHR" }, { 24, "TPE" }, { 5288, "TPE" }
        };
        Dictionary<string, int[]> flightsByOrigin = new(3)
        {
            { "LHR", new[] { 676, 1980 } },
            { "IST", new[] { 677, 24 } },
            { "TPE", new[] { 5288 } }
        };
        return new(originByFlight, destinationByFlight, flightsByOrigin);
    }
}

Which flights are available from Istanbul?

var incidenceGraph = FlightIncidenceGraph.Create();
EdgeEnumerator istanbulFlightEnumerator =
    incidenceGraph.EnumerateOutEdges("IST");
while (istanbulFlightEnumerator.MoveNext())
    Console.WriteLine(istanbulFlightEnumerator.Current);

Expected output is:

677
24

Which airports are connected by the flight 676?

if (incidenceGraph.TryGetTail(676, out string? flight676Origin))
    Console.WriteLine(flight676Origin);
if (incidenceGraph.TryGetHead(676, out string? flight676Destination))
    Console.WriteLine(flight676Destination);

Expected output is:

LHR
IST

[^DG]: Directed graph
https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)#Directed_graph

[^EVA]: EVA Air introduces special flight to nowhere
https://edition.cnn.com/travel/article/eva-air-hello-kitty-fathers-day-flight/index.html
https://flightaware.com/live/flight/EVA5288

[^EWI]: Edges with own identity
https://en.wikipedia.org/wiki/Multigraph#Directed_multigraph_(edges_with_own_identity)

[^EWO]: Edges without own identity
https://en.wikipedia.org/wiki/Multigraph#Directed_multigraph_(edges_without_own_identity)

https://en.wikipedia.org/wiki/Quiver_(mathematics)