directed_graph 0.1.0

Directed graph with algorithms enabling topological ordering and sorting of vertices.

example/README.md

Directed Graph

Example

The file example.dart (see folder bin) demonstrates how to create a numerical representation of the directed graph shown in the figure below using the package directed_graph.

The program also shows how to add/remove vertices and edges, determine if the graph is acyclic, or obtain a list of vertices in topological order.

The methods stronglyConnectedComponents() and shortestPath are provided for convenience only as they are simply calling the homonymously named functions provided by the package graphs.

The program can be run in a terminal by navigating to the folder directed_graph/example in your local copy of this library and using the command:

$ dart bin/example.dart

import 'package:directed_graph/directed_graph.dart';
import 'package:ansicolor/ansicolor.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);

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

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

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

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

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

  print(bluePen('\nShortestPath(orange,darkRed):'));
  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());

}

Features and bugs

Please file feature requests and bugs at the issue tracker.