NuGet\Install-Package SCGraphTheory.Abstractions -Version 1.0.7
dotnet add package SCGraphTheory.Abstractions --version 1.0.7
<PackageReference Include="SCGraphTheory.Abstractions" Version="1.0.7" />
paket add SCGraphTheory.Abstractions --version 1.0.7
#r "nuget: SCGraphTheory.Abstractions, 1.0.7"
// 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
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.
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.
IVertex? Simply because its shorter. Must confess I am slightly regretting this one though..
|.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|
- No dependencies.
NuGet packages (2)
Showing the top 2 NuGet packages that depend on SCGraphTheory.Abstractions:
Adjacency list graph implementation that implements the interfaces defined in SCGraphTheory.Abstractions.
Graph search algorithms that work against any graph type implementing the interfaces defined in SCGraphTheory.Abstractions.
This package is not used by any popular GitHub repositories.