SCGraphTheory.AdjacencyList
1.0.6
See the version list below for details.
dotnet add package SCGraphTheory.AdjacencyList --version 1.0.6
NuGet\Install-Package SCGraphTheory.AdjacencyList -Version 1.0.6
<PackageReference Include="SCGraphTheory.AdjacencyList" Version="1.0.6" />
paket add SCGraphTheory.AdjacencyList --version 1.0.6
#r "nuget: SCGraphTheory.AdjacencyList, 1.0.6"
// Install SCGraphTheory.AdjacencyList as a Cake Addin #addin nuget:?package=SCGraphTheory.AdjacencyList&version=1.0.6 // Install SCGraphTheory.AdjacencyList as a Cake Tool #tool nuget:?package=SCGraphTheory.AdjacencyList&version=1.0.6
SCGraphTheory.AdjacencyList
Adjacency list graph implementation that implements the interfaces defined in the SCGraphTheory.Abstractions package, and can thus work with other packages that also use this abstraction - such as SCGraphTheory.Search.
Usage Examples
Directed graphs are the simplest to use. Here's an example with some data properties:
using SCGraphTheory.AdjacencyList;
namespace MyDirectedGraph
{
public class Node : NodeBase<Node, Edge>
{
public Node(string myNodeProp) => MyNodeProp = myNodeProp;
public string MyNodeProp { get; }
}
public class Edge : EdgeBase<Node, Edge>
{
public Edge(Node from, Node to, string myEdgeProp)
: base(from, to) => MyEdgeProp = myEdgeProp;
public string MyEdgeProp { get; }
}
public static class Program
{
...
private static Graph<Node, Edge> MakeGraph()
{
var graph = new Graph<Node, Edge>();
Node node1, node2;
graph.Add(node1 = new Node("node 1"));
graph.Add(node2 = new Node("node 2"));
graph.Add(new Edge(node1, node2, "edge 1-2"));
...
}
}
}
Undirected graphs take a little more effort, though there's a handy UndirectedEdgeBase
class to do a bit of the work for you. UndirectedEdgeBase
still conforms to the IEdge<TNode, TEdge>
interface, so each undirected edge actually consists of a pair of edge objects*. Here's an example with a direction-ignorant settable edge data property:
* Note that if we really wanted a single object on the heap for an undirected edge, we could probably do something with by making the actual IEdges value types that refer to the single "edge". The extra complexity and resulting caveats (edge structs as IEdge will be boxed, need to be careful with mutability, etc) mean that it's not something I've bothered exploring thus far..
using SCGraphTheory.AdjacencyList;
namespace MyUndirectedGraph
{
public class Node : NodeBase<Node, Edge>
{
}
public class Edge : UndirectedEdgeBase<Node, Edge>
{
private string myEdgeProp;
public Edge(Node from, Node to, string myEdgeProp)
: base(from, to, (f, t, r) => new Edge(f, t, r, myEdgeProp))
{
this.myEdgeProp = myEdgeProp;
}
private Edge(Node from, Node to, Edge reverse, string myEdgeProp)
: base(from, to, reverse)
{
this.myEdgeProp = myEdgeProp;
}
public string MyEdgeProp
{
get => myEdgeProp;
set
{
myEdgeProp = value;
Reverse.myEdgeProp = value;
}
}
}
public static class Program
{
...
public static Graph<Node, Edge> MakeGraph()
{
var graph = new Graph<Node, Edge>();
Node node1, node2;
graph.Add(node1 = new Node());
graph.Add(node2 = new Node());
graph.Add(new Edge(node1, node2, "A"));
...
}
}
}
Finally, here's an example with "undirected" edges with a direction-specific settable data property (reverse edge negates the value of the property). Obviously its significant that int
is a value type - solution would be a little more complex with a mutable reference type..
using SCGraphTheory.AdjacencyList;
namespace MyUndirectedGraph2
{
public class Node : NodeBase<Node, Edge>
{
}
public class Edge : UndirectedEdgeBase<Node, Edge>
{
private int myEdgeProp;
public Edge(Node from, Node to, int myEdgeProp)
: base(from, to, (f, t, r) => new Edge(f, t, r, -myEdgeProp))
{
this.myEdgeProp = myEdgeProp;
}
private Edge(Node from, Node to, Edge reverse, int myEdgeProp)
: base(from, to, reverse)
{
this.myEdgeProp = myEdgeProp;
}
public int MyEdgeProp
{
get => myEdgeProp;
set
{
myEdgeProp = value;
Reverse.myEdgeProp = -value;
}
}
}
public static class Program
{
...
public static Graph<Node, Edge> MakeGraph()
{
var graph = new Graph<Node, Edge>();
Node node1, node2;
graph.Add(node1 = new Node());
graph.Add(node2 = new Node());
graph.Add(new Edge(node1, node2, 1));
...
}
}
}
Notes
- "But this isn't an adjacency list representation..": Yes, it is. Your algorithm textbook won't lumber itself with the conventions of object orientation, but .NET gives us them, and we should use the tools that we are given. If it helps, think of the node objects as the keys of a direct address table that points at each list.
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net5.0 was computed. net5.0-windows was computed. net6.0 was computed. net6.0-android was computed. net6.0-ios was computed. net6.0-maccatalyst was computed. net6.0-macos was computed. net6.0-tvos was computed. net6.0-windows was computed. net7.0 was computed. net7.0-android was computed. net7.0-ios was computed. net7.0-maccatalyst was computed. net7.0-macos was computed. net7.0-tvos was computed. net7.0-windows was computed. net8.0 was computed. net8.0-android was computed. net8.0-browser was computed. net8.0-ios was computed. net8.0-maccatalyst was computed. net8.0-macos was computed. net8.0-tvos was computed. net8.0-windows was computed. |
.NET Core | netcoreapp2.0 was computed. netcoreapp2.1 was computed. netcoreapp2.2 was computed. netcoreapp3.0 was computed. netcoreapp3.1 was computed. |
.NET Standard | netstandard2.0 is compatible. netstandard2.1 was computed. |
.NET Framework | net461 was computed. net462 was computed. net463 was computed. net47 was computed. net471 was computed. net472 was computed. 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. |
-
.NETStandard 2.0
- SCGraphTheory.Abstractions (>= 1.0.3)
NuGet packages
This package is not used by any NuGet packages.
GitHub repositories
This package is not used by any popular GitHub repositories.