adding to vector of vector<int>, check if element already present

[LMHmedchem]

Well it seems I explained this incorrectly. The above erase code you posted looks like it searches through the entire vec<vec> for any sub vector with the number 21 in it, which is what I said I needed.

new_set_of_paths.erase(std::remove_if(new_set_of_paths.begin(),
                                      new_set_of_paths.end(),
                                      PathRemover(21)),
                                      new_set_of_paths.end());

The fact is that a repeat number will be in more than one place and in some cases, the vector shouldn't be deleted.

I am working on this graph,
graph_test1.jpg

I am creating and storing paths of length 1-5, starting at vertex 1 (or any specified vertex). The number of path1 paths emanating from a given vertex is equal to the number of neighbors, which is 2 in this case (simple delta = 2). A path1 is one edge connecting two vertices, for anyone reading this who has never worked with graph theory.

There are two path1 paths from vertex 1
1,2
1,3

To build path2 paths, I use each of the path1s as a base. Looking at the last element in the first path1, vertex 2 has a delta of 3, so three paths can branch from v2.

The three neighbors of v2 are 1,4,5.

To build path2, I create delta copies of path1 1,2
1,2
1,2
1,2

and add one neighbor of 2 (last element in the path1 base) to each copy,
1,2,1
1,2,4
1,2,5

then I loop to the second path1 path
1,3

vertex 3 also has three neighbors (1,11,12), so I add three copies of 1,3
1,2,1
1,2,4
1,2,5
1,3
1,3
1,3

and then one neighbor of 3 to each copy,
1,2,1
1,2,4
1,2,5
1,3,1
1,3,11
1,3,12

these path2 paths will form the base path for path3 subgraphs, etc

The problem is that you don't want repeat elements in a path. Repeats mean that the path is moving backwards, or through a circuit, and neither is a path by definition or interest. This means that,
1,2,1
1,3,1

need to be deleted, or never created in the first place.

My thought was that, before adding the neighbor, I would scan the vector to see if it was already there, if not, add it, if it is, delete the vector. It may be simpler to wait until all of the paths of a given length have been enumerated and then loop through the vec<vec> checking the last element against the earlier ones.

I setup a very crude double loop to do this, and the algorithm does work now.

   vector<int> temp_copy;
   bool copy;

   for(i=0; i<new_set_of_paths.size(); i++) {
      copy = true;
      temp_copy = new_set_of_paths[i];
      last_vertex_in_path = temp_copy.back();
      for(j=0; j<temp_copy.size()-1; j++) {
         if(last_vertex_in_path == temp_copy[j]) { copy = false; }
      }
      if(copy == true) { copy_vector.push_back(temp_copy); }
      temp_copy.clear();
   }
   new_set_of_paths = copy_vector;

I get the expected,
path2[0] 1,2,4
path2[1] 1,2,5
path2[2] 1,3,11
path2[3] 1,3,12

I have tired up to path5 for a number of start vertices and it seems to work fine.

I tried modifying the erase code you posted to check the last element against the others, but I guess I'm not clear enough on how it works. Repeat elements can occur anywhere in the vector, so the entire vector must be scanned. For example,
1,3,12,11,3

I have attached the src code for this. It's a bit long, but everything interesting is in the first 222 lines. Everything after that is just loading the graph and the starting vertex.

So far, the algorithm works, is fast, and I don't see much of anywhere it could blow up, but I would really like to learn how to better make use of algorithms and not do so much for() double looping everywhere.

LMHmedchem