CODEWITHSUNDEEP
c++algorithm
ozdm
ozdm

Reputation: 153

Connected Components with Periodic Boundary Conditions

Normally to find the connected components on a set of points, I build a graph from the points that are placed in 2 dimensional Euclidean space where the edges are determined with thresholding. Namely, if the distance between two points is closer than a predetermined cut-off radius, then I consider them as neighbors. Then I do a depth-first search on this graph to determine the connected components.

The problem with this approach is I have to use thresholding to build the graph in the first place. I am not a computer scientist, so I never took an algorithms class. I would like to know if there is an algorithm with which I can find nearest neighbors or connected components without building the edges with thresholding? The main issue that makes thresholding so preferable is the fact that this box is periodic. That's why googling alone didn't help me much.

My code for this look like this:

// +++++
// Graph
// +++++

// ( Note that edges are lines connecting nodes or vertices )

class Graph
{

public:
    Graph() {}
    ~Graph() {}
    void setNumNodes( int nds );
    int getNumNodes() { return numNodes; }
    void addEdge( int nd_idx, set<int> dest );
    map<int,set<int> > edges; // [node, destination]
    void setThreshold( double cutoff, double carpan );
    double getThreshold() { return threshold; }

private:
    int numNodes;
    double threshold;

};

void Graph::setNumNodes( int nds ){
    numNodes = nds;
}

void Graph::addEdge( int nd_idx, set<int> dest ){
    edges.insert( pair<int,set<int> >( nd_idx, dest ) );
}

void Graph::setThreshold( double cutoff, double carpan ){
    threshold = 2*R + carpan*cutoff;
}


// +++++

// Function for depth-first search from a starting node
int dfsFromNode( Graph& graph, int i, stack<int>& S, vector<bool>& visited ){

    int connected_comp = 0;

    // Add the node to the stack
    S.push( i );

    // While there are nodes that are not visited
    // (so as long as stack is not empty ..)
    while( !S.empty() ){

        // Remove the top of the stack (backtracking process)
        S.pop();
        if( !visited[i] ){
            visited[i] = true;
            connected_comp++;
            set<int> neighbors;
            neighbors = graph.edges[i];
            for( auto j: neighbors ){
                i = j;
                S.push( i );
            }
        } // if the node is visited before, get out

    } // while loop to check if the stack is empty or not

    return connected_comp;

}

edit:

To reiterate the question, how can I find the nearest neighbors or connected components without doing thresholding in periodic boundary settings?

Upvotes: 1

Views: 615

Answers (1)

melampyge
melampyge

Reputation: 143

For finding connected components, you can use kd-trees. A k-d tree, (abbrev. k-dimensional tree) is an algorithm in which you split your data points into two alternating between orthogonal directions in each degrees of freedom. I find the following link quite useful for explanation.

Specifically, in the case of periodic boundary conditions, you can just ghost/image particles outside of the primary box and build the kd-tree including these particles.

Upvotes: 1

Related Questions