brainglobe / brainglobe/brainglobe-data-api-connectivity

Strongest Average Path Strategy

Open
#29 1 comment 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.