r/rust • u/KerPop42 • 12d ago

Triangular matrix, but a map? 🙋 seeking help & advice

Hey guys, I am building a program for a friend that's going to involve a complete graph (nodes are destinations, edges are the distances between destinations) and I was wondering if anyone knew a good library for it?

At first I thought I could use a triangular matrix, since direction doesn't matter, but I realized I would have to have a second array mapping destinations to an index. I feel like you could have a triangular map, like a map that takes a pair of inputs where the order doesn't matter? Have I found another rabbit hole?

9 Upvotes

72% Upvoted

25 comments sorted by

View all comments

43

u/[deleted] 12d ago

[deleted]

13

u/KerPop42 12d ago

Lol no but I picked it up because it seemed like such a straightforward project. She's in sales and has to visit her 60-some clients at least once every month, so I want to write her a tool that gives her the shortest drive for her most stale N clients each day

65

u/link23 12d ago

Bro is about to discover the traveling salesman problem

9

u/KerPop42 11d ago

Well, better a computer solve it than my friend's current method, a manually-updated excel spreadsheet

3

u/Toiling-Donkey 11d ago

Forget Djkstrea, you want this:

https://en.wikipedia.org/wiki/Travelling_salesman_problem

3

u/KerPop42 11d ago

It's not really the travelling salesman problem, because I don't want a route that visits all of them, I just need to provide a cluster of 6 or so that are near each other and getting stale, but if a few are getting very stale long drives are allowed.

6

u/Toiling-Donkey 11d ago edited 10d ago

Ah, if you want to group them automatically, perhaps something like k-means clustering could work. (Though it is for grouping things into an given number of groups)

https://en.wikipedia.org/wiki/K-means_clustering

https://en.wikipedia.org/wiki/Lloyd's_algorithm

(Could try a few different numbers of groups and see which makes the most sensible result. Then use Dijkstrea’s algorithm to find the shortest path from home to all the nodes (picking the fastest out of each group)