search

networkx / nx-guides

Examples and Jupyter Notebooks about NetworkX
https://networkx.org/nx-guides/
Creative Commons Zero v1.0 Universal
185 stars 105 forks source link

Notebook on minimum spanning tree using Prim's algorithm #74

Open NikitaSharma1 opened 2 years ago

NikitaSharma1 commented 2 years ago

@MridulS @rossbar can you please have a look at this notebook ? Also, should I add Kruskal's algorithm in this notebook only or make a separate notebook for it?

NikitaSharma1 commented 2 years ago

It was passing the checks before but now It's throwing error... idk why

MridulS commented 2 years ago

No worries, this is broken because of https://github.com/networkx/nx-guides/pull/76 Should be fixed once that is merged in.

NikitaSharma1 commented 2 years ago

@MridulS Thank you!!

NikitaSharma1 commented 2 years ago

@rossbar I totally agree with your point. I was thinking of making it as simple as possible with all situations covered, so, maybe that's why it slipped out of my mind. Would you suggest improvising the example and replacing the optimal route problem with a generalized example, like points A, B, C, D, and E instead of cities, or adding more edges to the example to make it a complete graph?

dschult commented 2 years ago

The route finding problem is the “traveling salesman problem”. And it shouldn’t be a tree. It finds the best path. A tree is rarely a path. But here’s a better setting that makes sense from a spanning tree perspective. Suppose you are trying to lay out the pipes for a gas distribution system. You can connect each city to other cities, but you want to find the tree that minimizes the total pipe length. So, unlike our traveler who has to continue from wherever their last position was, the tree can be extended from any point on the already built portion of the tree.

There must be other settings for the spanning trees — and I’m sure some of them do not start with a complete graph. But this gas pipeline tree setting does still have that complete graph information. I just wanted to separate the “best route” problem from the “best tree” problem.

Can someone come up with a setting that doesn’t start with a complete graph?

dschult commented 2 years ago

Wikipedia gives some examples that might help.
suppose you are laying down a new electric grid for a town. It is only feasible to build the route along existing roads, so you start with a road network. Then you want to build the least expensive tree of wires that serves all the customers. Of course in reality, you’d like redundancy to avoid outages. But the minimum spanning tree is a good starting place for laying down wire. And the restriction that you only put wire along roads means you start with a network rather than a complete graph. ;)

PurviChaurasia commented 1 year ago

Hi, I opened a issue regarding this #101 I will take into account all suggestions given here and will be constructing the notebook, thanks!

rossbar commented 1 year ago

@NikitaSharma1 are you still planning to work on this? If so, I think the place to (re)start would be by updating the motivating example per feedback from the previous review!