NewYour coding agent can read the release notes before it upgrades.Set up the MCP server →
Packagist
Packagist, #3904 most downloaded on Packagist
GraPHP is the mathematical graph/network library written in PHP.
Latest stable
v0.9.3
Last release 5 years ago
no release in 18 months
Ships unpredictably
gaps range from 2 months to 4.6 years
Nearly every release is documented
notes for 9 of 9 stable releases
Nothing withdrawn
no release was ever pulled
14 years old
9 releases · first in 2013
Drag across the ruler to compare, or tap a release to open it.
Feature: Support PHP 8.1 release. (#208 by @clue)
Feature: Support PHP 8.1 release. (#208 by @clue)
Fix: Fix automatic vertex ID generation when using vertex IDs with strings. (#204 by @viktorprogger)
Improve test suite and use GitHub Actions for continuous integration (CI). (#207 by @clue)
Feature: Support PHP 8 and PHPUnit 9.3. (#200 by @SimonFrings)
Fix: Deleting vertex with loop edge no longer fails. (#149 by @tomzx)
Your coding agent can read these notes before it upgrades. Set up the MCP server →
Fix: Deleting vertex with loop edge no longer fails. (#149 by @tomzx)
Fix: Fix returning directed loop edges and adjacent vertices from vertex twice. (#170 by @clue)
Minor documentation updates and fixes. (#153 by @marclaporte and #163, #164 and #172 by @clue)
Improve test suite to move tests to Fhaculty\Graph\Tests namespace,
update test suite to support PHPUnit 6 and PHPUnit 5 and
support running on legacy PHP 5.3 through PHP 7.2 and HHVM.
(#148 by @tomzx and #150 and #162 by @clue)
Originally planned to add a new AttributeAware::removeAttribute() method,
but reverted due to BC break. Change will be reconsidered for next major release.
(#138 and #171 by @johnathanmdell and @clue)
BC break: Split off individual components in order to stabilize core graph lib.
Algorithm namespace into separate graphp/algorithms package.
(#119)Exporter\TrivialGraphFormat into separate graphp/trivial-graph-format package.
(#121)Loader namespace into separate graphp/plaintext package.
(#117)Graph and Graph::__toString() (trivial graph format exporter has been split off).
(#122)src/ and add tests to achieve 100% test coverage.
(#127 & #129)Feature: Add general purpose Attributes.
Graph, Vertex and EdgeBase classes can now be
extended in order to implement a custom behavior. As such, one can now also
instantiate them using the normal new operator instead of having to use
Graph::createVertex() family of methods.
(#82)Algorithm\Directed::isDirected() to remove its ambiguity
in regards to mixed and/or empty graphs
(#80)| Old name | New name |
|---|---|
Algorithm\Directed::isDirected() |
Algorithm\Directed::hasDirected() |
Algorithm\Directed::hasUndirected() and
Algorithm\Directed::isMixed() in order to complement the renamed
Algorithm\Directed::hasDirected()
(#80)Walk::factoryCycleFromVertices() no longer tries to auto-complete
a cycle if the first vertex does not match the last one, but now throws an
InvalidArgumentException instead (#87)Walks, i.e. a walk with only a single edge from
vertex A back to A (#87)Algorithm\ShortestPath\MooreBellmanFord now also works for unweighted
edges. This also fixes an issue where Algorithm\DetectNegativeCycle didn't work
for unweighted edges. (#81)Algorithm\MinimumCostFlow algorithms now work again. The reference
to a non-existant class has been updated. Also fixed several issues with
regards to special cases such as disconnected or undirected graphs.
(#74)getVertexFirst(),
getVertexSource() and getVertexTarget()
(#76):| Old name | New name |
|---|---|
Graph::getVertexFirst() |
Graph::getVertices()->getVertexFirst() |
Walk::getVertexSource() |
Walk::getVertices()->getVertexFirst() |
Walk::getVertexTarget() |
Walk::getVertices()->getVertexLast() |
Fix: Throwing an UnexpectedValueException if writing GraphViz Dot script to a temporary file fails and remove its debugging output (#77 and #78 @Metab
Feature: Add new Set\Vertices and Set\Edges classes that handle common operations on a Set of multiple Vertex and Edge instances respectively.
Set\Vertices and Set\Edges classes that handle common
operations on a Set of multiple Vertex and Edge instances respectively.
(#48)| Old name | New name |
|---|---|
Edge\Base::getFirst() |
Set\Edges::getEdgeOrder() |
Edge\Base::getAll() |
Set\Edges::getEdgesOrder() |
Edge\Base::ORDER_* |
Set\Edges::ORDER_* |
| --- | --- |
Vertex::getFirst() |
Set\Vertices::getVertexOrder() |
Vertex::getAll() |
Set\Vertices::getVerticesOrder() |
Vertex::ORDER_ |
Set\Vertices::ORDER_* |
getVertices*() and getEdges*() method now returns a Set
instead of a primitive array of instances. Most of the time this should
work without changing your code, because each Set implements an Iterator
interface and can easily be iterated using foreach. However, using a Set
instead of a plain array differs when checking its boolean value or
comparing two Sets. I.e. if you happen to want to check if an Set is empty,
you now have to use the more explicit syntax $set->isEmpty().Vertex::getVertices(), Vertex::getVerticesEdgeTo() and
Vertex::getVerticesEdgeFrom() now return a Set\Vertices instance that
may contain duplicate vertices if parallel (multiple) edges exist. Previously
there was no easy way to detect this situation - this is now the default. If
you also want to get unique / distinct Vertex instances, use
Vertex::getVertices()->getVerticesDistinct() where applicable.getVerticesId(), use
getVertices()->getIds() instead.Cycle into Walk (#61).
As such, its static factory methods had to be renamed. Update your references if applicable:| Old name | New name |
|---|---|
Cycle::factoryFromPredecessorMap() |
Walk::factoryCycleFromPredecessorMap() |
Cycle::factoryFromVertices() |
Walk::factoryCycleFromVertices() |
Cycle::factoryFromEdges() |
Walk::factoryCycleFromEdges() |
Graph::isEmpty() because it's not well-defined and might
be confusing. Most literature suggests it should check for existing edges,
whereas the old behavior was to check for existing vertices instead. Use either
of the new and more transparent methods
Algorithm\Property\GraphProperty::isNull() (old behavior) or (where applicable)
Algorithm\Property\GraphProperty::isEdgeless() (#63).Walk::factoryCycleFromPredecessorMap(),
Walk::factoryCycleFromVertices(), Walk::factoryCycleFromEdges()) now
actually makes sure the returned Walk instance is actually a valid Cycle,
i.e. the start Vertex is the same as the end Vertex (#61)Algorithm\ShortestPath algorithm now consistenly does not
return a zero weight for the root Vertex and now supports loop edges on the root
Vertex (#62)Algorithm\ShortestPath algorithm now consistently throws an
OutOfBoundsException for unreachable vertices
(#62)Algorithm\Tree\Base::isTree()
accordingly.
(#72)getNumberOfVertices() and
getNumberOfEdges() (#75 and
#48):| Old name | New name |
|---|---|
$set->getNumberOfVertices() |
count($set->getVertices()) |
$set->getNumberOfEdges() |
count($set->getEdges()) |
Set class with Set\DualAggregate interface. This
is unlikely to affect you, but might potentially break your custom
inheritance or polymorphism for algorithms.
(#75)Algorithm\ShortestPath\Base::hasVertex(Vertex $vertex) to check whether
a path to the given Vertex exists (#62).Algorithm\MinimumSpanningTree\Base::getWeight() to get total
weight of resulting minimum spanning tree (MST).
(#73)Algorithm\MinimumSpanningTree algorithm now supports
undirected and mixed Graphs, as well as null weights for Edges.
(#73)Algorithm\MinimumSpanningTree algorithm now throws an
UnexpectedValueException for unconnected Graphs (and thus also null Graphs).
(#73)Walk::factoryFromVertices()
(#64).Walk::isValid()
(#61)Algorithm\ShortestPath\MooreBellmanFord::getCycleNegative() from actually
throwing the right UnderflowException if no cycle was found
(#62)Exporter\Image::setFormat() had no effect due to misassignment
(#70 @FGM)BC break: Move algorithm definitions in base classes to separate algorithm classes (#27). The following methods containing algorithms were now moved t
| Old name | New name | Related ticket |
|---|---|---|
Set::getWeight() |
Algorithm\Weight::getWeight() |
#33 |
Set::getWeightFlow() |
Algorithm\Weight::getWeightFlow() |
#33 |
Set::getWeightMin() |
Algorithm\Weight::getWeightMin() |
#33 |
Set::isWeighted() |
Algorithm\Weight::isWeighted() |
#33 |
| - | - | - |
Graph::getDegree() |
Algorithm\Degree::getDegree() |
#29 |
Graph::getDegreeMin() |
Algorithm\Degree::getDegreeMin() |
#29 |
Graph::getDegreeMax() |
Algorithm\Degree::getDegreeMax() |
#29 |
Graph::isRegular() |
Algorithm\Degree::isRegular() |
#29 |
Graph::isBalanced() |
Algorithm\Degree::isBalanced() |
#29 |
Vertex::getDegree() |
Algorithm\Degree:getDegreeVertex() |
#49 |
Vertex::getDegreeIn() |
Algorithm\Degree:getDegreeInVertex() |
#49 |
Vertex::getDegreeOut() |
Algorithm\Degree:getDegreeOutVertex() |
#49 |
Vertex::isSink() |
Algorithm\Degree:isVertexSink() |
#49 |
Vertex::isSource() |
Algorithm\Degree:isVertexSource() |
#49 |
Vertex::isIsolated() |
Algorithm\Degree::isVertexIsolated() |
#49 |
| - | - | - |
Set::isDirected() |
Algorithm\Directed::isDirected() |
#34 |
| - | - | - |
Graph::isSymmetric() |
Algorithm\Symmetric::isSymmetric() |
#41 |
| - | - | - |
Graph::isComplete() |
Algorithm\Complete::isComplete() |
#43 |
| - | - | - |
Set::hasFlow() |
Algorithm\Flow::hasFlow() |
#47 |
Graph::getBalance() |
Algorithm\Flow::getBalance() |
#30, #47 |
Graph::isBalancedFlow() |
Algorithm\Flow::isBalancedFlow() |
#30, #47 |
Vertex::getFlow() |
Algorithm\Flow::getFlowVertex() |
#47 |
| - | - | - |
Vertex::isLeaf() |
Algorithm\Tree\Undirected::isVertexLeaf() |
#44 |
| - | - | - |
Set::hasLoop() |
Algorithm\Loop::hasLoop() |
#51 |
Vertex::hasLoop() |
Algorithm\Loop::hasLoopVertex() |
#51 |
| - | - | - |
Set::hasEdgeParallel() |
Algorithm\Parallel::hasEdgeParallel() |
#52 |
Edge\Base::hasEdgeParallel() |
Algorithm\Parallel::hasEdgeParallelEdge() |
#52 |
Edge\Base::getEdgesParallel() |
Algorithm\Parallel::getEdgeParallelEdge() |
#52 |
| - | - | - |
Graph::isEdgeless() |
Algorithm\Property\GraphProperty::isEdgeless() |
#54 |
Graph::isTrivial() |
Algorithm\Property\GraphProperty::isTrivial() |
#54 |
Walk::isCycle() |
Algorithm\Property\WalkProperty::isCycle() |
#54 |
Walk::isPath() |
Algorithm\Property\WalkProperty::isPath() |
#54 |
Walk::hasCycle() |
Algorithm\Property\WalkProperty::hasCycle() |
#54 |
Walk::isLoop() |
Algorithm\Property\WalkProperty::isLoop() |
#54 |
Walk::isDigon() |
Algorithm\Property\WalkProperty::isDigon() |
#54 |
Walk::isTriangle() |
Algorithm\Property\WalkProperty::isTriangle() |
#54 |
Walk::isSimple() |
Algorithm\Property\WalkProperty::isSimple() |
#54 |
Walk::isHamiltonian() |
Algorithm\Property\WalkProperty::isHamiltonian() |
#54 |
Walk::isEulerian() |
Algorithm\Property\WalkProperty::isEulerian() |
#54 |
| Old/removed alias definition | Actual name |
|---|---|
Graph::isConnected() |
Algorithm\ConnectedComponents::isSingle() |
Graph::hasEulerianCycle() |
Algorithm\Eulerian::hasCycle() |
Graph::getNumberOfComponents() |
Algorithm\ConnectedComponents::getNumberOfComponents() |
Graph::getNumberOfGroups() |
Algorithm\Groups::getNumberOfGroups() |
Graph::isBipartit() |
Algorithm\Bipartit::isBipartit() |
Vertex::hasPathTo() |
Algorithm\ShortestPath\BreadthFirst::hasVertex() |
Vertex::hasPathFrom() |
Algorithm\ShortestPath\BreadthFirst::hasVertex() |
Vertex::getVerticesPathTo() |
Algorithm\ShortestPath\BreadthFirst::getVertices() |
Vertex::getVerticesPathFrom() |
Algorithm\ShortestPath\BreadthFirst::getVertices() |
Graph::createVertices() now returns an array of vertices instead of the
chainable Graph (#19)Loader\UmlClassDiagram to separate fhaculty/graph-uml
repo (#38)Algorithm\MinimumSpanningTree\PrimWithIf
(use Algorithm\MinimumSpanningTree\Prim instead)
(#45)Vertex::createEdgeTo() now returns an instance of type
Edge\Undirected instead of Edge\UndirectedId
(#46)Edge\Base::setCapacity() now consistently throws an RangeException
instead of InvalidArgumentException if the current flow exceeds the new maximum
capacity (#53)Algorithm\Tree namespace with algorithms for undirected and directed,
rooted trees (#44)Algorithm\Weight (#33)Algorithm\Degree (#29, #49)Algorithm\Directed (#34)Algorithm\Symmetric (#41)Algorithm\Complete (#43)Algorithm\Flow (#30, #47)Algorithm\Tree (#44)Algorithm\Loop (#51)Algorithm\Parallel (#52)Algorithm\Property (#54)Graph::createVertices() now also accepts an array of vertex IDs
(#19)Algorithm\Property\WalkProperty::hasLoop() alias definition for
completeness (#54)Algorithm\Property\WalkProperty::isCircuit() definition to distinguish
circuits from cycles (#54)Vertex/Edge layout attributes
(#32)First tagged release (See issue #20 for more info on why it starts as v0.5.0)
One column per quarter.