Gapotchenko.FX.Math.Topology
2022.2.7
Prefix Reserved
dotnet add package Gapotchenko.FX.Math.Topology version 2022.2.7
NuGet\InstallPackage Gapotchenko.FX.Math.Topology Version 2022.2.7
<PackageReference Include="Gapotchenko.FX.Math.Topology" Version="2022.2.7" />
paket add Gapotchenko.FX.Math.Topology version 2022.2.7
#r "nuget: Gapotchenko.FX.Math.Topology, 2022.2.7"
// Install Gapotchenko.FX.Math.Topology as a Cake Addin #addin nuget:?package=Gapotchenko.FX.Math.Topology&version=2022.2.7 // Install Gapotchenko.FX.Math.Topology as a Cake Tool #tool nuget:?package=Gapotchenko.FX.Math.Topology&version=2022.2.7
Overview
The module provides data structures and primitives for working with abstract topologies.
In its classical meaning, the science of topology is concerned with the properties of geometric objects. However, such a definition may be considered as too narrow by some. Math has no boundaries, so topology should not be viewed as limited to just one unique flavor of objects (geometric, physical); it can really be anything.
Graph
Basics
Graph<T>
provided by Gapotchenko.FX.Math.Topology
represents a stronglytyped directional graph of objects.
The objects correspond to mathematical abstractions called graph vertices and each of the related pairs of vertices is called an edge.
A graph can be viewed as a structure that contains two sets: set of vertices and set of edges.
Vertices define "what" graph contains and edges define "how" those vertices are connected.
Let's take a look at the simplest graph that contains just two vertices:
using Gapotchenko.FX.Math.Topology;
var g = new Graph<int>
{
Vertices = { 1, 2 }
};
If we could visualize that graph then it would look like this:
Now let's add one more vertex 3
plus an edge that goes from vertex 1
to vertex 2
:
var g = new Graph<int>
{
Vertices = { 1, 2, 3 },
Edges = { (1, 2) } // < an edge has (from, to) notation
};
Our new graph looks like this:
The vertices already defined in edges can be omitted for brevity:
var h = new Graph<int>
{
Vertices = { 3 },
Edges = { (1, 2) }
};
Console.WriteLine(g.GraphEquals(h)); // will print "True"
It is worth mentioning that the graph provides its vertices as an ISet<T>
, so the usual operations on a set apply to the vertices as well:
var g = new Graph<int>
{
Vertices = { 3 },
Edges = { (1, 2) }
};
g.Vertices.UnionWith(new[] { 3, 4, 5 });
The example above produces the following graph:
The same ISet<T>
model applies to the graph edges: they are treated as a set too.
Operations
Now once we have the basics in place, let's take a look at graph operations. Consider the graph:
var g = new Graph<int>
{
Edges =
{
(7, 5), (7, 6),
(6, 3), (6, 4),
(5, 2), (5, 4),
(3, 1),
(2, 1),
(1, 0)
}
};
which looks like this:
Let's transpose the graph (i.e. reverse the direction of its edges):
var h = g.GetTransposition();
Transposed graph h
renders as:
Note that graph h
is a new instance of Graph<T>
.
But what if we want to transpose the graph g
in place?
Every graph operation has a corresponding inplace variant, so for transposition it will be:
g.Transpose();
In this way, a developer can freely choose between immutable, mutable, or combined data models when working on a particular task at hand.
Graph transposition is just one example but there are plenty of other operations available. They all work in the same manner and follow the same model:
Operation  Description  Immutable Function  InPlace Method 

Transposition  Reverses the direction of all edges in the graph.  GetTransposition 
Transpose 
Transitive reduction  Prunes the transitive relations that have shorter paths.  GetTransitiveReduction 
ReduceTransitions 
Reflexive reduction  Removes the loops (also called selfloops or buckles).  GetReflexiveReduction 
ReduceReflexes 
Subgraph  Produces a vertexinduced or edgeinduced subgraph.  GetSubgraph 
Subgraph 
Intersection  Produces a graph containing vertices and edges that are present in both the current and a specified graphs.  Intersect 
IntersectWith 
Union  Produces a graph containing all vertices and edges that are present in the current graph, in the specified graph, or in both.  Union 
UnionWith 
Exception  Produces a graph containing vertices and edges that are present in the current graph but not in the specified graph.  Except 
ExceptWith 
Topological Sorting
Topological sort of a graph is a linear ordering of its vertices such that
for every directed edge u
→ v
,
u
comes before v
in the ordering.
A classic example of topological sorting is to schedule a sequence of jobs (or tasks) according to their dependencies.
The jobs are represented by vertices, and there is an edge from x
to y
if job x
must be completed before job y
can be started.
Performing topological sort on such a graph would give us an order in which to perform the jobs.
Let's take a look at example graph:
Let's assume that vertices represent the jobs, and edges define the dependencies between them.
In this way, job 0
depends on job 1
and thus cannot be started unless job 1
is finished.
In turn, job 1
cannot be started unless jobs 2
and 3
are finished. And so on.
In what order should the jobs be executed?
To answer that question, let's use OrderTopologically
method:
using Gapotchenko.FX.Math.Topology;
// Define a graph according to the diagram.
var g = new Graph<int>
{
Edges =
{
(7, 5), (7, 6),
(6, 3), (6, 4),
(5, 2), (5, 4),
(3, 1),
(2, 1),
(1, 0)
}
};
// Sort the graph topologically.
var ordering = g.OrderTopologically();
// Print the results.
Console.WriteLine(string.Join(", ", ordering));
The resulting sequence of jobs is:
7, 5, 6, 2, 3, 4, 1, 0
OrderTopologically
method can only work on directed acyclic graphs.
If the graph contains a cycle then CircularDependencyException
is raised.
Stable Topological Sort of a Graph
Graph is a data structure similar to a set: it does not guarantee to preserve the order in which the elements were added. As a result, topological sorting may return different orderings for otherwise equal graphs.
To overcome that limitation, it may be beneficial to use the topological sorting with a subsequent ordering by some other criteria.
Such approach makes the topological sorting stable.
It can be achieved by leveraging the standard IOrderedEnumerable<T>
LINQ semantics of the operation, like so:
g.OrderTopologically().ThenBy(…)
Stable Topological Sort of a Sequence
Sorting a sequence of elements in topological order is another play on topological sorting idea.
Say we have a sequence of elements {A, B, C, D, E, F}
. Some elements depend on others:
 A depends on B
 B depends on D
Objective: sort the sequence so that its elements are ordered according to their dependencies. The resulting sequence should have a minimal edit distance to the original one. In other words, sequence should be topologically sorted while preserving the original order of elements whenever it is possible.
Gapotchenko.FX.Math.Topology
provides an extension method for IEnumerable<T>
that allows to achieve that:
using Gapotchenko.FX.Math.Topology;
string seq = "ABCDEF";
// Dependency function.
static bool df(char a, char b) =>
(a + " depends on " + b) switch
{
"A depends on B" or
"B depends on D" => true,
_ => false
};
var ordering = seq.OrderTopologicallyBy(x => x, df);
Console.WriteLine(string.Join(", ", ordering)); // < prints "D, B, A, C, E, F"
Unlike its graph sibling, OrderTopologicallyBy
method tolerates circular dependencies by ignoring them.
They are resolved according to the original order of elements in the sequence.
OrderTopologicallyBy
method allows a subseqent sorting by following the standard IOrderedEnumerable<T>
LINQ convention:
seq.OrderTopologicallyBy(…).ThenBy(…)
Commonly Used Types
 Gapotchenko.FX.Math.Topology.Graph
Other Modules
Let's continue with a look at some other modules provided by Gapotchenko.FX:
 Gapotchenko.FX
 Gapotchenko.FX.AppModel.Information
 Gapotchenko.FX.Collections
 Gapotchenko.FX.Console
 Gapotchenko.FX.Data
 Gapotchenko.FX.Diagnostics
 Gapotchenko.FX.IO
 Gapotchenko.FX.Linq
 Gapotchenko.FX.Math
 Gapotchenko.FX.Memory
 Gapotchenko.FX.Security.Cryptography
 Gapotchenko.FX.Text
 Gapotchenko.FX.Threading
Or look at the full list of modules.
Product  Versions Compatible and additional computed target framework versions. 

.NET  net5.0 is compatible. net5.0windows was computed. net6.0 is compatible. net6.0android was computed. net6.0ios was computed. net6.0maccatalyst was computed. net6.0macos was computed. net6.0tvos was computed. net6.0windows was computed. net7.0 is compatible. net7.0android was computed. net7.0ios was computed. net7.0maccatalyst was computed. net7.0macos was computed. net7.0tvos was computed. net7.0windows was computed. net8.0 was computed. net8.0android was computed. net8.0browser was computed. net8.0ios was computed. net8.0maccatalyst was computed. net8.0macos was computed. net8.0tvos was computed. net8.0windows was computed. 
.NET Core  netcoreapp2.0 is compatible. netcoreapp2.1 is compatible. netcoreapp2.2 was computed. netcoreapp3.0 is compatible. netcoreapp3.1 was computed. 
.NET Standard  netstandard2.0 is compatible. netstandard2.1 is compatible. 
.NET Framework  net46 is compatible. net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 is compatible. net472 is compatible. net48 was computed. net481 was computed. 
MonoAndroid  monoandroid was computed. 
MonoMac  monomac was computed. 
MonoTouch  monotouch was computed. 
Tizen  tizen40 was computed. tizen60 was computed. 
Xamarin.iOS  xamarinios was computed. 
Xamarin.Mac  xamarinmac was computed. 
Xamarin.TVOS  xamarintvos was computed. 
Xamarin.WatchOS  xamarinwatchos was computed. 

.NETCoreApp 2.0
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETCoreApp 2.1
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETCoreApp 3.0
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETFramework 4.6
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETFramework 4.7.1
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETFramework 4.7.2
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETStandard 2.0
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

.NETStandard 2.1
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

net5.0
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

net6.0
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)

net7.0
 Gapotchenko.FX.Collections (>= 2022.2.7)
 Gapotchenko.FX.Linq (>= 2022.2.7)
 Gapotchenko.FX.Math (>= 2022.2.7)
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.