This week's book giveaway is in the Spring forum.We're giving away four copies of Modern frontends with htmx and have Wim Deblauwe on-line!See this thread for details.
Win a copy of Modern frontends with htmx this week in the Spring forum!
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Jeanne Boyarsky
• Ron McLeod
• Paul Clapham
• Liutauras Vilda
Sheriffs:
• paul wheaton
• Rob Spoor
• Devaka Cooray
Saloon Keepers:
• Stephan van Hulst
• Tim Holloway
• Carey Brown
• Frits Walraven
• Tim Moores
Bartenders:
• Mikalai Zaikin

# Graph theory anyone?

Rancher
Posts: 317
16
• Number of slices to send:
Optional 'thank-you' note:
Hello Ranchers!

I just did a problem that I apparently overestimated : Flying safely.

When I read the description, I figured it was some graph theory (albeit basic), so I draw numerous graphs with all kind of links between cities. I drafted a solution in which I checked whether a path had already been provided, and if so, included it in path collection. I put an edge case in case I had as many cities in pilots (as one is not needed and should be unemployed, poor soul).

But that solution did not went home. Instead, I just wrote that:

So my question(s):
What is the theory behind how many links you need between interconnected points?

If somebody could throw some piece of advice or facts I should be aware of, I would be thankful. After all, if one can teach a dog polymorphism...

Bartender
Posts: 5465
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
hi DJ,

long time no see! You seem to be very busy, but that is a good thing.

I had to read that assignment twice, but I think I got it. You are given N cities (vertices) and M lines of input indicating where a pilot can fly to and from (edges). So, it is an undirected Graph with N vertices and M edges. And the question is what the shortest path is between any two cities. Correct me if I'm wrong. Now, first thing what comes to mind is Dijkstra's algorithm: Dijkstra.

So, have a read and see if you agree with me!

Bartender
Posts: 1205
22
• 3
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:hi DJ,

long time no see! You seem to be very busy, but that is a good thing.

I had to read that assignment twice, but I think I got it. You are given N cities (vertices) and M lines of input indicating where a pilot can fly to and from (edges). So, it is an undirected Graph with N vertices and M edges. And the question is what the shortest path is between any two cities. Correct me if I'm wrong. Now, first thing what comes to mind is Dijkstra's algorithm: Dijkstra.

So, have a read and see if you agree with me!

That's not how I read it.  Given N vertices and M edges, I think it's asking for the minimum size of the subset of edges that connect all N verices (i.e. a spanning tree).  That seems strange to me, since the minimum number of edges in a spanning tree of a graph with N vertices is always N-1.  ...assuming the graph is indeed connected, which is guaranteed by the problem statement.

Let's look at the first test case given:
A fully connected triangle.  The spy has to trust the pilot that travels between cities 1 and 2.  Then he wants to get from city 1 to city 3.  He can't do that flying with the one pilot he trusts so far, so he has to trust a second one, for a running total of 2 so far.  Next he wants to fly from city 2 to city 3.  At first it looks like he'll have to trust a third pilot to make that flight.  But no... he could fly from 2 to 1 and then from 1 to 3 while flying only with pilots he already trusts.  So the minimum number of pilots our spy has to trust to get from any city to any city is 2 - final answer.

I think the second example would have been more fun if it was more fully connected.  i.e. instead of having the minimum of four required to connect all N=5 vertices, it should have had, say, seven or eight edges.  That would have made it "juicier".  Of course the answer still would have been been 4 when N=5.  At least it would have been more fun to draw.

Piet Souris
Bartender
Posts: 5465
212
• 1
• Number of slices to send:
Optional 'thank-you' note:
Hi Ryan,

I gave it another read, and you are absolutely right. So I think the difficulty lies in coming up with the idea of such a minimal spanning tree. And certainly given the time limit of 1 second, I think this exercise is pretty hard if you've never heard of these things.

Saloon Keeper
Posts: 27720
196
• 1
• Number of slices to send:
Optional 'thank-you' note:
Yeah, that sounds like Shortest Spanning Tree, and aside from Djikstra, my other primary reference would be my MIT algorithms book, which has quite a bit of graph theory in it.

Then again, superficially I can't tell it from the classic Travelling Salesman problem and Wikipedia has a very nice article on that, I see.

NP-hard, linear programming.

D.J. Quavern
Rancher
Posts: 317
16
• Number of slices to send:
Optional 'thank-you' note:
Thank you everyone, that was exactly what I was talking about: just by looking at the problem, you could determine it was a minimal spanning graph and see that the solution was N-1 directly. I had no idea what I was looking at, except a badly formulated Cold War movie. I am the proud winner of classical problems with Python and I hope it will help me at least to have an idea of the underlying theoretical world under programming problems. I had a look at the minimal spanning tree: so this is the one we have, but how do you deal with them when there are no weights on the branches? I also looked at Dijkstra algorithm: how can it find the most optimal route when it can't see the path n+2? I mean what if it choses the cheapest weight (2), but the next-one is extra salty (45)? Maybe it's not the point and it's a very stupid question though.

@Piet:
Yes! I am on holidays : I just have a web-development course -my questions also end up at the Ranch...-, but apart that, I am free. So I hang here and enjoy the company of nice people that give me golden advice and help     !

@Tim: Uh, NP-hard? Wiki has a funny definition : "the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"
I saw there was atraveling salesman, it is extra-hard.

Screenshot-2019-07-09-at-07.10.26.png

Tim Holloway
Saloon Keeper
Posts: 27720
196
• Number of slices to send:
Optional 'thank-you' note:
Yup, as I said, this problem looks very much like the classic Traveling Salesman problem, just replacing time (or cost) of travel with danger level as the node-to-node weights.

Traveling Salesman is a Computer Science classic, like the Dining Philosophers, but it has very definite uses in the real world and anyone who can solve it to run in Polynomial time will instantly be adored by UPS, Fedex, DHL, and many others.

In fact, TS isn't merely a classic CompSci problem, it's a classic problem in Mathematics. "Linear Programming" is a mathematical term, not a software term.

You can obviously solve this problem by brute-force running all possible paths, but that's a solution that gets exponentially slower and more expensive as the number of vertexes increase. Mathematicians have come up with some shortcuts, but they all suffer from the flaw of being fuzzy result sets rather than returning the One True Path. Still, fuzzy results are better than none.

Master Rancher
Posts: 4764
71
• 1
• Number of slices to send:
Optional 'thank-you' note:

D.J. Quavern wrote:I had a look at the minimal spanning tree: so this is the one we have, but how do you deal with them when there are no weights on the branches?

"No weights" often is really "equal weights".  The thing we are asked to minimize here is the number of pilots, which is also the number of routes, or number of selected edges in the graph  We know that ever time we select a pilot/edge, the cost of our solution is 1 pilot more than another solution without that pilot.  But all pilots have equal cost.  So we can just say that all pilots have equal weight, and for simplicity, we let that weight be 1.  So, the cost of each edge in the graph is 1.  If we were given a table that included different salaries for different pilots, then those might be our different weights - but for the given problem, all pilots are equal.

D.J. Quavern wrote: I also looked at Dijkstra algorithm: how can it find the most optimal route when it can't see the path n+2? I mean what if it choses the cheapest weight (2), but the next-one is extra salty (45)? Maybe it's not the point and it's a very stupid question though.

Not stupid, no, it's a good question.  A key point is that with Dijkstra, at step n you aren't committing to any one solution yet - you are handling *all* possible solutions, of length n.  Or of a particular maximum cost.  Well, not really *all* of the solutions, because you are weeding out the ones that waste time getting to the edge of your graph.  But you are keeping a set of all the best solutions that would reach the current edge of the search area.  Without committing to any one point on the edge, yet.

I don't think Dijkstra really applies to your original problem, though it's similar in some ways.  Dijkstra finds the best way to connect *two* particular nodes.  And one of those nodes is always in the center of your search.  (Or, you have two expanding search regions, and each node is in the center of one of them.)  SST finds the best way to make sure *all* nodes are connected.  Traveling salesman is much more similar, as the salesman needs to travel through all the cities/nodes.

D.J. Quavern
Rancher
Posts: 317
16
• Number of slices to send:
Optional 'thank-you' note:
Hello!
Thank you for all the answers!

I will not risk the traveling salesman right now, the difficulty level is way to high for where I am right now! I saw the dining philosophers in class, as an example!

A key point is that with Dijkstra, at step n you aren't committing to any one solution yet - you are handling *all* possible solutions, of length n.  Or of a particular maximum cost.  Well, not really *all* of the solutions, because you are weeding out the ones that waste time getting to the edge of your graph.  But you are keeping a set of all the best solutions that would reach the current edge of the search area.  Without committing to any one point on the edge, yet.

What do you mean? Do the algorithm keep track of all the paths in an array and propose the cheapest one at the end (minus those that go in the walls)?

Saloon Keeper
Posts: 15455
363
• 1
• Number of slices to send:
Optional 'thank-you' note:
Let's quickly make a distinction between "path length" and "distance". I don't know if these are good names for these concepts, I just chose to name them that way in THIS post only.

Path length is the number of edges between two nodes.

Distance is the sum of the weights of each edge between two nodes. So the distance when traveling path "A -> B -> C" may be smaller than when travelling "A -> C" if the weight of the edge "A -> C" is large.

Dijkstra's algorithm keeps track of the optimal paths (least distance) from a starting node to ALL nodes with a path of length at most N. It doesn't yet commit to the solutions for each visited node, because a path of length N+1, or N+2 or more may have a smaller distance. When at path length N+1 it finds a path with less distance to an already visited node, it will update the optimal path leading to that already visited node.

D.J. Quavern wrote:Uh, NP-hard? Wiki has a funny definition : "the defining property of a class of problems that are, informally, "at least as hard as the hardest problems in NP"

Let's explain this in another funny way: If aliens come down to earth and hand us a small machine that does nothing else but provide answers to the traveling salesman problem instantaneously, we can build it into our computer processors to make them able to quickly provide an answer to EVERY OTHER NP-problem, even if they seem completely unrelated to the traveling salesman problem. For instance, if you want to decrypt a secret message without knowing the key, you can write a program that states the decryption operation in terms of the traveling salesman problem, and the computer will be able to provide you the decrypted message very fast.

Stephan van Hulst
Saloon Keeper
Posts: 15455
363
• 1
• Number of slices to send:
Optional 'thank-you' note:

D.J. Quavern wrote:(and about Dijkstra... I am almost with you on that one. Just need to understand how it "stores" the possible solutions!)

I just implemented the algorithm in Java:

As you can see, I use the same type to keep track of the definite shortest paths (shortestPaths) and the best found paths so far (nodesToVisit): A map of the key of the destination to a path leading there. An instance of Path contains a list of edges and can calculate the total weight of the edges in the path.

D.J. Quavern
Rancher
Posts: 317
16
• Number of slices to send:
Optional 'thank-you' note:
Oups, I managed to miss your last post Stephan!

I will come back to it later, I just got the book grokking algorithms, can't recommend it warmly enough . Implemented a BFS search this morning and will try myself at implementing Dijkstra tomorrow morning. So I will be back!

Tim Holloway
Saloon Keeper
Posts: 27720
196
• 1
• Number of slices to send:
Optional 'thank-you' note:
As it happens, I just ran across a related problem/solution. When designing electronic circuit boards (PCBs), the object of the game is to run "wires" (traces) between the electronic components laid out on the boards - transistors, resistors, capacitors and so forth.

However, it's not as easy as you might think. The traces are limited mostly to 2 dimensions, and many components cannot be directly connected without crossing wires.

The solution to that problem is to temporarily jump into the third dimension and run wiring on the other side of the PCB. In ancient times, typically only one side was etched with wiring traces and to wire the other side, you had to literally punch holes through the board and connect the crossovers with actual wire. These days, factories simply etch both sides of the board and make the cross-connection via a metal plug through the hole (known as a "via").

Vias are undesirable. They are less mechanically secure than a simple trace run and more likely to introduce funny electrical effects, especially at high frequencies. And they don't always cure everything. Really complex PCBs such as computer motherboards actually stack 2 double-sided PCBs to get 4 layers of wiring. But that's a bit much for most of us - although if you're so inclined I can direct you to some good design software (it's open-source and free).

So it's a bit of a game to design a PCB where the number of vias is kept to a minimum and the traces are kept as short and simple as possible.

Many people think that the only real way to do this is by hand, but automation is everywhere, and there are programs available to attempt optimal routing automatically. One such program is FreeRouting by Alfons Wirtz and it's in Java, if you want to see how it's done. As it is a visual program you can actually watch it run as it lays down traces, decides it made a bad move, rips them up and lays down new ones, making multiple passes until it is satisfied that it has done the best job reasonably possible.

And, incidentally, it reminded me that there are 2 other problems of this same general class: the "Bridges of Konigsberg" problem, where the graph overlays 7 islands connected by bridges where you have to visit each island crossing each bridge only once, and "map coloring" problems, where you have a limited number of colors and a geographic map of, say, post-Roman Europe where you have lots of little countries and you want to color each one such that it is a distinct color - no two adjacent countries being the same color.

D.J. Quavern
Rancher
Posts: 317
16
• Number of slices to send:
Optional 'thank-you' note:
I'm nowhere near designing such complicated systems yet, so you'll have to read my baby steps

 Did you see how Paul cut 87% off of his electric heat bill with 82 watts of micro heaters?