p-hatan / mirrormirror.p-hatan.ir

Viewing version 2.3.2. Open the latest package page.

graphs

2.3.2

Graph algorithms that operate on graphs in any representation.

Download archive

Readme

CI pub package package publisher

Graph algorithms that 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 that are resolved asynchronously will have similar functions which return FutureOr.

Changelog

2.3.2

  • Require Dart 3.4
  • Update to the latest version of package:dart_flutter_team_lints.

2.3.1

  • Update package repository after move.

2.3.0

  • Add a transitiveClosure function.
  • Make stronglyConnectedComponents and topologicalSort iterative rather than recursive to avoid stack overflows on very large graphs.
  • Require Dart 2.18

2.2.0

  • Add a secondarySort parameter to the topologicalSort() function which applies an additional lexical sort where that doesn't break the topological sort.

2.1.0

  • Add a topologicalSort() function.

2.0.0

  • Breaking: crawlAsync will no longer ignore a node from the graph if the readNode callback returns null.

1.0.0

  • Migrate to null safety.
  • Breaking: Paths from shortestPath[s] are now returned as iterables to reduce memory consumption of the algorithm to O(n).

0.2.0

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

Installing

export PUB_HOSTED_URL=https://pub.mirror.p-hatan.ir
flutter pub add 'graphs:2.3.2'
pubspec.yaml
name: graphs
version: 2.3.2
description: Graph algorithms that operate on graphs in any representation.
repository: https://github.com/dart-lang/tools/tree/main/pkgs/graphs

environment:
  sdk: ^3.4.0

dependencies:
  collection: ^1.15.0

dev_dependencies:
  dart_flutter_team_lints: ^3.0.0
  test: ^1.21.6

  # For examples
  analyzer: '>=5.2.0 <7.0.0'
  path: ^1.8.0
  pool: ^1.5.0

Version history

VersionPublishedArchiveSHA-256
0.1.0Cached · Upstream SHA-256 matchedDownload79e0b059…7930b4
0.1.1Cached · Upstream SHA-256 matchedDownload54b58581…21654c
0.1.2Cached · Upstream SHA-256 matchedDownload208bca8f…20eebb
0.1.2+1Cached · Upstream SHA-256 matchedDownload5a533764…336b4b
0.1.3Cached · Upstream SHA-256 matchedDownload0a92d81c…734924
0.1.3+1Cached · Upstream SHA-256 matchedDownload9735f30b…6c65c9
0.2.0Cached · Upstream SHA-256 matchedDownloaddb4e50f3…15af52
1.0.0Cached · Upstream SHA-256 matchedDownloade84da18c…797f5e
2.0.0Cached · Upstream SHA-256 matchedDownloade07b56af…d1da0c
2.1.0Cached · Upstream SHA-256 matchedDownloadae0b3d95…a6679c
2.2.0Cached · Upstream SHA-256 matchedDownloadf9e130f3…db39b2
2.3.0Cached · Upstream SHA-256 matchedDownload772db3d5…89ba0e
2.3.1Cached · Upstream SHA-256 matchedDownloadaedc5a15…2a4d19
2.3.2Cached · Upstream SHA-256 matchedDownload741bbf84…7bb8d0

Dependencies

collection "^1.15.0"