pathfinding

[Vib-UX]

fixes #190

[codecov-commenter]

Codecov Report

Merging #192 (698cb5a) into main (eacb603) will decrease coverage by 0.90%. The diff coverage is 45.05%.

:exclamation: Current head 698cb5a differs from pull request most recent head 96146da. Consider uploading reports for the commit 96146da to get more accurate results

@@            Coverage Diff             @@
##             main     #192      +/-   ##
==========================================
- Coverage   93.37%   92.47%   -0.91%     
==========================================
  Files         182      183       +1     
  Lines        4757     4848      +91     
  Branches      561      581      +20     
==========================================
+ Hits         4442     4483      +41     
- Misses        174      214      +40     
- Partials      141      151      +10     

Impacted Files	Coverage Δ
packages/graph/lib/PriorityQueue.ts	34.00% <34.00%> (ø)
packages/graph/lib/graph.ts	73.01% <58.53%> (-26.99%)	:arrow_down:

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update eacb603...96146da. Read the comment docs.

[Vib-UX]

K its coming along nicely. Some nits surrounding coding style that we can go over. The biggest issues I see are:

1. The construction of the adjacency list is only from node1 -> node2. The graph is a symmetric directed graph meaning each channel is two edges: node1->node2 and node2->node1.
2. This would be facilitated by using the Node's channels property, which is a Map. If it helps you can create a secondary property on Node that returns a tuple containing the [Channel,ChannelSettings] for the Node's channel setting which would aid in point 1.
3. Finding the min distance should ideally use a heap, but we can get to optimizations later.

Yes, I made a mistake it should behave like an undirected graph. Nice Catch 😓

[bmancini55]

Yes, I made a mistake it should behave like an undirected graph. Nice Catch sweat

Conceptually yes, channels are similar to undirected/symmetric directed graph. So both directions or every node pair where a channel exists are theoretically possible and need to be considered. For routing purposes that symmetry may break when:

1. A channel only has settings on one side (meaning it only received a channel_update from one of the nodes)
2. A node may disable it's side of the channel in the update message
3. The min/max settings may prevent an HTLC from being routeable.

[bmancini55]

Also just for edification, node1/node2 in the channel are just the lexicographical ordering of the identifiers. When I first starting learning this stuff I thought node1 was the opener or had some larger meaning. But it's just the node with the lower ordered nodeId.

[Vib-UX]

Also just for edification, node1/node2 in the channel are just the lexicographical ordering of the identifiers. When I first starting learning this stuff I thought node1 was the opener or had some larger meaning. But it's just the node with the lower ordered nodeId.

That's really insightful 💡 , I actually thought that node1 is probably the one who opened the channel.

[Vib-UX]

K its coming along nicely. Some nits surrounding coding style that we can go over. The biggest issues I see are:

1. The construction of the adjacency list is only from node1 -> node2. The graph is a symmetric directed graph meaning each channel is two edges: node1->node2 and node2->node1.
2. This would be facilitated by using the Node's channels property, which is a Map. If it helps you can create a secondary property on Node that returns a tuple containing the [Channel,ChannelSettings] for the Node's channel setting which would aid in point 1.
3. Finding the min distance should ideally use a heap, but we can get to optimizations later.

For Heap optimization, I found this package related to priority queues we can import that and workaround with it or should I build it from scratch?

• https://www.npmjs.com/package/priorityqueuejs

[bmancini55]

For Heap optimization, I found this package related to priority queues we can import that and workaround with it or should I build it from scratch?

* https://www.npmjs.com/package/priorityqueuejs

Scratch, we try to avoid external packages where possible.

We'll most likely put it in the Core package but feel free to add it to this project first so we don't have to deal with deps issues while prototyping.

[Vib-UX]

For Heap optimization, I found this package related to priority queues we can import that and workaround with it or should I build it from scratch?

* https://www.npmjs.com/package/priorityqueuejs

Scratch, we try to avoid external packages where possible.

We'll most likely put it in the Core package but feel free to add it to this project first so we don't have to deal with deps issues while prototyping.

Sure 🤝

[Vib-UX]

min-heap looks good with a couple minors. If you want to split that into a separate PR and add tests we can merge it in.

I still need to review dijkstras using the heap.

separate PR would make it look neat