Weird bug with a function that gives the connected component of a triangular mesh

Question

i am trying to code a function in C++ that gives me the connected components of a triangular mesh. I have a custom class that modelize a 3D triangular mesh. My goal is to obtain a std::vector<Mesh2d> with contain a connected component of my mesh in each component.

class Mesh2d{
    
    std::vector<R3>* node_ptr;
    std::vector<Elt2d> elt;
public:
    
    Mesh2d(){};
    Mesh2d(std::vector<R3>& node){}
    void Load(const string& filename){}
    void PushBack(const Elt2d& e){}
    std::vector<Elt2d>::iterator begin(){}
    std::vector<Elt2d>::iterator end(){}
    std::vector<int> Num(const int& j) const {}
    void Plot(string filename) const {}
    const Elt2d& operator[](const int& j) const {}
    std::vector<Elt2d> const GetElt() const {}
    void GetBoundary(Mesh& mesh){} 
    friend  std::vector<Elt2d> adj(Elt2d e, Mesh2d mesh){}
    friend int find_index(Elt2d e,Mesh2d mesh){}
    

    friend void DFS(int j , std::vector<bool> visited, Mesh2d boundary, std::vector<Mesh2d> ConnectedComponents, int n){
         visited[j] = true;

        std::cout<<"visited = " << visited << std::endl;
        ConnectedComponents[n].PushBack(boundary[j]);
        Elt2d e = boundary[j];
        std::vector<Elt2d> neighbor = adj(e,boundary);
        for(int i = 0; i<neighbor.size(); ++i){
         //   std::cout<<"i = " << i << std::endl;
            int p = find_index(neighbor[i], boundary);
            if(visited[p] == false){
                DFS(p, visited, boundary, ConnectedComponents, n);
            }
            
             
            
        }
    }


    std::vector<Mesh2d> Boundary(Mesh mesh){
        Mesh2d boundary;
        boundary.GetBoundary(mesh);
        std::vector<Mesh2d> ConnectedComponents;
        std::vector<bool> visited(boundary.NbElt(),false);
        std::vector<bool> True(boundary.NbElt(),true);
        int k = 0;
        for(int j = 0; j<boundary.NbElt(); ++j){
            ConnectedComponents.resize(k+1);
            std::cout<<"j =" << j << std::endl;
            Elt2d e = boundary[j];
            if(visited[j]==false){

                DFS(j, visited, boundary, ConnectedComponents,k);
                ConnectedComponents[k].PushBack(boundary[j]);
                std::cout<< "NbCC = " << ConnectedComponents.size() << std::endl;
                
            
            



            }

            ++k;
           std::cout<<"k = " << k << std::endl;
            
        }
        return ConnectedComponents;
    }
};

Where R3 and Elt2d are custom class representing 3D vectors and triangle. My problem is with the two function DFS and Boundary, i'm using a depth-first search algorithm to explore my mesh (with the triangle as nodes). But i am getting a strange bug where my vector visited changes some of its value to false. If I print my visited vector for a small mesh i get this :

visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   1   1   1   1   1   1   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   0   1   1   1   1   0   1
visited = 1 1   1   1   1   0   1   1   1   1   0   1
visited = 1 1   1   1   1   1   1   1   1   1   0   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   1   0   1   1   1   1   1   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   1   1   1   1   1   0   1
visited = 1 1   1   1   1   1   1   1   1   1   0   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   1   1   1   1   1   1   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   0   1   1   1   1   1   1
visited = 1 1   1   1   1   0   1   1   1   1   1   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   1   1   1   1   1   1   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   0   0   1   1   1   0   1   1
visited = 1 1   1   1   1   0   1   1   1   0   1   1
visited = 1 1   1   1   1   1   1   1   1   0   1   1
visited = 1 1   1   1   1   1   1   1   1   1   1   1
visited = 1 1   1   1   1   0   1   1   1   1   1   1

I have absolutely no clue why it's happening. Please keep in mind that I am a beginner with C++ and some part (or a lot) of my code can look silly. Any help would be greatly appreciated

*I have absolutely no clue why it's happening* -- 1) Use the debugger. 2) Change the access to all of your vectors by replacing `[ ]` with the `at()` function. This will check if you are going out-of-bounds within your code. 3) Post a [mcve], so that we can actually run something. — PaulMcKenzie, Dec 23 '20 at 04:56
`Mesh2d(){};` -- This failed to initialize the pointer member. Also `Mesh2d` violates the [rule of 3](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three), yet you're passing it by value to the `DFS` function. You really need to post a [mcve], because you have multiple issues with the code you have now. — PaulMcKenzie, Dec 23 '20 at 05:02
Should i post my `Elt2d` class and the whole `Mesh2d` and `Mesh` class then ? — Djekt, Dec 23 '20 at 05:23

Dmitry Kuzminov · Accepted Answer · 2020-12-23T05:37:41.653

You are passing the visited by value:

void DFS(int j, std::vector<bool> visited, Mesh2d boundary, std::vector<Mesh2d> ConnectedComponents, int n)

That means that this vector is copied each time you call the DFS function, and no values of the original vector are changed. You observe that as the values "restored" whenever you return from the function.

Pass the vector by reference instead:

void DFS(int j, std::vector<bool> &visited, Mesh2d &boundary, std::vector<Mesh2d> &ConnectedComponents, int n)

Revise the rest of the code, you never pass the "heavy" objects by referece. That is at least inefficient.

Weird bug with a function that gives the connected component of a triangular mesh

1 Answers1