Skip to content

Latest commit

 

History

History
147 lines (105 loc) · 5.79 KB

CHANGELOG.md

File metadata and controls

147 lines (105 loc) · 5.79 KB
Raw

Changelog

All notable changes to this project will be documented in this file.

The format is based on Keep a Changelog, and this project adheres to Semantic Versioning.

[0.12.0] - 2022-09-19

Added

  • Added the PermitCycles option to explicitly prevent the creation of cycles.

Changed

  • Changed the Acyclic option to not implicitly impose cycle checks for operations like AddEdge. To prevent the creation of cycles, use PermitCycles.
  • Changed TopologicalSort to only work for graphs created with PermitCycles. This is temporary.
  • Changed TransitiveReduction to only work for graphs created with PermitCycles. This is temporary.

[0.11.0] - 2022-09-15

Added

  • Added the Order method for retrieving the number of vertices in the graph.
  • Added the Size method for retrieving the number of edges in the graph.

Changed

  • Changed the graph logo.
  • Changed an internal operation of ShortestPath from O(n) to O(log(n)) by implementing the priority queue as a binary heap. Note that the actual complexity might still be defined by ShortestPath itself.

Fixed

  • Fixed draw.DOT to work correctly with vertices that contain special characters and whitespaces.

[0.10.0] - 2022-09-09

Added

  • Added the PredecessorMap method for obtaining a map with all predecessors of each vertex.
  • Added the RemoveEdge method for removing the edge between two vertices.
  • Added the Clone method for retrieving a deep copy of the graph.
  • Added the TopologicalSort function for obtaining the topological order of the vertices in the graph.
  • Added the TransitiveReduction function for transforming the graph into its transitive reduction.

Changed

  • Changed the visit function of DFS to accept a vertex hash instead of the vertex value (i.e. K instead of T).
  • Changed the visit function of BFS to accept a vertex hash instead of the vertex value (i.e. K instead of T).

Removed

  • Removed the Predecessors function. Use PredecessorMap instead and look up the respective vertex.

[0.9.0] - 2022-08-17

Added

  • Added the Graph.AddVertex method for adding a vertex. This replaces Graph.Vertex.
  • Added the Graph.AddEdge method for creating an edge. This replaces Graph.Edge.
  • Added the Graph.Vertex method for retrieving a vertex by its hash. This is not to be confused with the old Graph.Vertex function for adding vertices that got replaced with Graph.AddVertex.
  • Added the Graph.Edge method for retrieving an edge. This is not to be confused with the old Graph.Edge function for creating an edge that got replaced with Graph.AddEdge.
  • Added the Graph.Predecessors function for retrieving a vertex' predecessors.
  • Added the DFS function.
  • Added the BFS function.
  • Added the CreatesCycle function.
  • Added the StronglyConnectedComponents function.
  • Added the ShortestPath function.
  • Added the ErrEdgeNotFound error indicating that a desired edge could not be found.

Removed

  • Removed the Graph.EdgeByHashes method. Use Graph.AddEdge instead.
  • Removed the Graph.GetEdgeByHashes method. Use Graph.Edge instead.
  • Removed the Graph.DegreeByHash method. Use Graph.Degree instead.
  • Removed the Graph.Degree method.
  • Removed the Graph.DFS and Graph.DFSByHash methods. Use DFS instead.
  • Removed the Graph.BFS and Graph.BFSByHash methods. Use BFS instead.
  • Removed the Graph.CreatesCycle and Graph.CreatesCycleByHashes methods. Use CreatesCycle instead.
  • Removed the Graph.StronglyConnectedComponents method. Use StronglyConnectedComponents instead.
  • Removed the Graph.ShortestPath and Graph.ShortestPathByHash methods. Use ShortestPath instead.

[0.8.0] - 2022-08-01

Added

  • Added the EdgeWeight and EdgeAttribute functional options.
  • Added the Properties field to Edge.

Changed

  • Changed Edge to accept a variadic options parameter.
  • Changed EdgeByHashes to accept a variadic options parameter.
  • Renamed draw.Graph to draw.DOT for more clarity regarding the rendering format.

Removed

  • Removed the WeightedEdge function. Use Edge with the EdgeWeight functional option instead.
  • Removed the WeightedEdgeByHashes function. Use EdgeByHashes with the EdgeWeight functional option instead.

Fixed

  • Fixed missing edge attributes when drawing a graph using draw.DOT.

[0.7.0] - 2022-07-26

Added

  • Added draw package for graph visualization using DOT-compatible renderers.
  • Added Traits function for retrieving the graph's traits.

[0.6.0] - 2022-07-22

Added

  • Added AdjacencyMap function for retrieving an adjancency map for all vertices.

Removed

  • Removed the AdjacencyList function.

[0.5.0] - 2022-07-21

Added

  • Added AdjacencyList function for retrieving an adjacency list for all vertices.

Changed

  • Updated the examples in the documentation.

[0.4.0] - 2022-07-01

Added

  • Added ShortestPath function for computing shortest paths.

Changed

  • Changed the term "properties" to "traits" in the code and documentation.
  • Don't traverse all vertices in disconnected graphs by design.

[0.3.0] - 2022-06-27

Added

  • Added StronglyConnectedComponents function for detecting SCCs.
  • Added various images to usage examples.

[0.2.0] - 2022-06-20

Added

  • Added Degree and DegreeByHash functions for determining vertex degrees.
  • Added cycle checks when adding an edge using the Edge functions.

[0.1.0] - 2022-06-19

Added

  • Added CreatesCycle and CreatesCycleByHashes functions for predicting cycles.

[0.1.0-beta] - 2022-06-17

Changed

  • Introduced dedicated types for directed and undirected graphs, making Graph[K, T] an interface.

[0.1.0-alpha] - 2022-06-13

Added

  • Introduced core types and methods.