Tutorial

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
• others view the graph as a directed graph and treat edges as bidirectional channels.
  • e.g. TopologicalOrder, Dijkstra, Preflow

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);

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 or Arcs.
• You can get the two nodes of an Arc by calling the U and V 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 Supergraph, you can e.g. extend a read-only graph like CompleteGraph with new nodes and arcs, even though the graph itself cannot be modified directly.

Example for Subgraph:

var g = new CompleteGraph(10); // create a complete graph on 10 nodes
var sg = new Subgraph(g); // 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); // 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);
[...]
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