search

graphp / algorithms

Common mathematical graph algorithms implemented in PHP
MIT License
135 stars 68 forks source link

Add dedicated Result interfaces for algorithms #4

Closed clue closed 5 years ago

clue commented 9 years ago

Originally reported by @clue in clue/graph#94:

A lot of our algorithms would benefit from a dedicated Result interface, which saves the intermediary result for further operations. Also, passing its arguments to the createResult() method instead of the constructor allows for a much cleaner design by interchanging the actual algorithm implementation (via dependency injection).

For example, calling the following code always calculates the whole algorithm and then only returns a subset of its results:

$alg = new EdmondsKarp($va, $vb);
$max1 = $alg->getFlowMax();
$max2 = $alg->getFlowMax();

Instead, I'd like to propose something like this, which makes it clear when the actual algorithm runs:

$alg = new EdmondsKarp();
$result = $alg->createResult($va, $vb);
$max1 = $result->getFlowMax();
$max2 = $result->getFlowMax();

This applies to at least MaxFlow, MaximumMatching, MinimumCostFlow, MinimumSpanningTree, ShortestPath, TravelingSalesmanProblem and perhaps a few others.

I'm opening this one as a way to discuss this concept and also to link the first batch of PRs against. I'd love to get some feedback!

clue commented 5 years ago

I still see how this could potentially be useful, but given the discussion in #19 (and others), I don't see me chasing this any time soon. Accordingly, I don't see it's likely this will get traction any time soon, so I will have to close this for now.