graphs 0.2.0

Build Status #

Graph algorithms which do not specify a particular approach for representing a Graph.

Functions in this package will take arguments that provide the mechanism for traversing the graph. For example two common approaches for representing a graph:

class Graph {
  Map<Node, List<Node>> nodes;
}
class Node {
  // Interesting data
}
class Graph {
  Node root;
}
class Node {
  List<Node> edges;
  // Interesting data
}

Any representation can be adapted to the needs of the algorithm:

  • Some algorithms need to associate data with each node in the graph. If the node type T does not correctly or efficiently implement hashCode or ==, you may provide optional equals and/or hashCode functions are parameters.
  • Algorithms which need to traverse the graph take a edges function which provides the reachable nodes.
    • (node) => graph[node]
    • (node) => node.edges

Graphs which are resolved asynchronously will have similar functions which return FutureOr.

0.2.0-dev #

  • BREAKING shortestPath, shortestPaths and stronglyConnectedComponents now have one generic parameter and have replaced the key parameter with optional params: {bool equals(T key1, T key2), int hashCode(T key)}. This follows the pattern used in dart:collection classes HashMap and LinkedHashMap. It improves the usability and performance of the case where the source values are directly usable in a hash data structure.

0.1.3+1 #

  • Fixed a bug with non-identity key in shortestPath and shortestPaths.

0.1.3 #

  • Added shortestPath and shortestPaths functions.
  • Use HashMap and HashSet from dart:collection for stronglyConnectedComponents. Improves runtime performance.

0.1.2+1 #

  • Allow using non-dev Dart 2 SDK.

0.1.2 #

  • crawlAsync surfaces exceptions while crawling through the result stream rather than as uncaught asynchronous errors.

0.1.1 #

  • crawlAsync will now ignore nodes that are resolved to null.

0.1.0 #

  • Initial release with an implementation of stronglyConnectedComponents and crawlAsync.

example/example.dart

// Copyright (c) 2017, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

import 'package:graphs/graphs.dart';

/// A representation of a directed graph.
///
/// Data is stored on the [Node] class.
class Graph {
  final Map<Node, List<Node>> nodes;

  Graph(this.nodes);
}

class Node {
  final String id;
  final int data;

  Node(this.id, this.data);

  @override
  bool operator ==(Object other) => other is Node && other.id == id;

  @override
  int get hashCode => id.hashCode;

  @override
  String toString() => '<$id -> $data>';
}

void main() {
  var nodeA = Node('A', 1);
  var nodeB = Node('B', 2);
  var nodeC = Node('C', 3);
  var nodeD = Node('D', 4);
  var graph = Graph({
    nodeA: [nodeB, nodeC],
    nodeB: [nodeC, nodeD],
    nodeC: [nodeB, nodeD]
  });

  var components = stronglyConnectedComponents<Node>(
      graph.nodes.keys, (node) => graph.nodes[node]);

  print(components);
}

Use this package as a library

1. Depend on it

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


dependencies:
  graphs: ^0.2.0

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:graphs/graphs.dart';
  
Popularity:
Describes how popular the package is relative to other packages. [more]
91
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]
95
Learn more about scoring.

We analyzed this package on Sep 13, 2019, and provided a score, details, and suggestions below. Analysis was completed with status completed using:

  • Dart: 2.5.0
  • pana: 0.12.21

Platforms

Detected platforms: Flutter, web, other

No platform restriction found in primary library package:graphs/graphs.dart.

Dependencies

Package Constraint Resolved Available
Direct dependencies
Dart SDK >=2.0.0 <3.0.0
Dev dependencies
analyzer ^0.34.0
path ^1.1.0
pedantic ^1.3.0
test ^1.5.1