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,
- others view the graph as a directed graph and treat edges as bidirectional channels.
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();
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);
var cost = new Dictionary<Node, double>();
int i = 0;
foreach (Node node in g.Nodes()) cost[node] = i++;
Func<Arc, double> arcCost =
(arc => cost[g.U(arc)] + cost[g.V(arc)]);
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);
var sg = new Subgraph(g);
sg.Enable(g.GetNode(0), false);
Console.WriteLine("The subgraph contains "+sg.NodeCount()+" nodes and "+sg.ArcCount()+" arcs.");
Example for Supergraph:
var g = new CompleteGraph(20);
var sg = new Supergraph(g);
var s = sg.AddNode();
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())
{
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:
- 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