# 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:

- adding/removing vertices and edges,
- the sorting of vertices.

The library provides access to algorithms for finding:

- 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
graph.addEdges(i, [k]);
graph.addEdges(l, [l]);
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.