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

[Paul McKenzie]

In your new code, you have a small issue here:

 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; }
      }

You don't check to see if temp_copy is empty. Your loop will go haywire since you subtract 1 from 0.

Regards,

Paul McKenzie

[Paul McKenzie]

Try this:

#include <vector>
#include <algorithm>

typedef std::vector<int> IntVect;
typedef std::vector<IntVect> IntVect2D;

bool CopyVect(const IntVect& vect)
{
    if ( vect.empty() )
        return true;
    int last_vertex_in_path = vect.back();
    IntVect::const_iterator last = vect.end();
    --last;  
    IntVect::const_iterator it = std::find(vect.begin(), last, last_vertex_in_path);
    if ( it != last)
        return false;
    return true;
}

int main()
{
    // Test data
    int data1[] = {17, 19, 21};
    int data2[] = {17, 19, 20};

    // Here is our 2d vector
    IntVect2D new_set_of_paths(2);

    // Set our test data
    new_set_of_paths[0] = IntVect(data1, data1 + 3);
    new_set_of_paths[1] = IntVect(data2, data2 + 3);

    new_set_of_paths.erase(
        std::remove_if(new_set_of_paths.begin(), new_set_of_paths.end(), CopyVect), new_set_of_paths.end());
}

The CopyVect function should do the same thing you're doing now.

1) It gets the last item in the vector.

2) It searches for the last element in the vector, up until the item before the last one.

3) Returns true of false, depending on whether the item is found or not.

Then in the main() program, the new_set_of_paths is trimmed of the removed vectors.

Regards,

Paul McKenzie

[LMHmedchem]

I think that possibly the return values should be the opposite,

bool CopyVect(const IntVect& vect)
{
    if ( vect.empty() )
        return true;
    int last_vertex_in_path = vect.back();
    IntVect::const_iterator last = vect.end();
    --last;  
    IntVect::const_iterator it = std::find(vect.begin(), last, last_vertex_in_path);
    if ( it != last)
//        return false;
//    return true;
        return true;
    return false;
}

so that the function returns true if a match is found. It seems to work properly if I switch those bool values. Then I get the following output,

path1[0] 1,2
path1[1] 1,3

path2[0] 1,2,4
path2[1] 1,2,5
path2[2] 1,3,11
path2[3] 1,3,12

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

path4[0] 1,2,4,6,5
path4[1] 1,2,5,6,4
path4[2] 1,2,5,7,8
path4[3] 1,2,5,7,9
path4[4] 1,2,5,7,10
path4[5] 1,3,11,13,14
path4[6] 1,3,11,13,15
path4[7] 1,3,11,13,16
path4[8] 1,3,12,11,13

path5[0] 1,2,4,6,5,7
path5[1] 1,2,5,7,10,21
path5[2] 1,2,5,7,10,22
path5[3] 1,3,11,13,16,17
path5[4] 1,3,11,13,16,18
path5[5] 1,3,12,11,13,14
path5[6] 1,3,12,11,13,15
path5[7] 1,3,12,11,13,16

In your new code, you have a small issue here:

 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; }
      }

You don't check to see if temp_copy is empty. Your loop will go haywire since you subtract 1 from 0.

I don't think it is possible for temp_copy to be empty, but this code is being replaced by the erase code you posted. This is exactly why I would like to get away from endless looping and make more use of algorithms, which are less susceptible to going out of bounds and such.

Do you think there is anything else in the algorithm that is poorly formed? I understand that may be a "you asked for it" kind of question.

LMHmedchem

[Paul McKenzie]

I think that possibly the return values should be the opposite,

bool CopyVect(const IntVect& vect)
{
    if ( vect.empty() )
        return true;
    int last_vertex_in_path = vect.back();
    IntVect::const_iterator last = vect.end();
    --last;  
    IntVect::const_iterator it = std::find(vect.begin(), last, last_vertex_in_path);
    if ( it != last)
//        return false;
//    return true;
        return true;
    return false;
}

so that the function returns true if a match is found. It seems to work properly if I switch those bool values. Then I get the following output

OK. As long as the function does the correct thing, then this should work.

I don't think it is possible for temp_copy to be empty,

You should always check for bad data, and subtracting 1 from the end() iterator and then blowing up on an empty container is one runtime error that happens a lot, but can be avoided. So I highly suggest that you check for an empty container somewhere, whether it is in this function or before.

Do you think there is anything else in the algorithm that is poorly formed? I understand that may be a "you asked for it" kind of question.

The thing is, I didn't really study your code that hard except to see what loops could be replaced with algorithms. This is a test case of me not knowing everything that you want to accomplish, and by just looking at your loops, writing the equivalent using the STL algorithms.

BTW, this is the final code:

bool CopyVect(const IntVect& vect)
{
    return vect.empty() // return true if container is empty 
                     ||           // OR
               // return true if last element cannot be found in the range [0 ... n-1)
               (std::find(vect.begin(), vect.end()-1, vect.back()) != vect.end()-1); 
}
//...
 new_set_of_paths.erase(
        std::remove_if(new_set_of_paths.begin(), new_set_of_paths.end(), CopyVect), new_set_of_paths.end());

Regards,

Paul McKenzie

[JohnW@Wessex]

Could you perhaps store the paths in a std::map with the path id("1,2,4" or 124) as a key? That way you could never have more than one instance of a path.

[gao6530]

Develop Your First Metro Application