v0.16.2

Fixed

• Fixed ShortestPath for an edge case.

v0.16.1

Fixed

• Fixed TransitiveReduction not to incorrectly report cycles.

v0.16.0

This release contains breaking changes to the public API (see "Changed").

Added

• Added the Store interface, introducing support for custom storage implementations.
• Added the NewWithStore function for explicitly initializing a graph with a Store instance.
• Added the EdgeData functional option that can be used with AddEdge, introducing support for arbitrary data.
• Added the Data field to EdgeProperties for retrieving data added using EdgeData.

Changed

• Changed Order to additionally return an error instance (breaking change).
• Changed Size to additionally return an error instance (breaking change).

v0.15.1

Changed

• Changed ShortestPath to return ErrTargetNotReachable if the target vertex is not reachable.

Fixed

• Fixed ShortestPath to return correct results for large unweighted graphs.

v0.15.0

Added

• Added the ErrVertexAlreadyExists error instance. Use errors.Is to check for this instance.
• Added the ErrEdgeAlreadyExists error instance. Use errors.Is to check for this instance.
• Added the ErrEdgeCreatesCycle error instance. Use errors.Is to check for this instance.

Changed

• Changed AddVertex to return ErrVertexAlreadyExists if the vertex already exists.
• Changed VertexWithProperties to return ErrVertexNotFound if the vertex doesn't exist.
• Changed AddEdge to return ErrVertexNotFound if either vertex doesn't exist.
• Changed AddEdge to return ErrEdgeAlreadyExists if the edge already exists.
• Changed AddEdge to return ErrEdgeCreatesCycle if cycle prevention is active and the edge would create a cycle.
• Changed Edge to return ErrEdgeNotFound if the edge doesn't exist.
• Changed RemoveEdge to return the error instances returned by Edge.

v0.14.0

Added

• Added the ErrVertexNotFound error instance.

Changed

• Changed TopologicalSort to fail at runtime when a cycle is detected.
• Changed TransitiveReduction to return the transitive reduction as a new graph and fail at runtime when a cycle is detected.
• Changed Vertex to return ErrVertexNotFound if the desired vertex couldn't be found.

v0.13.0

Added

• Added the VertexProperties type for storing vertex-related properties.
• Added the VertexWithProperties method for retrieving a vertex and its properties.
• Added the VertexWeight functional option that can be used for AddVertex.
• Added the VertexAttribute functional option that can be used for AddVertex.
• Added support for rendering vertices with attributes using draw.DOT.

Changed

• Changed AddVertex to accept functional options.
• Renamed PermitCycles to PreventCycles. This seems to be the price to pay if English isn't a library author's native language.

Fixed

• Fixed the behavior of ShortestPath when the target vertex is not reachable from one of the visited vertices.

v0.12.0

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.

v0.11.0

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.

v0.10.0

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.