Hi all,
I want to add a Dijkstra example to my DCI library for PHP. I was
debating about how to design the functionality of finding the
closest unvisited node from the start node, which is really a more
general question: does it ever make sense to have a role that
doesn't operate on its own role player's data, but only the data
in other roles?
This is the role method in question, located in the UnvisitedNodes role in this version (let's call it version 1):
If I weren't thinking about the code, the mental model I would naturally lean toward would be to put that role method in StartNode, as I did on the following branch (version 2—and yes I know I did this backwards by not thinking more about my mental model up-front ;-) ):
As you can see from this code snippet, it doesn't use any of the
data in the StartNode role player, but only CurrentNode,
TentativeDistances, and UnvisitedNodes.
So it belongs to StartNode only based on my mental model (one of
multiple possible mental models) and not any consideration about
what data it's operating on. I'm leaning toward sticking with this
mental model (StartNode.findClosestUnvisitedNode), but this is the
first time I've really encountered this so I'd be curious to hear
what you all think.
Thanks,
Matt
On 3 Dec 2024, at 04.22, Matthew Browne <mbro...@gmail.com> wrote:Hi all,
I want to add a Dijkstra example to my DCI library for PHP. I was debating about how to design the functionality of finding the closest unvisited node from the start node, which is really a more general question: does it ever make sense to have a role that doesn't operate on its own role player's data, but only the data in other roles?
This is the role method in question, located in the UnvisitedNodes role in this version (let's call it version 1):
If I weren't thinking about the code, the mental model I would naturally lean toward would be to put that role method in StartNode, as I did on the following branch (version 2—and yes I know I did this backwards by not thinking more about my mental model up-front ;-) ):
trait StartNode{function findClosestUnvisitedNode() {$this->context->currentNode->determinePreviousInPath();$tentativeDistances = $this->context->tentativeDistances;$unvisitedNodes = iterator_to_array($this->context->unvisitedNodes);if (empty($unvisitedNodes)) {return null;}return array_reduce($unvisitedNodes,function($x, $y) use ($tentativeDistances) {return $tentativeDistances->distanceTo($x) < $tentativeDistances->distanceTo($y)? $x: $y;},$unvisitedNodes[0]);}}
As you can see from this code snippet, it doesn't use any of the data in the StartNode role player, but only CurrentNode, TentativeDistances, and UnvisitedNodes.
So it belongs to StartNode only based on my mental model (one of multiple possible mental models) and not any consideration about what data it's operating on. I'm leaning toward sticking with this mental model (StartNode.findClosestUnvisitedNode), but this is the first time I've really encountered this so I'd be curious to hear what you all think.
Thanks,
Matt
--
You received this message because you are subscribed to the Google Groups "object-composition" group.
To unsubscribe from this group and stop receiving emails from it, send an email to object-composit...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/object-composition/11b118db-5fd3-423c-a679-cb34c541c9c1%40gmail.com.
I have found that having methods with arguments in DCI:
public function shortestPathFrom(Node $startNode, Node $destinationNode)might be a smell.
I just did it that way so that after creating an instance of CalculateShortestPath, you can calculate a shortest path again from a different start/destination in the same graph without having to create a new instance. I don't feel strongly about it and could certainly change it, but what is the downside of binding several roles in the shortestPathFrom() method (rather than the constructor), given that this Context has no other public operations?
Is there a reason that $startNode and $destinationNode are not Roles?
They are already roles in my implementation.
Another smell: the method
private function processCurrentNode(): Node | null {
begs to be a method of the currentNode. I can see that it’s not because in your model, CurrentNode is not a role that a node can play. I think it’s a Role.
CurrentNode was already a role as well, but I agree that the
functionality in processCurrentNode() makes more sense as a role
method. I just refactored it:
I don’t think StartNode should have any methods. It is just another name for one of the objects. That object will be of interest when the code interacts with it through CurrentNode.
Could you elaborate a bit on why that's your favored approach
here?
Den 4. dec. 2024 kl. 03.23 skrev Matthew Browne <mbro...@gmail.com>:
I just did it that way so that after creating an instance of CalculateShortestPath, you can calculate a shortest path again from a different start/destination in the same graph without having to create a new instance. I don't feel strongly about it and could certainly change it, but what is the downside of binding several roles in the shortestPathFrom() method (rather than the constructor), given that this Context has no other public operations?
Hi Rune,
To me rebinding suffers from some of the same mental issues as class oriented vs object oriented. It treats the context object as a compile time construct just as class oriented treats any type of objects.
I can definitely see how role re-binding could lead to more
fragile code in some cases, but in the case Cope was pointing out,
it's all essentially initialization code. I think the point you've
raised here might be a larger point than what Cope said, which are
both worthy of discussion but we should probably separate those
out.
In order to complete the Dijkstra algorithm with a single context
instance, the CurrentNode role has to be re-bound. Alternatively
it can be implemented using multiple context instances and
recursion, as you did in your Marvin
implementation of the algorithm.
I'm not strictly opposed to re-implementing it with immutable
role bindings, but my original goal was just to write an
implementation similar to the other existing DCI implementations
with the exception of the Marvin one (as far as I know that's the
only one that avoids role re-binding). And I would like to
understand what the practical problem is in this particular case
before doing so...to me it feels like I'm already thinking in
terms of run-time, it's just that my run-time object happens to be
mutable rather than immutable, kind of like how you can put new
wheels on a car and it's still generally considered to be the same
car. I can still create as many varying instances of the context
as I want.
If I understand correctly, Cope was making a narrower point: not saying that no roles should be re-bound, but just that all the initial role bindings at the start of the algorithm should be done in the constructor rather than in CalculateShortestPath.shortestPathFrom(). But as I said above, I regard that as still being initialization code, or re-initialization in the case where you want to take an existing instance of CalculateShortestPath (where you already set the graph in the constructor) and now you want to know the shortest path between a different pair of nodes. It's a pretty minor convenience though (and yes I mean convenience, not inconvenience), and since it's a bit unconventional, maybe I should just move that role binding code to the constructor. I just don't see the actual downside of it.
Thanks,
Matt
--
You received this message because you are subscribed to the Google Groups "object-composition" group.
To unsubscribe from this group and stop receiving emails from it, send an email to object-composit...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/object-composition/CAJ7XQb7rsHuVcC1KwmZqfJ7OwYWku1NJ_bFE%3DOwx_tdroAd0EA%40mail.gmail.com.
Update: I moved those role assignments to the constructor, because I realized I hadn't actually tested calling the same context instance multiple times, and making that work correctly would have required binding UnvisitedNodes and ShortestPathSegments in the operation method (shortestPathFrom()), which definitely would have put it over the edge to where it was doing too much.
I also moved StartNode.findClosestUnvisitedNode() to CurrentNode.findClosestUnvisitedNode(). Here's the updated version in case anyone is interested:
BTW, I kept the original street map with its weights from the
original examples on fulloo.info, because I realized (when I first
started working on this) that only uneven weights make a
difference for the shortest path when it's a grid with only
perpendicular intersections. So the weights here mean traffic or
some other factor, since higher weights for larger distances
wouldn't be meaningful for a city grid.
To view this discussion visit https://groups.google.com/d/msgid/object-composition/6EC8F737-2DF6-4DAF-8AA3-62C358F0D9B8%40gmail.com.
In the C++ example, for one:
https://fulloo.info/Examples/C++Examples/Dijkstra/DCIDijkstraInC++.html
But I just remembered that I did tweak the numbers a bit, even though the letters and their arrangement is the same, and the shortest path is the same. (This is what happens when you start working on something and then put it down for a few months before actually finishing it, haha.) I remember now that I initially changed the avenues to all have a cost of at least 3, since avenues in Manhattan are as long as 3 streets. But it doesn't really have any consequences on how it works.
FYI I also looked at the trygve example as a starting point,
which uses the same street grid as the C++ one, and technically
that's linked from fulloo.info too but only indirectly via
Github—I just noticed that it isn't actually listed on this page,
in case you wanted to add it:
https://fulloo.info/Examples/TrygveExamples/