directed_graph 0.1.6

  • Readme
  • Changelog
  • Example
  • Installing
  • 77

Directed Graph #

Build Status

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.

Directed Graph Image

  • 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';

// 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],
      b: [h],
      c: [h, g],
      d: [e, f],
      e: [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(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]);

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

  // Create graph crawler.
  final crawler = GraphCrawler<String>(edges: graph.edges);
  print(bluePen('\nPaths from A to H.'));
  print(crawler.paths(a, h));
}
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: [],
    }

    Is Acylic:
    true

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

    ShortestPath(f,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:
    [F, I, K, F]

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

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.

0.1.6 #

Added info about class GraphCrawler.

0.1.5 #

Added explicit generic type parameter to graph getter iterator.

0.1.4 #

Added class GraphCrawler.

Transformed the following DirectedGraph methods to getters:

  • isAcyclic,
  • localSources,
  • outDegreeMap,
  • sortedTopologicalOrdering,
  • stronglyConnectedComponents,
  • topologicalOrdering.

Added methods for finding cycles in cyclic graphs:

  • cycle
  • findCycle()

0.1.3 #

Specified type of the parameter comparator in DirectedGraph constructor.

0.1.2 #

Amended equality operator of ConstantVertex.

0.1.1 #

Amended section ##Usage in README.md.

0.1.0 #

Fixed logic in removeEdges(). The field comparator is no longer final, it can be set to trigger a resort of the graph vertices.

0.0.5 #

Edited image url.

0.0.4 #

Added method localSources(). DirectedGraph now extends Iterator.

0.0.3 #

Amended README.md, included travis icon.

0.0.2 #

Amended package description.

0.0.1 #

Initial version of the library.

example/README.md

Directed Graph #

Build Status

Example #

The file example.dart (see folder bin) contains a short program that 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.

Directed Graph Image

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

Features and bugs #

Please file feature requests and bugs at the issue tracker.

Use this package as a library

1. Depend on it

Add this to your package's pubspec.yaml file:


dependencies:
  directed_graph: ^0.1.6

2. Install it

You can install packages from the command line:

with pub:


$ pub get

with Flutter:


$ flutter pub get

Alternatively, your editor might support pub get or flutter pub get. Check the docs for your editor to learn more.

3. Import it

Now in your Dart code, you can use:


import 'package:directed_graph/directed_graph.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
54
Health:
Code health derived from static analysis. [more]
100
Maintenance:
Reflects how tidy and up-to-date the package is. [more]
100
Overall:
Weighted score of the above. [more]
77
Learn more about scoring.

We analyzed this package on Jul 9, 2020, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.8.4
  • pana: 0.13.14

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.7.0 <3.0.0
graphs ^0.2.0 0.2.0
lazy_evaluation ^0.0.6+3 0.0.6+3
meta ^1.2.1 1.2.2 1.3.0-nullsafety
Dev dependencies
test ^1.15.2