sorting a vector

[acosgaya]

Hi,

I'd like some help to do the following:

I have an stl::vector, with elements of this form (I'm showing only the basic operations in the class)

class Edge {

    NodeID source() const {return _source;}

    NodeID target() const {return _target;}

    EdgeWeight weight() const {return _weight;}

   ... etc

}

a small example of a dataset:
(source, target) weight
(3, 0) 4
(6, 0) 6
(7, 0) 5
(3, 1) 2
(4, 2) 3
(0, 3) 4
(1, 3) 2
(2, 4) 3
(5, 4) 4
(4, 5) 4
(6, 5) 4
(0, 6) 6
(5, 6) 4
(0, 7) 5
(9, 7) 3
(9, 8) 3
(7, 9) 3
(8, 9) 3

I want to sort it so that adjacent elements correspond to the same values for source and target (just reversed), and also by decreasing weight. This is how it should look like.
(6, 0) 6
(0, 6) 6
(7, 0) 5
(0, 7) 5
(3, 0) 4
(0, 3) 4
(4, 5) 4
(5, 4) 4
(6, 5) 4
(5, 6) 4
(4, 2) 3
(2, 4) 3
(9, 7) 3
(7, 9) 3
(9, 8) 3
(8, 9) 3
(3, 1) 2
(1, 3) 2

I am trying this function for my stl::sort:

class segmentOrdering  {
public:
  bool operator() (const Edge &e1, const Edge &e2) const
  {
    
    if ( std::min(e1.source(), e1.target()) < std::min(e2.source(), e2.target()) ){
      return true;
    }

    if ( std::max(e1.source(), e1.target()) < std::max(e2.source(), e2.target()) )  
      return true;
    
    return false;
  }

which works (not in all cases apparently) for sorting by the adjacent element as mentioned before, but I don't know hot to add a way to sort it also by weight.

Can you please tell what's wrong with my sorting function, and how could I fix it and add the weight comparison as well?

thanks a lot

[Codeplug]

Let's say you have members a, b, and c - and you want to sort first by a, then by b, and then by c. The code would look something like this:

// lhs and rhs are the objects being compared
// lhs = left hand side
// rhs = right hand side

if (lhs.a < rhs.a)
    return true
else if (lhs.a > rhs.a)
    return false
else
{
    if (lhs.b < rhs.b)
        return true
    else if (lhs.b > rhs.b)
        return false
    else
    {
        if (lhs.c < rhs.c)
            return true
        else if (lhs.c > rhs.c)
            return false
     }
}

return false

gg

[anon]

I'm not sure about the rest but you probably want to compare weight first and do the rest of the comparisons only if weights are equal.

[acosgaya]

tks for the replies,

I did this and seems to be working:

  bool operator() (const Edge &e1, const Edge &e2) const
  {
    
    if (e1.weight() > e2.weight()) 
      return true;
    else if (e1.weight() < e2.weight()) 
      return false;    
    else{
      if ( std::min(e1.source(), e1.target()) < std::min(e2.source(), e2.target()) )
        return true;
      else if ( std::min(e1.source(), e1.target()) > std::min(e2.source(), e2.target()) )
        return false;
      else{
        if ( std::max(e1.source(), e1.target()) < std::max(e2.source(), e2.target()) )  
          return true;
        else if ( std::max(e1.source(), e1.target()) > std::max(e2.source(), e2.target()) ) 
          return false;
      }
    }
    return false;
  }