CODEWITHSUNDEEP
pythongraphminimum-spanning-tree
Blackrunner01
Blackrunner01

Reputation: 23

Multiple Minimum Spanning Trees in a Single Graph

I am looking for an algorithm that I am not sure how to define, but the idea is to have multiple disjoint minimum spanning Trees in a single Graph.

Consider this undirected Graph, where all nodes are every node is connected to every other node in the Graph. (Too Lazy to Draw, but imagine 9 vertexes exiting/entering every node)

every node may be directed to every other node, at a cost based on direct distance

A minimum spanning tree for this Graph may appear as follows: All nodes are connected through a min-span tree

I am searching for an algorithm which can be fed with parameters such as: Maximum Vertexes pr. Node and Maximum Tree Span.

So that I for instance I tell the Algorithm: No Node may be directly connected to more than 2 other nodes, and no tree in the graph may consist of more than 3 vertexes (4 nodes) a result like this a solution. All nodes are connected to at least one other node, and the conditions as stated above the image are met

It's eventually going to be written in Python 3.0, but for now I'm just looking for some input as to how I approach this.

Upvotes: 1

Views: 830

Answers (1)

Prune
Prune

Reputation: 77827

First, please note that this is not a trivial problem. There are plenty of algorithms out there to find all minimal spanning trees -- but your inclusion of disjoint graphs turns this into more of a partitioning problem.

  • This will involve dynamic programming to reduce your path explosion.
  • Start with partitioning. For each partition, collect the possible spanning trees.
  • The product of these lists is your solution set for that partition.
  • Write a function to return all spanning trees for a given set of nodes -- memoize the result, so you don't have to regenerate the list of trees every time you change a node number.

Now for the partitions. You're getting into Grundy numbers here: all the possible ways to express a target value as the sum of possible integers. This is a well-documented DP algorithm, easy to find on Stack Overflow with "algorithm Python ..." For illustration, I'll work with only 4 nodes: QWER. The possible partitions of 4 items, with at least 2 nodes in each partition, are

4
2 2

A critical question here is whether your nodes are interchangeable -- for instance, are

QW  ER
QE  WR
QR  WE

... distinct solutions for you? If so, you now have four partitions to handle; if not, you have only two.

For each partition, generate all legal spanning trees. The 2-node solutions are trivial; the 4-node solution includes configurations (using parameter nodes abcd):

a-b-c-d (linear) a-b + c-a-d (star, with a in the center)

Again, if your nodes are interchangeable, you have only two solutions.

[(ab, bc, cd), (ab, ac, ad)]

Finally, use itertools.product to form all combinations of your partition solutions.

Does that get you moving?

Update per OP's comment

Nodes and edges are not interchangeable. Let's consider, then a 5-node system, QWERT. This has 10 distinct partitions -- each must be a 3-2 split.

QW ERT WE QRT QE WRT WR QET QR WET WT QER QT WER ER QWT RT QWE ET QWR

Each of these will follow the same configuration of solutions. For illustration, consider the first: QW | ERT. QW has only one spanner: the list of edges (one) [(Q,W)]. ERT has three: [(E,R), (R,T)], [(E,R), (E,T)], [(E,T), (R,T)]. Your collection of spanning trees is the itertools.product of these two lists.

Upvotes: 1

Related Questions