graph

Are you using graph? Check out the graph user survey

Added

• Added the AllPathsBetween function for computing all paths between two vertices.

Changed

• Changed StableTopologicalSort to invoke the less function as few as possible, reducing comparisons.
• Changed CreatesCycle to use an optimized path if the default in-memory store is being used.
• Changed map allocations to use pre-defined memory sizes.

Fixed

• Fixed the major performance issues of StableTopologicalSort.

Fixed

• Fixed TopologicalSort to retain its original performance.

Added

• Added the StableTopologicalSort function for deterministic topological orderings.
• Added the VertexAttributes functional option for setting an entire vertex attributes map.

Added

• Added the BFSWithDepth function for performing a BFS with depth information.

Fixed

• Fixed false positives of ErrVertexHasEdges when removing a vertex.

Release post: graph Version 0.20 Is Out

Added

• Added the Graph.AddVerticesFrom method for adding all vertices from another graph.
• Added the Graph.AddEdgesFrom method for adding all edges from another graph.
• Added the Graph.Edges method for obtaining all edges as a slice.
• Added the Graph.UpdateEdge method for updating the properties of an edge.
• Added the Store.UpdateEdge method for updating the properties of an edge.
• Added the NewLike function for creating a new graph that is "like" the given graph.
• Added the EdgeAttributes functional option for setting an entire edge attributes map.

Changed

• Changed Graph.Clone to use the built-in in-memory store for storing vertices and edges for cloned graphs.

Added

• Added the MinimumSpanningTree function for finding a minimum spanning tree.
• Added the MaximumSpanningTree function for finding a maximum spanning tree.

Added

• Added the Graph.RemoveVertex method for removing a vertex.
• Added the Store.RemoveVertex method for removing a vertex.
• Added the ErrVertexHasEdges error instance.
• Added the Union function for combining two graphs into one.

Added

• Added the draw.GraphAttributes functional option for draw.DOT for rendering graph attributes.

Changed

• Changed the library's GoDoc documentation.

Fixed

• Fixed ShortestPath for an edge case.

Fixed

• Fixed TransitiveReduction not to incorrectly report cycles.

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

Changed

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

Fixed

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

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.

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.

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.

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.

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.

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.