Skip to content

v0.7.0

Pre-release
Pre-release
Compare
Choose a tag to compare
@sdboyer sdboyer released this 03 Sep 18:10
· 4 commits to master since this release
0.7.0
a219231

This release refactors, and adds to, the set of methods for traversing/iterating graphs.

  • Graph::eachAdjacent($vertex) -> Graph::adjacentTo($vertex). The semantics here have also changed significantly; the iterator produces only a value, which is the adjacent vertex. More importantly, the notion of adjacency is now correct - vertices are adjacent regardless of edge direction. Behavior is unchanged for undirected graphs; for directed graphs, the old behavior is now available via the new successorsOf($vertex) method.
  • Graph::eachVertex() -> Graph::vertices(). The semantics have also changed: only a value is emitted, and that value is the vertex. The 'adjacency set' is no longer emitted at all, as it was not only confusing, but also rested on the same incorrect notion of adjacency as above.
  • Graph::eachEdge() -> Graph::edges(). Semantics are unchanged.
  • Introduced Graph::incidentTo($vertex); the edge-traversing counterpart to adjacentTo($vertex).
  • Introduced Digraph::successorsOf($vertex), which emits successor vertices as values.
  • Introduced Digraph::predecessorsOf($vertex), which emits predecessor vertices as values.
  • Introduced Digraph::arcsFrom($vertex), which emits outbound arcs as values.
  • Introduced Digraph::arcsTo($vertex), which emits inbound arcs as values.

Other changes:

  • Edge-adding methods on the Mutable* interfaces were changes from addEdge(), addDirectedEdge() to ensureEdge() and ensureArc() respectively. This reflects the fact that these interfaces are intended to describe simple graphs (disallowing parallel edges); at some point in the future, separate interfaces may be created for multigraphs that are more appropriate for "add" semantics.
  • Interfaces were granulated and renamed a bit. DirectedGraph -> Digraph. The Mutable interface hierarchy was separated for graphs and digraphs, for which MutableVertexSet was introduced as a shared component.
  • Tests for graphs have been refactored to be spec-driven. This means that new graph implementations can be written and tested trivially easily, simply by including the appropriate testing traits.

Note that there is little intention to backport these changes to 5.3, in large part due to the heavy reliance on traits.

This should be the last pre-1.0.0 release; that will be reached once documentation is up to snuff.

Assets 2