CODEWITHSUNDEEP
algorithmlanguage-agnosticgraph-theory
Extrakun
Extrakun

Reputation: 19305

Find and connect sub-graphs

I have a simple Node structure (which stores the X, and Y position, and a list of nodes linked to it) and have a list of Node structures.

When the nodes are generated, each node will have an edge to up to the 3 closest nodes (by distance, number of edge is random from 1 to 3). I end up with many sub-graphs, which I need to connect to form one graph.

  1. How do I find the subgraphs?

  2. Once I have found the subgraphs, I wish to connect them together to form a connected graph. I could choose a subgraph at random, and pick the subgraph closest to it and join them. Then I will repeat step 1 to 2 again until there are no subgraphs. How do I a) find the closest subgraph, and b) decide on which 2 nodes to join such that the resulting edge is minimal?

Each node may have more than one edge.

PS. I am generating a star map with 'wormholes' linking them. Hence the edges are bidirectional. Implementation is in C#

Upvotes: 2

Views: 1022

Answers (1)

MAK
MAK

Reputation: 26586

From what I understand, your graph should be composed of clusters of points close together (which you consider as nodes that are connected to one another using short/inexpensive edges), but the clusters themselves are much farther apart (perhaps by several orders of magnitude relative to the distances between points within a cluster).

You want to create a connected graph such that the edges used are the least expensive.

A graph that is connected in such a way that the total cost of the edges in it is minimal is actually a Minimum Spanning Tree. There are several algorithms that lets you find such a tree from your graph, I would recommend Kruskal's Algorithm for your use case.

Kruskal's algorithm basically works by taking a list of all edges (in your case all n*(n-1)/2 possible connections between nodes), sorting the list in non-descending order and going from the cheapest to the most expensive edges. Initially you just take an empty graph that only has all your nodes and no edges - so it is made up of n disconnected components of a single node each. Every time you process an edge, see if adding the edge creates a cycle in your graph. If it doesn't add it to your graph, otherwise skip it. Continue until the entire list is processed. To check whether adding an edge causes a cycle, you can use a Disjoint Set data structure (as Lucasus suggested).

Kruskal's can also be used to find only the clusters, if that is what you are interested in. Just stop building the tree when you get to an edge that is too expensive to be between nearby nodes. You will get a graph composed of disconnected components that each represent a cluster formed of nodes that are close together. How expensive is too expensive is something that you will have to decide.

Upvotes: 1

Related Questions