directed_graph

• Added the graph method sort, to enable the sorting of vertices and edges. The vertices must be comparable or a suitable comparator must be provided.
  • By default, vertices are stored (and printed) in insertion order.
  • Subsequent insertion of vertices and edges might invalidate the sorting.

• Added [DirectedGraph][DirectedGraph], [WeightedDirectedGraph][WeightedDirectedGraph] method removeEdge.

• Fixed the documentation of the graph method clear. This method removes all graph vertices. The resulting graph will be empty.
• Added the graph method clearEdges. This method removes only the graph edges, leaving the graph vertices in place.

• Added WeightedDirectedGraph methods: weightedEdges and updateEdgeWeight.
• Updated docs and examples.

• Fixed grammar in CHANGELOG entry below.
• Moved [GraphCrawler][GraphCrawler] to a separate folder.
• Added function defaultComparator<T>() which returns a function of type Comparator<T>.
• When constructing a graph with vertices of type T and no explicit comparator is provided, then the function defaultComparator<T>() is provided instead.
• If a user explicitly sets the graph comparator to null, then vertices and edges will not be sorted. To restore the default see below:

  final graph = DirectedGraph<String>({a: {b}}); // Has default comparator.
  print(graph.hasComparator); // Prints true.
  graph.comparator = graph.inverseComparator; // Has explicitly set comparator.
  print(graph.hasComparator); // Prints true.
  graph.comparator = null;
  print(graph.hasComparator); // Prints false;
  graph.comparator = defaultComparator<String>(); // Restoring the default comp.
  

• The graph method contains, now explicitly uses the keys of the underlying map to calculate its result.

• The graph length is now calculated using an efficient length iterable (the keys of the map storing the graph edges). The function reachableVertices was moved from DirectedGraphBase to [GraphCrawler][GraphCrawler]. It is now using a more efficient recursive algorithm.
• Extended the definition of a quasi-topological ordering in section Usage.
• Lowered the required SDK version to ^3.5.0.

• Breaking changes: The following getters have been converted to functions, to reflect the fact that a potentially long computation is be needed to calculate the result:

  • stronglyConnectedComponents({bool sorted, Comparator <T> comparator}) and the function return type has been changed to List<Set> to show the fact that each scc is a set of vertices and to make searching a component for a specify vertex more efficient,
  • topologicalOrdering({bool sorted}),
  • cycle(),
  • localSource().

• The getters cycleVertex and isAcyclic were kept, but are now cached and only updated if vertices or edges are added/removed.

• The getter sortedTopologicalOrdering was removed. To get the equivalent result call topologicalOrdering(sorted:true).

• New additions:

  • addEdge({vertex, connectedVertex}) was added to DirectedGraph and BiDirectedGraph to make it consistent with WeightedDirectedGraph,
  • reverseTopologicalOrdering({bool sorted}), for the meaning of quasi-topological ordering see Section Terminology of README.md.
  • quasiTopologicalOrdering({bool sorted}),
  • reverseQuasiTopologicalOrdering({bool sorted}).

• Fixed a bug related to the addition of a default comparator if the generic type T of DirectedGraph<T> is Comparable<T>.

• Updated dependencies.

• Updated dependencies.
• Updated benchmark report.

• Fixed bug where cache was updated after calling the method addEdge on an instance of type WeightedDirectedGraph.
• Updated dependencies.
• Updated benchmark_runner version and benchmark report.

• Updated deps.

• Updated deps.
• Added topics to pubspec.yaml.

• Updated section Usage.
• Updated dependencies.
• Applied suggested lints.

• Updated dependencies.
• Library now uses latest version of [lazy_memo][lazy_memo].
• Removed dependency on [graphs][graphs].
• Benchmarks now using [benchmark_runner][benchmark_runner].

• Updated dependencies.
• Amended extensions in sort.dart.
• Sorting is now possible without specifying a Comparator as long as the the vertex type T implements Comparable.
• Added tests.

• Updated dependencies.
• Applied suggested lints.

• Updated deps.
• Added graph methods edgeExists and vertexExists.

• Replace package pedantic with lints.
• Updated deps.

• Amended docs. Migrated from travis to github actions.

• Eliminated cyclic dependency between class [WeightedDirectedGraph][WeightedDirectedGraph] and extension GraphUtils.
• Added getter crawler.
• Added the method clear() to classes [DirectedGraph][DirectedGraph] and [WeightedDirectedGraph][WeightedDirectedGraph].

• Added weighted graph getter transitiveWeightedEdges and method addEdge().

• Amended factory constructor DirectedGraph.transitiveClosure().

• Amended documentation.

• Added null-safety features.
• Tightened the definition of path. A path [v_i, ..., v_n] is an ordered list of at least two connected vertices where each inner vertex is distinct.
• Functions returning a topological ordering now return an ordered set of vertices, reflecting the fact that in a topological ordering each vertex must be distinct.
• Added the classes [WeightedDirectedGraph][WeightedDirectedGraph] and BiDirectedGraph.
• Complete overhaul of the class GraphCrawler.

Added [GraphCrawler][GraphCrawler] method tree. Amended methods path and paths.

Added the getter data.

Removed debug print statement.

Amended README.md.

• Moved [GraphCrawler][GraphCrawler] to a separate file.
• Amended graph crawler method paths.
• Added [DirectedGraph][DirectedGraph] constructor .fromData.

Corrected missing links in dartdocs.

Incorporated pedantic lint suggestions. Updated docs.

Added info about class [[GraphCrawler][GraphCrawler]][GraphCrawler].

Added explicit generic type parameter to graph getter iterator.

Added class [GraphCrawler][GraphCrawler].

Converted the following [DirectedGraph][DirectedGraph] methods to getters:

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

Added methods for finding cycles in cyclic graphs:

• cycle
• findCycle()

Specified type of the parameter comparator in [DirectedGraph][DirectedGraph] constructor.

Amended equality operator of ConstantVertex.

Amended section ##Usage in README.md.

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

Edited image url.

Added method localSources(). DirectedGraph now extends Iterator.

Amended README.md, included travis icon.

Amended package description.

Initial version of the library.