directed_graph

KO | EN

gitlite — search

#python #hacktoberfest #go #golang #rust #linux #nodejs #macos #java #cli #awesome-list #vue #pytorch #ios

(★ 63)

Dart implementation of a directed graph. Provides algorithms for sorting vertices, retrieving a topological ordering or detecting cycles.

directed_graph Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Directed Graph

[![Dart](https://github.com/simphotonics/directed_graph/actions/workflows/dart.yml/badge.svg)](https://github.com/simphotonics/directed_graph/actions/workflows/dart.yml)

## 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`][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`][graphs].
It includes methods that enable:
* adding/removing vertices and edges,
* sorting of vertices and edges.

The library provides access to algorithms
for finding:
* the shortest path between vertices,
* the path with the lowest/highest weight (for weighted directed graphs),
* all paths connecting two vertices,
* the shortest paths from a vertex to all connected vertices,
* cycles,
* a topological ordering of the graph vertices,
* a reverse topological ordering of the graph vertices.

The class [`GraphCrawler`][GraphCrawler] can be used to retrieve *paths* or *walks* 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 a *weighted directed graph* each
edge is assigned a weight.

![Directed Graph Image](https://github.com/simphotonics/directed_graph/raw/main/images/directed_graph.svg?sanitize=true)

- *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.
- *Directed Edge*: An ordered pair of connected vertices (vi, vj). For example, the edge (A, C) starts at vertex A and ends at vertex C.
- *Path*: A path \[vi, ..., vn\] is an ordered list of at least two connected vertices where each *inner* vertex is *distinct*.
 The path \[A, E, G\] starts at vertex A and ends at vertex G.
- *Cycle*: A cycle is an ordered *list* of connected vertices where each inner vertex is distinct and the
first and last vertices are identical. The sequence \[F, I, K, F\] completes a cycle.
- *Walk*: A walk is an ordered *list* of at least two connected vertices.
\[D, F, I, K, F\] is a walk but not a path since the vertex F is listed twice.
- *DAG*: An acronym for *Directed Acyclic Graph*, a directed graph without cycles.
- *Topological ordering*: An ordered *set* of all vertices in a graph such that vi
occurs before vj if there is a directed edge (vi, vj).
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.
- *Quasi-topological ordering*: An ordered *sub-set* of graph vertices
such that vi
occurs before vj if there is a directed edge (vi, vj).
For example, the set \{ A, D, E, G \} represents a valid quasi-topological ordering,
even though the edges (I, K) and (L, L) render the total graph cyclic.
 * For a quasi-topological ordering to exist, any two vertices belonging to the *sub-set*
must not be mutually connected. That is, if there is a path \[vi, ..., vj\]
then there must not be a path \[vj, ..., vi\] and vice versa. Note:
 * The paths \[vi, ..., vj\] and
\[vj, ..., vi\] may include vertices that are *not* in
the sub-set, but belong to the graph.
 * A quasi-topological ordering many exist even if the
total graph is cyclic.

*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.

## Usage

To use this library include [`directed_graph`][directed_graph] as a dependency in your pubspec.yaml file. The
example below shows how to construct an object of type [`DirectedGraph`][DirectedGraph].

The graph classes provided by this library are generic with type argument
`T extends Object` (that is `T` must be non-nullable). The graphs
extend [`Iterable`][Iterable] making it possible to iterate over the graph vertices.

Graph vertices can be sorted if `T is Comparable` or
if a custom comparator function is provided.
Note: If `T is Comparable` and no comparator is provided, then
the following default comparator is automatically provided:
```Dart
(T left, T right) =>  (left as Comparable).compareTo(right);
```
In the example below, a custom
comparator is used to sort vertices in lexicographical order.

```Dart
import 'package:directed_graph/directed_graph.dart';
void main() {
  int comparator(String s1, String s2) => s1.compareTo(s2);
  int inverseComparator(String s1, String s2) => -comparator(s1, s2);

// Constructing a graph from vertices.

final graph = DirectedGraph<String>({
 'a': {'b', 'h', 'c', 'e'},
 'b': {'h'},
 'c': {'h', 'g'},
 'd': {'e', 'f'},
 'e': {'g'},
 'f': {'i'},
 //g': {'a'},
 'i': {'l'},
 'k': {'g', 'f'},
 }, comparator: comparator);

print('Example Directed Graph...');
  print('graph.toString():');
  print(graph);

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

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

print('\nLocal sources:');
  print(graph.localSources());

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

print('\nshortestPaths(a)');
  print(graph.shortestPaths('a'));

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

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

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

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

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

print('\nSorted Topological Ordering:');
  print(graph.topologicalOrdering(sorted: true));

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

print('\nReverse Topological Ordering:');
  print(graph.reverseTopologicalOrdering());

print('\nReverse Topological Ordering, sorted: true');
  print(graph.reverseTopologicalOrdering(sorted: true));

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

print('\nAdding edges: i -> k and i -> d');

// Add edge to render the graph cyclic
  graph.addEdge('i', 'k');
  //graph.addEdge('l', 'l');
  graph.addEdge('i', 'd');

print('\nCyclic graph:');
  print(graph);

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

print('\nCycle vertex:');
  print(graph.cycleVertex);

print('\ngraph.isAcyclic: ');
  print(graph.isAcyclic);

print('\nShortest Paths:');
  print(graph.shortestPaths('a'));

print('\nEdge exists: a->b');
  print(graph.edgeExists('a', 'b'));

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

print('\nStrongly connected components, sorted:');
  print(
    graph.stronglyConnectedComponents(sorted: true, comparator: comparator),
  );

print('\nStrongly connected components, sorted, inverse:');
  print(
    graph.stronglyConnectedComponents(
      sorted: true,
      comparator: inverseComparator,
    ),
  );

print('\nQuasi-Topological Ordering:');
  print(graph.quasiTopologicalOrdering({'d', 'e', 'a', 'g'}));

print('\nQuasi-Topological Ordering, sorted:');
  print(graph.quasiTopologicalOrdering({'d', 'e', 'a', 'g'}, sorted: true));

print('\nReverse-Quasi-Topological Ordering, sorted:');
  print(graph.reverseQuasiTopologicalOrdering({'d', 'e', 'a', 'g'}, sorted: true));
}

```

<details> <summary> Click to show the console output. </summary>

```Console
$ dart example/bin/directed_graph_example.dart
Example Directed Graph...
graph.toString():
{
 'a': {'b', 'h', 'c', 'e'},
 'b': {'h'},
 'h': {},
 'c': {'h', 'g'},
 'e': {'g'},
 'g': {},
 'd': {'e', 'f'},
 'f': {'i'},
 'i': {'l'},
 'l': {},
 'k': {'g', 'f'},
}

Is Acylic:
true

Strongly connected components:
[{h}, {b}, {g}, {c}, {e}, {a}, {l}, {i}, {f}, {d}, {k}]

Local sources:
[{a, d, k}, {b, c, e, f}, {g, h, i}, {l}]

shortestPath(d, l):
[d, f, i, l]

shortestPaths(a)
{b: [b], h: [h], c: [c], e: [e], g: [c, g]}

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}

Reverse Topological Ordering:
{l, g, i, f, k, h, e, d, c, b, a}

Reverse Topological Ordering, sorted: true
{h, b, g, c, e, a, l, i, f, d, k}

Local Sources:
[{a, d, k}, {b, c, e, f}, {g, h, i}, {l}]

Adding edges: i -> k and i -> d

Cyclic graph:
{
 'a': {'b', 'h', 'c', 'e'},
 'b': {'h'},
 'h': {},
 'c': {'h', 'g'},
 'e': {'g'},
 'g': {},
 'd': {'e', 'f'},
 'f': {'i'},
 'i': {'l', 'k', 'd'},
 'l': {},
 'k': {'g', 'f'},
}

Cycle:
[f, i, k, f]

Cycle vertex:
f

graph.isAcyclic:
false

Shortest Paths:
{b: [b], h: [h], c: [c], e: [e], g: [c, g]}

Edge exists: a->b
true

Strongly connected components:
[{h}, {b}, {g}, {c}, {e}, {a}, {l}, {k, i, f, d}]

Strongly connected components, sorted:
[{h}, {b}, {g}, {c}, {e}, {a}, {l}, {d, f, i, k}]

Strongly connected components, sorted, inverse:
[{l}, {g}, {e}, {k, i, f, d}, {h}, {c}, {b}, {a}]

Quasi-Topological Ordering:
{d, a, e, g}

Quasi-Topological Ordering, sorted:
{a, d, e, g}

Reverse-Quasi-Topological Ordering, sorted:
{g, e, a, d}
```
</details>

## Weighted Directed Graphs

The example below shows how to construct an object of type [`WeightedDirectedGraph`][WeightedDirectedGraph].
Initial graph edges are specified in the form of map of type `Map<T, Map<T, W>>`. The vertex type `T` extends
`Object` and therefore must be a non-nullable. The type associated with the edge weight `W` extends `Comparable`
to enable sorting of vertices by their edge weight.

The constructor takes an optional comparator function
as parameter. Vertices may be sorted if
a [comparator] function is provided
or if `T` implements [`Comparator`][Comparator].

```Dart
import 'package:directed_graph/directed_graph.dart';

void main(List<String> args) {
 int comparator(String s1, String s2) {
 return s1.compareTo(s2);
 }

final a = 'a';
  final b = 'b';
  final c = 'c';
  final d = 'd';
  final e = 'e';
  final f = 'f';
  final g = 'g';
  final h = 'h';
  final i = 'i';
  final k = 'k';
  final l = 'l';

int sum(int left, int right) => left + right;

var graph = WeightedDirectedGraph<String, int>(
 {
 a: {b: 1, h: 7, c: 2, e: 40, g: 7},
 b: {h: 6},
 c: {h: 5, g: 4},
 d: {e: 1, f: 2},
 e: {g: 2},
 f: {i: 3},
 i: {l: 3, k: 2},
 k: {g: 4, f: 5},
 l: {l: 0},
 },
 summation: sum,
 zero: 0,
 comparator: comparator,
 );

print('Weighted Graph:');
  print(graph);

print('\nNeighbouring vertices sorted by weight:');
  print(graph..sortEdgesByWeight());

final lightestPath = graph.lightestPath(a, g);
  print('\nLightest path a -> g');
  print('$lightestPath weight: ${graph.weightAlong(lightestPath)}');

final heaviestPath = graph.heaviestPath(a, g);
  print('\nHeaviest path a -> g');
  print('$heaviestPath weigth: ${graph.weightAlong(heaviestPath)}');

final shortestPath = graph.shortestPath(a, g);
  print('\nShortest path a -> g');
  print('$shortestPath weight: ${graph.weightAlong(shortestPath)}');

print('\nTransitive Closure');
  print(WeightedDirectedGraph.transitiveClosure(graph));

print('\nTransitive Weighted Edges:');
  print(graph.transitiveWeightedEdges);

print('\nVertices reachable from d:');
  print(graph.reachableVertices(d));

print('\nUpdate weight of edge (a,b) with value 101:');
  graph.updateEdgeWeight(vertex: a, connectedVertex: b, weight: 101);
  print('graph.weightedEdges(a): ${graph.weightedEdges(a)}');
}
```

<details> <summary> Click to show the console output. </summary>

```Console
$ dart example/bin/weighted_graph_example.dart
Weighted Graph:
{
 'a': {'b': 1, 'h': 7, 'c': 2, 'e': 40, 'g': 7},
 'b': {'h': 6},
 'c': {'h': 5, 'g': 4},
 'd': {'e': 1, 'f': 2},
 'e': {'g': 2},
 'f': {'i': 3},
 'g': {},
 'h': {},
 'i': {'l': 3, 'k': 2},
 'k': {'g': 4, 'f': 5},
 'l': {'l': 0},
}

Neighbouring vertices sorted by weight:
{
 'a': {'b': 1, 'c': 2, 'h': 7, 'g': 7, 'e': 40},
 'b': {'h': 6},
 'c': {'g': 4, 'h': 5},
 'd': {'e': 1, 'f': 2},
 'e': {'g': 2},
 'f': {'i': 3},
 'g': {},
 'h': {},
 'i': {'k': 2, 'l': 3},
 'k': {'g': 4, 'f': 5},
 'l': {'l': 0},
}

Lightest path a -> g
[a, c, g] weight: 6

Heaviest path a -> g
[a, e, g] weigth: 42

Shortest path a -> g
[a, g] weight: 7

Transitive Closure
{
 'a': {'b': 1, 'c': 2, 'h': 7, 'g': 6, 'e': 40},
 'b': {'h': 6},
 'c': {'g': 4, 'h': 5},
 'd': {'e': 1, 'f': 2, 'g': 3, 'i': 5, 'k': 7, 'l': 8},
 'e': {'g': 2},
 'f': {'i': 3, 'k': 5, 'l': 6, 'g': 9, 'f': 10},
 'g': {},
 'h': {},
 'i': {'k': 2, 'l': 3, 'g': 6, 'f': 7, 'i': 10},
 'k': {'g': 4, 'f': 5, 'i': 8, 'k': 10, 'l': 11},
 'l': {'l': 0},
}

Transitive Weighted Edges:
{a: {b: 1, c: 2, h: 7, g: 6, e: 40}, b: {h: 6}, c: {g: 4, h: 5}, d: {e: 1, f: 2, g: 3, i: 5, k: 7, l: 8}, e: {g: 2}, f: {i: 3, k: 5, l: 6, g: 9, f: 10}, g: {}, h: {}, i: {k: 2, l: 3, g: 6, f: 7, i: 10}, k: {g: 4, f: 5, i: 8, k: 10, l: 11}, l: {l: 0}}

Vertices reachable from d:
{e, g, f, i, k, l}

Update weight of edge (a,b) with value 101:
graph.weightedEdges(a): {b: 101, c: 2, h: 7, g: 7, e: 40}
```
</details>

## 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].

[comparator]: https://api.dart.dev/stable/dart-core/Comparator.html

[issue tracker]: https://github.com/simphotonics/directed_graph/issues

[collections]: https://api.dart.dev/stable/dart-collection/dart-collection-library.html

[example]: https://github.com/simphotonics/directed_graph/tree/main/example

[graphs-examples]: https://pub.dev/packages/graphs#-example-tab-

[graphs]: https://pub.dev/packages/graphs

[directed_graph]: https://pub.dev/packages/directed_graph

[GraphCrawler]: https://pub.dev/documentation/directed_graph/latest/directed_graph/GraphCrawler-class.html

[DirectedGraph]: https://pub.dev/documentation/directed_graph/latest/directed_graph/DirectedGraph-class.html

[Iterable]: https://api.dart.dev/dart-core/Iterable-class.html

[WeightedDirectedGraph]: https://pub.dev/documentation/directed_graph/latest/directed_graph/WeightedDirectedGraph-class.html

directed_graph

directed_graph Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

directed_graph

directed_graph Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README