brainglobe / brainglobe/brainglobe-data-api-connectivity
Strongest Average Path Strategy
- Dominant language
- Python
- Stars
- 2
- Forks
- 1
- Avg merge
- 3d 13h
- Merged PRs (30d)
- 2
Description
A follow on from #19 |
Joel has also expressed a desire for calculating "strongest average path strengths".
I think we can handle this with our `DijkstraStrategy` class, by mutating how the cost is stored and how it is computed from what is stored. If we create a new subclass for the strongest average path strategy and do the following:
- Store the "costs" as tuples, of the form `(total_weight_to_here, number_of_steps_to_here)`.
- Under this convention;
- `starting_node_initial_distance` should return `(0, 0)`.
- `regular_node_initial_distance` should return `(inf, 1)`. Note that the default number of steps is 1 - this is important later.
- `cost_to` is calculated as the sum of `(current_cost[0] + next_node_weight) / (current_cost[1] + 1)`. Note that this avoids division by zeros when the number of steps to reach the current node is 0 (like it will be with the start node, or when we check if we've reached a previously un-reachable node).
- `is_lower_cost` checks whether `proposed_cost[0]/proposed_cost[1] < current_cost[0]/current_cost[1]`. Note that here we should _never_ encounter division by zero errors here, since `proposed_cost[1]` and `current_cost[1]` can only be 0 if we are considering moving back to the starting node, but that node is marked as visited when the algorithm begins, so we never do this. `regular_node_initial_distance` having the value `(inf, 1)` ensures that nodes we haven't yet reached always have their cost evaluated to `inf / 1 = inf`, which also avoids division by 0.
Contributor guide
Research direction
Start by reading the existing DijkstraStrategy class and the context from follow-on issue #19. Implement the strongest average path strategy using tuple costs, the specified initial distances, average-cost comparison, and step counting; done means the strategy can calculate paths by strongest average strength without division-by-zero errors.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- python
- Domain
- backend
- Issue type
- Feature
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100