CODEWITHSUNDEEP
pythongraphnodesnetworkx
tafelplankje
tafelplankje

Reputation: 583

Algorithm to prune nodes in network, achieve maximum number of isolates (python networkx)

I have networks (large&small) which I need to prune until only isolates are left. I would like to maximize the number of isolates. Is there an algorithm to do this? also if its more complex ? (e.g. on the bottom there may be connected nodes as well)

consider this simple example:

import networkx as nx
G = nx.DiGraph()
G.add_edges_from([(1,2), (2,3), (2,4), (3,5), (3,6), (4,7), (4,8),
 (1,2+9), (2+9,3+9), (2+9,4+9), (3+9,5+9), (3+9,6+9), (4+9,7+9), (4+9,8+9) ])

Here, the optimal solution is deleting node 1,3,4,11 and 12.

example

Upvotes: 0

Views: 986

Answers (1)

sascha
sascha

Reputation: 33532

This sounds like you want to calculate the Maximum Independent Set (which is NP-hard for general graphs). (Wikipedia also mentions the name vertex packing).

Networkx has an approximation algorithm.

Maybe an approximation is not enough for you (and i think there is no prebuild alternative).

According to the wikipedia-link above, there is an exact algorithm available in igraph.

Also keep in mind, that this approximation-algorithm is for general graphs, so it might be very much possible, that there are better approaches for trees.

Edit: (Without checking) This SO-answer presents an algorithm for trees (and the question is a possible duplicate).

Upvotes: 1

Related Questions