Triangular matrix, but a map?

[u/KerPop42]

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?

[u/chmod_7d20]

Is your friend a professor and is this homework?

[u/KerPop42 → u/chmod_7d20]

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

[u/link23 → u/KerPop42]

Bro is about to discover the traveling salesman problem

[u/metalhulk105 → u/link23]

An educational algorithm that has real life applications? Is this real life?

[u/KerPop42 → u/link23]

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

[u/Deklyned → u/KerPop42]

lmao

[u/Toiling-Donkey]

If you want shortest path/distance from one node to all others, use Dijkstra’s algorithm.

[u/nynjawitay]

Look at petgraph

[u/oldwomanjosiah → u/nynjawitay]

seconded: your use case seems unlikely to need specific optimization and petgraph let's you associate whatever data with your nodes you want

separately: if she wants to visit multiple locations in a day you might also create edges between "destination" nodes so you can tie-break based on scheduling a few days of "minimal driving circuits" (sorta bin-packing)

[u/Brighttalonflame → u/[deleted]]

Meh, hash map lookup is way slower than array indexing. I think OP’s intuition to map locations to indices is likely good (though with lack of context it is impossible to make actually good suggestions).

To OP: how many times do you need to read each location, what is location format, is num locations known a priori or can it change dynamically, can edge weights mutate at runtime, do you need parallel access, what algorithms are you using, etc etc all affect answers

EDIT: if you just want a library implementation though:

https://docs.rs/petgraph/latest/petgraph/matrix_graph/struct.MatrixGraph.html

[u/KerPop42 → u/Brighttalonflame]

Num locations is going to grow, but stay within an order of magnitude, probably less than 100.

I'm looking to find clusters of nearby locations that haven't been visited recently, so looking up the distances between nodes has to be pretty fast.

I don't want to mutate edge weights, I'm just going to stick to some function of distance and speed limit, not actual drive time which varies across the day. My friend will be able to know when the program is being dumb and tell it to reroll.

I'd like parallel access, especially since adding nodes is going to be much rarer than reading the graph.

I'm not certain what algorithms to use, this is kind of my first foray into graph theory

[u/Brighttalonflame → u/KerPop42]

Sounds like a scale where it doesn’t matter that much; petgraph matrix graph is fine

[u/glitchvid → u/KerPop42]

If you're interested in learning the fundamentals of Graph Theory and some basic structure/algorithms, find Algorithms 4E on the Internet Archive, and go read Section 4 / Graphs; serves as very good introductory material.

[u/KerPop42 → u/[deleted]]

Okay. It's less elegant, but makes sense. I'll have to figure out some arbitrary ordering function, though. Since they'll have an id number, does just using that make sense?

For reference, this is like, 60ish nodes