Unchase.Satsuma.Algorithms
1.0.0
dotnet add package Unchase.Satsuma.Algorithms --version 1.0.0
NuGet\Install-Package Unchase.Satsuma.Algorithms -Version 1.0.0
<PackageReference Include="Unchase.Satsuma.Algorithms" Version="1.0.0" />
paket add Unchase.Satsuma.Algorithms --version 1.0.0
#r "nuget: Unchase.Satsuma.Algorithms, 1.0.0"
// Install Unchase.Satsuma.Algorithms as a Cake Addin #addin nuget:?package=Unchase.Satsuma.Algorithms&version=1.0.0 // Install Unchase.Satsuma.Algorithms as a Cake Tool #tool nuget:?package=Unchase.Satsuma.Algorithms&version=1.0.0
Satsuma is a graph library for .NET, written in C#. The goal was to create an easy-to-use and flexible library, which implements all the necessary graph structures, and the fastest possible versions of common graph algorithms.
Ported and updated by Unchase � 2022
Introduction
- Graphs consist of nodes connected with arcs.
- All graphs are mixed in Satsuma, which means that a graph can contain directed and undirected arcs at once. In short, there is no distinction between directed and undirected graphs. Loops and multiple arcs are also allowed.
- An undirected arc is called an edge.
Graphs can be accessed in a read-only way through the IGraph
interface. The IBuildableGraph
and IDestroyableGraph
interfaces provide write access to a graph.
The structs Node
and Arc
represent the nodes and arcs of a graph. Node.Invalid
and Arc.Invalid
are null-like constants, denoting "no node" and "no arc", respectively.
Warning
Though all graphs use the same type for representing Node and Arc objects, they are generally not interchangeable between graphs. Each graph has its own Node and Arc set. If you pass a Node obtained from a graph to a method of another graph, you will likely get an error. (Adaptors are an exception from this general rule.)
Most of the algorithms can be divided into two categories:
- while there are operations which view the graph as undirected and treat all arcs as edges,
- e.g.
ConnectedComponents
,Bipartition
- e.g.
- others view the graph as a directed graph and treat edges as bidirectional channels.
- e.g.
TopologicalOrder
,Dijkstra
,Preflow
- e.g.
Creating graphs
A graph can have at most int.MaxValue
nodes and int.MaxValue
arcs.
To create your first graph, enter the following code:
CustomGraph g = new CustomGraph();
Node a = g.AddNode();
Node b = g.AddNode();
Node c = g.AddNode();
Arc ab = g.AddArc(a, b, Directedness.Directed);
Arc bc = g.AddArc(b, c, Directedness.Undirected);
or (with extension methods):
CustomGraph g = new CustomGraph()
.WithNodes(1, 2, 3)
.WithArcs(
(1, 2, Directedness.Directed),
(2, 3, Directedness.Undirected)));
The above code creates a graph on three nodes, consisting of a directed arc and an edge. As you can see, the CustomGraph
class can be used to build a graph.
You can also use some "graph constants". These are predefined graphs which usually consume very little memory, due to their special nature. They include CompleteBipartiteGraph
and CompleteGraph
. Using them is more efficient than e.g. building a complete graph using CustomGraph
.
Graphs can also be loaded and saved. See the IO.SimpleGraphFormat
, IO.LemonGraphFormat
and IO.GraphML.GraphMLFormat
classes.
Processing graphs
- To enumerate the elements of a graph, you can call
Nodes
orArcs
. - You can get the two nodes of an
Arc
by calling theU
andV
methods of the containing graph. IsEdge
tells you whether an arc is undirected.- Use the
ArcToString
method to convert an arc to a readable representation.
Example:
var g = new CompleteGraph(100); // create a complete graph on 100 nodes
var cost = new Dictionary<Node, double>(); // create a cost function on the nodes
int i = 0;
foreach (Node node in g.Nodes()) cost[node] = i++; // assign some integral costs to the nodes
Func<Arc, double> arcCost =
(arc => cost[g.U(arc)] + cost[g.V(arc)]); // a cost of an arc will be the sum of the costs of the two nodes
foreach (Arc arc in g.Arcs())
Console.WriteLine("Cost of "+g.ArcToString(arc)+" is "+arcCost(arc));
Using adaptors
By using adaptors, you can perform slight modifications on graphs without actually altering the graph object. Adaptors are analogous to camera filters as they allow you to see an underlying object in a different way.
Two basic adaptor examples are Subgraph
and Supergraph
.
Subgraph
allows you to temporarily disable nodes and arcs in a graph, and work with a smaller portion of it.Supergraph
allows you to temporarily add new nodes and arcs to an existing graph.- With
Supergrap
h, you can e.g. extend a read-only graph likeCompleteGraph
with new nodes and arcs, even though the graph itself cannot be modified directly.
- With
Example for Subgraph
:
var g = new CompleteGraph(10); // create a complete graph on 10 nodes
// var sg = new Subgraph(g);
var sg = g.ToSubgraph(); // create a subgraph of the complete graph
sg.Enable(g.GetNode(0), false); // disable a single node
Console.WriteLine("The subgraph contains "+sg.NodeCount()+" nodes and "+sg.ArcCount()+" arcs.");
Example for Supergraph
:
var g = new CompleteGraph(20); // create a complete graph on 20 nodes
// var sg = new Supergraph(g);
var sg = g.ToSupergraph(); // create a supergraph of the complete graph
var s = sg.AddNode(); // add a node
sg.AddArc(s, g.GetNode(3), Directedness.Directed); // add a directed arc
Console.WriteLine("The extended graph contains "+sg.NodeCount()+" nodes and "+sg.ArcCount()+" arcs.");
Generally speaking, Node
and Arc
objects are interchangeable between the underlying graph and the adaptor, as long as it "makes sense". For clarification, you should always read the description of the adaptor class you want to use. For example:
- nodes of the
Subgraph
are valid as nodes of the underlying graph as well, - and nodes of the underlying graph are valid as nodes of the
Supergraph
as well.
Thus, the code below is correct and will not produce an error:
CustomGraph g;
// Subgraph sg = new Subgraph(g);
Subgraph sg = g.ToSubgraph();
[...]
foreach (var arc in sg.Arcs()) // we are enumerating the arcs of the *subgraph*!
{
// we are now querying arc properties using the *original graph*!
Console.WriteLine("This arc goes from "+g.U(arc)+" to "+g.V(arc)+
", and is "+(g.IsEdge(arc) ? "" : "not ")+"an edge.");
Console.WriteLine("As text: "+g.ArcToString(arc));
}
Other adaptor types:
Path
stores a path of the underlying graph.ContractedGraph
allows merging multiple nodes into one node.RedirectedGraph
allows changing the direction of some arcs.ReverseGraph
allows reversing all arcs of the graph.UndirectedGraph
allows viewing all arcs as edges.
Warning
Modifying the underlying graph while using an adaptor is often illegal, depending on the adaptor type. You should always read the description of the adaptor carefully.
Algorithms
The following algorithms are available:
BiEdgeConnectedComponents
,BiNodeConnectedComponents
,Bipartition
,ConnectedComponents
,StrongComponents
,TopologicalOrder
.FindPathExtensions
: finding a path in a graph.- The abstract class
Dfs
can be extended to create additional depth-first-search-based algorithms. Bfs
,Dijkstra
,BellmanFord
: finding shortest (minimum length) or cheapest (minimum cost) paths.Kruskal<TCost>
,Prim<TCost>
: finding minimum cost spanning forests.MaximumMatching
,MinimumCostMatching
: finding matchings.Preflow
,IntegerPreflow
: finding a maximum flow.NetworkSimplex
: finding a minimum cost feasible circulation.- Multiple heuristics for the traveling salesman problem.
Drawing.ForceDirectedLayout
: computing an aesthetically pleasing visual representation of a graph.
The traveling salesman problem
Suppose that we have a bidirectional complete directed graph (that is, for each pair of nodes a, b there is a directed arc from a to b) and a cost function on the arcs.
We would like to find a minimum cost Hamiltonian cycle in the graph. This is called the traveling salesman problem.
The TSP-related classes in Satsuma are: CheapestLinkTsp<TNode>
, InsertionTsp<TNode>
, Opt2Tsp<TNode>
, HamiltonianCycle
. They do not generally use the basic Satsuma types Node
, Arc
and IGraph
, as the input graph in a TSP is always a bidirectional complete directed graph. Instead, there is a generic type parameter which is the type of the nodes to visit. TSP-solving classes like InsertionTsp<TNode>
accept a collection of nodes and a cost function defined on node pairs, and produce a cost-effective visiting order of the supplied nodes.
TSP cost functions must always be finite. The algorithms generally perform well if the cost function is symmetric (that is, the cost of traveling from a to b is the same as traveling from b to a). In particular, they perform the best for metric cost functions (that is, the triangle inequality must hold as well).
Warning
As the traveling salesman problem is NP-hard, there is no known optimal polynomial solution, and it is unlikely that one exists. Therefore, all classes employ some kind of heuristic and the returned tours will be probably suboptimal.
The following example demonstrates how a reasonably cheap tour on Euclidean points can be found using a Satsuma TSP solver:
// create a node collection: in this example, they are geographical locations
var points = new PointD[]
{
new PointD(47.50704, 19.04592),
new PointD(47.50284, 19.03171),
new PointD(47.472331, 19.062706),
new PointD(47.515373, 19.082839)
};
// define a cost function: in this example, it is the Euclidean distance
Func<PointD, PointD, double> cost = (p, q) => p.Distance(q);
// create a TSP solver instance and calculate a tour
InsertionTsp<PointD> tsp = new InsertionTsp<PointD>(points, cost);
tsp.Run();
Console.WriteLine("Total tour cost: "+tsp.TourCost);
Console.WriteLine("Visiting order:");
foreach (PointD p in tsp.Tour()) Console.WriteLine(p);
Thread safety
A type is called thread safe if its instances can be simultaneously operated on by multiple threads without compromising integrity.
For example, a class is thread safe if its methods and properties behave correctly even if multiple threads call/access them at once.
The following rules apply for types defined in Satsuma, concerning thread safety:
- If not stated otherwise, all classes and interfaces should be treated as thread unsafe.
- Do not assume that they are safe by just looking at their source code. If their description does not say anything about thread safety, then their implementation may introduce thread unsafe solutions anytime in the future, which may break your code.
- Nevertheless, all structs in Satsuma are thread safe.
- All structs defined in the Satsuma library are immutable.
The thread safety of an interface is in fact a restriction on implementor classes. In a sense, thread safety is part of the interface definition. For example, if ISomething is thread safe, then this means that all implementors should be written in a way that ISomething instances can be used by multiple threads at once.
Warning
If an interface or base class is thread safe, this does not imply that all implementor or descendant classes are thread safe. However, if an instance of the derived type is treated as an instance of the base type, then it should be thread safe. This statement may sound confusing, so let us take a fictional example.
- Supposed that
IReadOnlySomething
is a thread safe interface.- WritableSomething, which implements
IReadOnlySomething
, may not be thread safe, as the data structure may be compromised if it is modified concurrently.- However, if only the
IReadOnlySomething
methods are called, then aWritableSomething
instance should be freely usable by any number of threads.
Product | Versions Compatible and additional computed target framework versions. |
---|---|
.NET | net6.0 is compatible. 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. |
-
net6.0
- Unchase.Satsuma.Adapters (>= 1.0.0)
NuGet packages (2)
Showing the top 2 NuGet packages that depend on Unchase.Satsuma.Algorithms:
Package | Downloads |
---|---|
Kemsekov.GraphSharp
Package Description |
|
Unchase.Satsuma.TSP
Satsuma is a graph library for .NET, written in C# (TSP). |
GitHub repositories
This package is not used by any popular GitHub repositories.
Version | Downloads | Last updated |
---|---|---|
1.0.0 | 1,905 | 10/18/2022 |