2

I want to find minimum vertices that connect certain vertices to each other. For example, assume list of edges is connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)] and the graph will be like below:

enter image description here

Then I want to know how to connect vertices 2, 4, 5 together with minimum number of vertices. Which in this case is vertex 0.

Therefore the output should be [0,2,4,5] which means 4 vertices needed. I tried to implement the algorithm with brute force since there would be more complicates cases but I am not sure how to find the best answer from all possible combinations.

from itertools import combinations

verticis = [0,1,2,3,4,5]
connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)]
key = [2,4,5]

i, j = 2, len(verticis)
res1 = [com for sub in range(j) for com in combinations(verticis, sub + 1)] 
res2 = [com for sub in range(i - 1) for com in combinations(verticis, sub + 1)] 
res = list(set(res1) - set(res2))
  • 4
    This is not shortest path problem. I want to connect those 3 nodes to each other with minimum possible number of nodes. –  Nov 28 '20 at 18:32
  • Very interesting question! If you don't find a satisfying answer here, perhaps you could try [the computer science stackexchange](https://cs.stackexchange.com). – Stef Nov 28 '20 at 18:34
  • Related questions: [pyhon: minimum connected subgraph containing a given set of nodes](https://stackoverflow.com/questions/3975763/minimum-connected-subgraph-containing-a-given-set-of-nodes), [igraph: given a list of vertices, find the smallest connected subgraph](https://stackoverflow.com/questions/31718224/igraph-given-a-list-of-vertices-find-the-smallest-connected-subgraph), [R, igraph: extract a connected subgraph from a subset of vertices](https://stackoverflow.com/questions/23367765/extract-a-connected-subgraph-from-a-subset-of-vertices-with-igraph). – Stef Nov 28 '20 at 18:38
  • See also: [Wikipedia: minimum Steiner tree problem](https://en.wikipedia.org/wiki/Steiner_tree_problem) – Stef Nov 28 '20 at 18:39
  • What do you mean by `Therefore the output should be [0,2,4,5] which means 4 vertices needed.`. I understand the line before that but this one confuses me a bit. – Akshay Sehgal Nov 28 '20 at 18:43
  • It means node 0 can connect nodes 2, 4 and 5 to each other. I have this combination [0,2,4,5] in res but I am not sure how can I pick it as a best answer. –  Nov 28 '20 at 18:46
  • 1
    Suggestion: Write a function `is_connected` that tells you whether a graph is connected or not. Then, using vertices which are not in your selected set [2, 4, 5], enumerate in order: all sets of 0 vertices; all sets of 1 vertices; all sets of 2 vertices; etc (possibly using functions from module `itertools` to help you). Then, for every set of vertices, generate the set of edges which use only vertices from this set plus vertices from your set [2, 4, 5]. Use function `is_connected` to tell you whether this subgraph is connected or not. If it is connected, halt and return this set of vertices. – Stef Nov 28 '20 at 19:06
  • What do you mean by all sets of 0 vertices...? –  Nov 28 '20 at 19:17
  • Well, there is the empty set :) I'm only talking about "extra" vertices, vertices not in your set of interest, so the empty set represents "don't add any vertices and check if the induced subgraph is already connected" – Stef Nov 29 '20 at 02:03

0 Answers0