CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithmunion-find
Anton Gildebrand
Anton Gildebrand

Reputation: 3707

Algorithm to find cluster of nodes that are connected

I'm working with 3d data and am provided with a list of vertices that are connected to each other. The data has the following format:

faces = [
    (0, 1, 2),
    (1, 3, 2),
    (3, 5, 6),
    (5, 7, 4),
    (10, 11, 12),
    (11, 12, 13),
    (12, 13, 14)    
]

Each item in the array consist of a 3-tuple where the number in each position represents the index of the vertices that are connected with each other. I've visualized this example in the picture to give a better understanding of how the vertices are connected.

What I'm looking for is a simple, easy to implement, algorithm that takes faces as it's input and returns the following as it's output:

[
    [0, 1, 2, 3, 4, 5, 6, 7],
    [10, 11, 12, 13, 14]
]

Example of connected vertices

Upvotes: 0

Views: 1511

Answers (3)

ravenspoint
ravenspoint

Reputation: 20472

Assume that you want to separate the vertices into sets of vertices that are all reachable from each other, but not reachable from any vertice outside the set.

Here is the pseudo code for the algorithm

LOOP
    CONSTRUCT empty current set
    SELECT V arbitrary vertex
    add V to current set
    remove V from graph
    LOOP      // while set is growing
        added_to_set = false
        LOOP V over vertices in graph
            LOOP Vset over current set
                IF Vset connected to V
                     add V to current set
                     remove V from graph
                     added_to_set = true
                     break;
        IF added_to_set == false
           break;    // the set is maximal
    ADD current set to list of sets
    IF graph has no remaining vertices
       OUTPUT sets found
       STOP

For a C++ implementation of this see code at https://github.com/JamesBremner/PathFinder2/blob/dbd6ff06edabd6a6d35d5eb10ed7972dc2d779a6/src/cPathFinder.cpp#L483

Upvotes: 0

curiouscupcake
curiouscupcake

Reputation: 1277

Surt's algorithm is one possible solution.

Since your graph is undirected and you are looking for something very simple, take a look at Breadth-first-search or Depth-first-search (they are the standard algorithms for graph theory which are very easy to understand and implement).

You basically search for every vertex that is reachable from a start vertex and label them to the same group. This process is repeated until every vertex has a group.

Upvotes: 0

Surt
Surt

Reputation: 16099

You could use union-find

I'll add a naive version of it here

untested code ahead

using face = std::array<int, 3>;
std::vector<face>  faces = {
    {0, 1, 2},
    {1, 3, 2},
    {3, 5, 6},
    {5, 7, 4},
    {10, 11, 12},
    {11, 12, 13},
    {12, 13, 14}
}

std::unordered_map<int> con;

int Find(int vert) {
  while (vert != con[very])
    vert = con[vert];
  return vert;
}

for (auto triple : faces) {
  for (int vert : triple) {
    if (!con.count(vert)) {
      con[vert]=vert; // i'm my own parent ...
    } else {
      con[vert] = Find(vert);
    }
  }
}

std::unordered_map<int, std::vector<int>> clusters

for (auto& pair : con) {
  // reduce the search path for nodes that has pair as parent.
  int cluster = Find(pair.second);
  con[pair.second] = cluster; 

  clusters[cluster].push_back(pair.first);
}

return clusters; // or convert to vector of vectors

Note without path halving and effective union this will have a horrible runtime.

Upvotes: 2

Related Questions