Skip to content
/ Rivers Public
forked from Washi1337/Rivers

A fast graphing library that allows for constructing, importing, exporting, and analysing graph structures in .NET.

License

Notifications You must be signed in to change notification settings

lulzzz/Rivers

 
 

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

21 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Rivers

Build status

Rivers is a light-weight graphing library written in C#. It contains a model for directed and undirected graphs, as well as a whole bunch of standard algorithms to analyse graphs.

Rivers is released under the MIT license.

Binaries

Features

  • Easy to use graph class modelled using adjacency lists for each node. This has the following advantages:
    • Optimised for quick insertion of nodes and edges.
    • Minimal memory footprint.
    • Efficient for sparse graphs.
  • Support for directed as well as undirected graphs. The default is directed.
  • Various graph generators to help building up common graph structures.
  • Various built-in node traversal and search algorithms (including breadth first, depth first and more).
  • Built-in dominator analysis. Useful for control flow graph analysis.
    • Construct dominator trees from CFGs.
    • Get dominance frontier.
  • Dot file import/export support.

Quick starters guide

Creating a graph

The Graph class contains two collections representing the nodes and edges of the graph. They work like any other collection in .NET, and you can add and remove items, and iterate through them.

var graph = new Graph();

// Add nodes
graph.Nodes.Add(new Node("1"));
graph.Nodes.Add("2");
graph.Nodes.Add("3");

// Add edges.
graph.Edges.Add(new Edge("1", "2"));
graph.Edges.Add("2", "3");

By default, graphs are directed. If you want an undirected graph, use the second constructor:

var graph = new Graph(false);

Inspecting and editing nodes

The Node class has various properties that give more insight about a node in the graph. Get a node by its name through the indexer of the Graph.Nodes property.

  • Inspect, add or remove incoming and outgoing edges on the fly using the IncomingEdges and OutcomingEdges collections.
  • Store custom defined properties in the UserData property.
// Obtain the node.
var node = graph.Nodes["1"];

// Add an edge from 1 to 2, 3 and 4.
node.OutgoingEdges.Add(new Edge(node, graph.Nodes["2"]));
node.OutgoingEdges.Add(graph.Nodes["3"]);
node.OutgoingEdges.Add("4");

// Set user data.
node.UserData["MyProperty"] = 1234;

Perform graph searches and traversals

There are various extension methods defined to perform searches in the graph. Example:

using Rivers.Analysis;

var result = myNode.DepthFirstSearch(n => n.Name.Contains("A"));
if (result == null) 
{
    // There is no path from myNode to a node with the letter "A".
}

If you are more interested in the actual traversal of the nodes, you can use the corresponding Traversal extension instead. This will result in an IEnumerable<Node> that is lazily initialized with all the nodes that it is traversing.

foreach (var node in myNode.DepthFirstTraversal()) 
{
    // ...
}

var nodes = from n in myNode.DepthFirstTraversal()
            // ...
            select n;

Generating graphs

The Rivers.Generators namespace contains various graph generators for building common graph structures easily.

using Rivers.Generators;

var generator = new PathGenerator(true, 5);
var pathGraph = generator.GenerateGraph();
// pathGraph now contains the graph:
// 1 -> 2 -> 3 -> 4 -> 5

Dominator analysis

Dominator information can be obtained by creating a new instance of the DominatorInfo class.

using Rivers.Analysis;

var cfg = new Graph();
var rootNode = cfg.Nodes.Add("root");
var someOtherNode = cfg.Nodes.Add("other");
// ...

var info = new DominatorInfo(rootNode);

var idom = info.GetImmediateDominator(someOtherNode);
var frontier = info.GetDominanceFrontier(someOtherNode);

Dot file support

Importing and exporting to dot files can be done using the DotReader and DotWriter classes. You can then use a tool such as http://webgraphviz.com/ to visualise the graph.

using Rivers.Serialization.Dot;

// Importing
var reader = new StreamReader("mygraph.dot");
var dotReader = new DotReader(reader);
var myGraph = reader.Read();

...

// Exporting
var writer = new StreamWriter("mygraph2.dot");
var dotWriter = new DotWriter(writer);
dotWriter.Write(myGraph);

About

A fast graphing library that allows for constructing, importing, exporting, and analysing graph structures in .NET.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages

  • C# 100.0%