SCGraphTheory.Abstractions 1.0.7

.NET Standard 2.0
NuGet\Install-Package SCGraphTheory.Abstractions -Version 1.0.7
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
dotnet add package SCGraphTheory.Abstractions --version 1.0.7
<PackageReference Include="SCGraphTheory.Abstractions" Version="1.0.7" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add SCGraphTheory.Abstractions --version 1.0.7
#r "nuget: SCGraphTheory.Abstractions, 1.0.7"
#r directive can be used in F# Interactive, C# scripting and .NET Interactive. Copy this into the interactive tool or source code of the script to reference the package.
// Install SCGraphTheory.Abstractions as a Cake Addin
#addin nuget:?package=SCGraphTheory.Abstractions&version=1.0.7

// Install SCGraphTheory.Abstractions as a Cake Tool
#tool nuget:?package=SCGraphTheory.Abstractions&version=1.0.7

Graph Theory Abstractions

Graph theory interfaces - IGraph<TNode,TEdge>, INode<TNode,TEdge> and IEdge<TNode,TEdge> - to allow for graph algorithms that do not depend on a particular graph representation.

Example implementation and usage can be found in the separate SCGraphTheory.AdjacencyList and SCGraphTheory.Search packages, respectively. Additional (test-focused) implementation examples can be found in the TestGraphs library in the SCGraphTheory.Search repo. Notably:

  • A super-simple (though rather inefficient) LINQ-powered immutable implementation. Used for tests in the search algorithm package.
  • A square grid implementation using structs. Involves no up-front heap allocations other than a 2D array of node values, but performs a little worse under search because lots of data gets moved around compared to a class-based implementation (including a little boxing - see notes, below). Included in search benchmarks project because I was interested in the performance impact.
  • A bare-bones adjacency matrix implementation. Doesn't actually feature in any tests - I was just curious to know what an adjacency matrix implementation of these interfaces could look like.

Notes:

  • The fact that the IEdge abstraction has a "From" and a "To" doesn't make this abstraction unsuitable for undirected graphs. Graph algorithms will generally traverse edges in a particular direction, making this a useful interface, and while the AdjacencyList implementation doesn't do this (thus favouring low latency over low memory usage), there's nothing stopping an implementation (with class-valued edges) from making the IEdge implementation a struct created from the "actual" edge, depending on the current node - thus avoiding "duplicated" undirected edges on the heap.

    ..Of course, the Edges property of IGraph returns IEdges, so necessarily should include both directions of an undirected edge - which could cause confusion. However, it should be noted that this is also justified by what it facilitates for algorithms using the abstraction. Consider Bellman-Ford, for example - which (iterates graph edges and) operates specifically on directed graphs. By including both directions of an undirected edge, we allow algorithms such as these to be used against all graphs that implement this abstraction correctly. In this way, treating the two directions of undirected edges separately is a form of normalisation.

  • The declaration of the edges collection of each node as an IReadOnlyCollection<TEdge> necessitates boxing by consumers of these interfaces when this collection is a value type. See an alternative formulation in the benchmarks project of the SCGraphTheory.Search for more on this.

  • Why INode and not IVertex ? Simply because its shorter. Must confess I am slightly regretting this one though..

Product Versions
.NET net5.0 net5.0-windows net6.0 net6.0-android net6.0-ios net6.0-maccatalyst net6.0-macos net6.0-tvos net6.0-windows
.NET Core netcoreapp2.0 netcoreapp2.1 netcoreapp2.2 netcoreapp3.0 netcoreapp3.1
.NET Standard netstandard2.0 netstandard2.1
.NET Framework net461 net462 net463 net47 net471 net472 net48
MonoAndroid monoandroid
MonoMac monomac
MonoTouch monotouch
Tizen tizen40 tizen60
Xamarin.iOS xamarinios
Xamarin.Mac xamarinmac
Xamarin.TVOS xamarintvos
Xamarin.WatchOS xamarinwatchos
Compatible target framework(s)
Additional computed target framework(s)
Learn more about Target Frameworks and .NET Standard.
  • .NETStandard 2.0

    • No dependencies.

NuGet packages (2)

Showing the top 2 NuGet packages that depend on SCGraphTheory.Abstractions:

Package Downloads
SCGraphTheory.AdjacencyList

Adjacency list graph implementation that implements the interfaces defined in SCGraphTheory.Abstractions.

SCGraphTheory.Search

Graph search algorithms that work against any graph type implementing the interfaces defined in SCGraphTheory.Abstractions.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
1.0.7 38 9/16/2022
1.0.6 68 7/30/2022
1.0.5 61 7/30/2022
1.0.4 66 7/30/2022
1.0.3 233 5/25/2021
1.0.2 643 2/29/2020
1.0.1 944 2/29/2020
1.0.0 315 2/29/2020