# Directed Graph

## Introduction

An integral part of storing, manipulating, and retrieving numerical data are data structures or as they are called in Dart: collections. Arguably the most common data structure is the list. It enables efficient storage and retrieval of sequential data that can be associated with an index.

A more general (non-linear) data structure where an element may be connected to one, several, or none of the other elements is called a graph.

Graphs are useful when keeping track of elements that are linked to or are dependent on other elements. Examples include: network connections, links in a document pointing to other paragraphs or documents, foreign keys in a relational database, file dependencies in a build system, etc.

The package `directed_graph` contains an implementation of a Dart graph that follows the recommendations found in graphs-examples and is compatible with the algorithms provided by `graphs`. It is simple to use and includes methods that enable:

• the sorting of vertices.

• the shortest path between vertices,
• all paths connecting two vertices,
• cycles,
• a topological ordering of the graph vertices.

The class `GraphCrawler` can be used to find all paths connecting two vertices.

## Terminology

Elements of a graph are called vertices (or nodes) and neighbouring vertices are connected by edges. The figure below shows a directed graph with unidirectional edges depicted as arrows. Graph edges are emanating from a vertex and ending at a vertex.

• In-degree of a vertex: Number of edges ending at this vertex. For example, vertex H has in-degree 3.
• Out-degree of a vertex: Number of edges starting at this vertex. For example, vertex F has out-degree 1.
• Source: A vertex with in-degree zero is called (local) source. Vertices A and D in the graph above are local sources.
• Edge: An ordered pair of connected vertices. For example, the edge (A, C) starts at vertex A and ends at vertex C.
• Path: A directed path is an ordered list of at least two connected vertices. The path (A, E, G) starts at vertex A and ends at vertex G.
• Cycle: A path that starts and ends at the same vertex. For example, a self-loop is a cycle. The dashed edges in the figure complete a cycle.
• DAG: An acronym for Directed Acyclic Graph, a directed graph without cycles.
• Topological ordering: An ordered list of all vertices in a graph such that vertex1 occurs before vertex2 if there is an edge pointing from vertex1 to vertex2. A topological ordering of the graph above is: `A, D, B, C, E, K, F, G, H, I, L`. Hereby, dashed edges were disregarded since a cyclic graph does not have a topological ordering.

Note: In the context of this package the definition of edge might be more lax compared to a rigorous mathematical definition. For example, self-loops, that is edges connecting a vertex to itself are explicitly allowed.

For simplicity, edges are (internally) stored in a structure of type `Map<Vertex<T>, List<Vertex<T>>>` and there is nothing preventing a user from inserting self-loops or multiple edges between the same nodes. While self-loops will render a graph cyclic, multiple entries of the same edge do not affect the algorithms calculating a topological ordering of vertices.

## Usage

To use this library include `directed_graph` as a dependency in your pubspec.yaml file. The example below shows how to construct a graph. The constructor takes an optional comparator function as parameter. If a comparator is specified, vertices are sorted accordingly. For more information see comparator.

``````import 'package:directed_graph/directed_graph.dart';
import 'package:ansicolor/ansicolor.dart';
import 'package:directed_graph/graph_crawler.dart';

// To run this program navigate to
// the folder 'directed_graph/example'
// in your terminal and type:
//
// # dart bin/example.dart
//
// followed by enter.
void main() {
var a = Vertex<String>('A');
var b = Vertex<String>('B');
var c = Vertex<String>('C');
var d = Vertex<String>('D');
var e = Vertex<String>('E');
var f = Vertex<String>('F');
var g = Vertex<String>('G');
var h = Vertex<String>('H');
var i = Vertex<String>('I');
var k = Vertex<String>('K');
var l = Vertex<String>('L');

int comparator(
Vertex<String> vertex1,
Vertex<String> vertex2,
) {
return vertex1.data.compareTo(vertex2.data);
}

int inverseComparator(Vertex<String> vertex1, Vertex<String> vertex2) =>
-comparator(vertex1, vertex2);

// Constructing a graph from vertices.
var graph = DirectedGraph<String>(
{
a: [b, h, c, e],
b: [h],
c: [h, g],
d: [e, f],
e: [g],
f: [i],
i: [l],
k: [g, f]
},
comparator: comparator,
);

// Constructing a graph from data.
// Note: Each object is converted to a vertex.
var graphII = DirectedGraph<String>.fromData({
'A': ['B', 'H', 'C', 'E'],
'B': ['H'],
'C': ['H', 'G'],
'D': ['E', 'F'],
'E': ['G'],
'F': ['I'],
'I': ['L'],
'K': ['G', 'F'],
}, comparator: comparator);

final bluePen = AnsiPen()..blue(bold: true);
final magentaPen = AnsiPen()..magenta(bold: true);

print(magentaPen('Example Directed Graph...'));
print(bluePen('\ngraph.toString():'));
print(graph);

print(bluePen('\ngraphII.toString():'));
print(graphII);

print(bluePen('\nIs Acylic:'));
print(graph.isAcyclic);

print(bluePen('\nStrongly connected components:'));
print(graph.stronglyConnectedComponents);

print(bluePen('\nShortestPath(d, l):'));
print(graph.shortestPath(d, l));

print(bluePen('\nInDegree(C):'));
print(graph.inDegree(c));

print(bluePen('\nOutDegree(C)'));
print(graph.outDegree(c));

print(bluePen('\nVertices sorted in lexicographical order:'));
print(graph.vertices);

print(bluePen('\nVertices sorted in inverse lexicographical order:'));
graph.comparator = inverseComparator;
print(graph.vertices);
graph.comparator = comparator;

print(bluePen('\nInDegreeMap:'));
print(graph.inDegreeMap);

print(bluePen('\nSorted Topological Ordering:'));
print(graph.sortedTopologicalOrdering);

print(bluePen('\nTopological Ordering:'));
print(graph.topologicalOrdering);

print(bluePen('\nLocal Sources:'));
print(graph.localSources);

// Add edge to render the graph cyclic

print(bluePen('\nCycle:'));
print(graph.cycle);

// Create graph crawler.
final crawler = GraphCrawler<String>(edges: graph.edges);

print(bluePen('\nPaths from D to L.'));
print(crawler.paths(d, l));

print(bluePen('\nPaths from D to I.'));
print(crawler.paths(d, i));

print(bluePen('\nPaths from A to H.'));
print(crawler.paths(a, h));

print(bluePen('\nPaths from L to L.'));
print(crawler.paths(l, l));

print(bluePen('\nPath from F to F.'));
print(crawler.path(f, f));

print(bluePen('\nPath from A to H.'));
print(crawler.path(a, h));

print(bluePen('\nTree with root L.'));
print(crawler.tree(l));

print(bluePen('\nTree with root A, target H.'));
print(crawler.tree(a, target: h));

print(bluePen('\nTree with root A, target G.'));
print(crawler.tree(a, target: g));

print(bluePen('\nPaths from L to L.'));
print(crawler.paths(l, l));
}

``````
Click to show the console output.
``````  \$ dart example/bin/example.dart
Example Directed Graph...

graph.toString():
{
A: [B, H, C, E],
B: [H],
C: [H, G],
D: [E, F],
E: [G],
F: [I],
G: [],
H: [],
I: [L],
K: [G, F],
L: [],
}

Example Directed Graph...

graphII.toString():
{
A: [B, H, C, E],
B: [H],
C: [H, G],
D: [E, F],
E: [G],
F: [I],
G: [],
H: [],
I: [L],
K: [G, F],
L: [],
}

Is Acylic:
true

Strongly connected components:
[[H], [B], [G], [C], [E], [A], [L], [I], [F], [D], [K]]

ShortestPath(d, l):
[F, I, L]

InDegree(C):
1

OutDegree(C)
2

Vertices sorted in lexicographical order:
[A, B, C, D, E, F, G, H, I, K, L]

Vertices sorted in inverse lexicographical order:
[L, K, I, H, G, F, E, D, C, B, A]

InDegreeMap:
{A: 0, B: 1, H: 3, C: 1, E: 2, G: 3, D: 0, F: 2, I: 1, L: 1, K: 0}

Sorted Topological Ordering:
[A, B, C, D, E, H, K, F, G, I, L]

Topological Ordering:
[A, B, C, D, E, H, K, F, I, G, L]

Local Sources:
[[A, D, K], [B, C, E, F], [G, H, I], [L]]

Cycle:
[L, L]

Paths from D to L.
[[D, F, I, L]]

Paths from D to I.
[[D, F, I]]

Paths from A to H.
[[A, B, H], [A, H], [A, C, H]]

Paths from L to L.
[[L, L]]

Path from F to F.
[F, I, K, F]

Path from A to H.
[A, H]

Tree with root L.
[[L], [L, L]]

Tree with root A, target H.
[[A], [A, B], [A, H]]

Tree with root A, target G.
[[A], [A, B], [A, H], [A, C], [A, E], [A, B, H], [A, C, H], [A, C, G]]

Paths from L to L.
[[L, L]]

``````

## Examples

For further information on how to generate a topological sorting of vertices see example.

## Features and bugs

Please file feature requests and bugs at the issue tracker.

## Libraries

directed_graph
Dart implementation of a directed graph. Provides methods to [...]
graph_crawler
Library providing `GraphCrawler`, a utility class for finding paths connecting two vertices.