Re: Why aren't "tri-valent" comparison functions used in the standard library?

* Rupert Swarbrick:


Even though I have not denied anything (yet), I must confess that this
is too subtle for me to grok. I guess that some heavy study of wikipedia
might clear up at least /what/ is being discussed. Hint?


Well, there are at least two flies in the ointment:

1) Formally, the operator< for the std::sort function must have this
property: let eq(a,b) = !(a<b) && !(b<a), then by C++11 ?25.4/4 this eq
must be transitive such that eq(a,b) and eq(b,c) implies eq(a,c), and
for a topological sort of edge(x, a), edge(x, b) and edge(a, c) we have
that neither a<b nor b<a is true, so eq(a,b), and likewise we have
eq(b,c), but it's then not true that eq(a,c): they're <-comparable.

2) As far as I can see defining a suitable operator< so that sort can
sort topologically, makes for some serious inefficiency.


For the in-practice, which I think is UB for both operator<-based
std::sort and compare()-based qsort, I fail to make the sorting fail...

So, I don't understand that statement, especially the "obviously".

However, I have no idea *why the sorting works* in my example code below.

Maybe it's just the example graph, which I took from the Wikipedia
article, <url: http://en.wikipedia.org/wiki/Topological_sorting>?

Or, maybe, there's some logical explanation so that any "reasonable"
implementation of std::sort and qsort must work for topological sorting?

[UB-code]
#include <algorithm> // std::sort, std::random_shuffle, std::find
#include <iostream> // std::cout, std::endl
#include <map> // std::multimap
#include <set> // std::set
#include <search.h> // qsort
#include <string> // string
#include <utility> // std::move
#include <vector> // std::vector
using namespace std;

#define ITEMS_OF( c ) c.begin(), c.end()
template< class T > using Type_ = T;

struct Vertex
{
      int index;

      struct Is_in_value_order
      {
          // `operator<` except in name, to be sure isn't inadvertently
used.
          auto operator()( Vertex const a, Vertex const b ) const
              -> bool
          { return (a.index < b.index); }
      };
};

typedef set<Vertex, Vertex::Is_in_value_order> Vertex_set;
typedef map<Vertex, Vertex_set, Vertex::Is_in_value_order> Vertex_set_map;

struct Edge
{
      Vertex start, end;
};

namespace g{
      // Graph figure at
http://en.wikipedia.org/wiki/Topological_sorting#Examples
      vector<Edge> const edges =
      {
          Edge{7, 11}, Edge{7, 8}, Edge{5, 11}, Edge{3, 8},
   Edge{3, 10},
          Edge{11, 2}, Edge{11, 9}, Edge{11, 10}, Edge{8, 9}
      };

      Vertex_set const vertices = [&]() -> Vertex_set
      {
          Vertex_set result;
          for( auto e : edges ) { result.insert( e.start );
result.insert( e.end ); }
          return move( result );
      }();

      Vertex_set_map parents = [&]() -> Vertex_set_map
      {
          Vertex_set_map result;
          for( auto const e : edges ) { result[e.end].insert( e.start ); }
          return move( result );
      }();
} // namespace g

void display( vector<Vertex> const& v )
{
      for( auto it = v.begin(); it != v.end(); ++it )
      { cout << (it != v.begin()? ", " : "") << it->index; }
      cout << endl;
}

struct Is_in_topological_order
{
      // An `operator<` except in name.
      auto operator()( Vertex const a, Vertex const b ) const
          -> bool
      {
          auto const& parents = g::parents[b];
          if( parents.count( a ) > 0 ) { return true; }
          for( auto const v : parents )
          {
              if( Is_in_topological_order()( a, v ) ) { return true; }
          }
          return false;
      }
};

auto is_topologically_ordered( vector<Vertex> const& v )
      -> bool
{
      bool first_iteration = true;
      Vertex a{}, b{};
      for( auto vertex : v )
      {
          a = b; b = vertex;
          if( !first_iteration )
          {
              if( Is_in_topological_order()( b, a ) ) { return false; }
          }
          first_iteration = false;
      }
      return true;
}

void test_cpp_sort( vector<Vertex> const& vertices )
{
      auto v = vertices;
      cout << "Original vertex order: " << endl;
      display( v );

      sort( ITEMS_OF( v ), Is_in_topological_order() );

      cout << "Topologically sorted using `std::sort`:" << endl;
      display( v );
      cout << "Is sorted = " << is_topologically_ordered( v ) << endl;
      cout << "Swapped first and last vertex:" << endl;
      swap( v.front(), v.back() );
      display( v );
      cout << "Is sorted = " << is_topologically_ordered( v ) << endl;
}

void test_c_qsort( vector<Vertex> const& vertices )
{
      auto v = vertices;
      cout << "Original vertex order: " << endl;
      display( v );

      qsort( &v[0], v.size(), sizeof( Vertex ),
      []( void const* void_a, void const* void_b ) -> int
          {
              auto& a = *reinterpret_cast<Vertex const*>( void_a );
              auto& b = *reinterpret_cast<Vertex const*>( void_b );
              return (0?0
                  : Is_in_topological_order()( a, b )? -1
                  : Is_in_topological_order()( b, a )? +1
                  : 0 );
          } );

      cout << "Topologically sorted using `qsort`:" << endl;
      display( v );
      cout << "Is sorted = " << is_topologically_ordered( v ) << endl;
      cout << "Swapped first and last vertex:" << endl;
      swap( v.front(), v.back() );
      display( v );
      cout << "Is sorted = " << is_topologically_ordered( v ) << endl;
}

auto main() -> int
{
      vector<Vertex> vertices( ITEMS_OF( g::vertices ) );

      cout << boolalpha;

      random_shuffle( ITEMS_OF( vertices ) );
      cout << "Shuffled: " << endl;
      display( vertices ); cout << endl;
      test_cpp_sort( vertices ); cout << endl;
      test_c_qsort( vertices ); cout << endl;

      for( int i = 1; i <= 7; ++i )
      {
          cout << endl;
          cout << i << " " << string( 76, '-' ) << endl;
          random_shuffle( ITEMS_OF( vertices ) );
          test_c_qsort( vertices ); cout << endl;
      }
}
[/UB-code]

[output]
Shuffled:
8, 3, 10, 5, 2, 9, 11, 7

Original vertex order:
8, 3, 10, 5, 2, 9, 11, 7
Topologically sorted using `std::sort`:
3, 8, 5, 7, 11, 10, 2, 9
Is sorted = true
Swapped first and last vertex:
9, 8, 5, 7, 11, 10, 2, 3
Is sorted = false

Original vertex order:
8, 3, 10, 5, 2, 9, 11, 7
Topologically sorted using `qsort`:
3, 7, 5, 11, 2, 10, 8, 9
Is sorted = true
Swapped first and last vertex:
9, 7, 5, 11, 2, 10, 8, 3
Is sorted = false

1
----------------------------------------------------------------------------
Original vertex order:
2, 10, 8, 7, 5, 9, 11, 3
Topologically sorted using `qsort`:
5, 7, 11, 3, 8, 9, 10, 2
Is sorted = true
Swapped first and last vertex:
2, 7, 11, 3, 8, 9, 10, 5
Is sorted = false

2
----------------------------------------------------------------------------
Original vertex order:
2, 10, 5, 9, 11, 7, 8, 3
Topologically sorted using `qsort`:
5, 7, 11, 3, 8, 9, 10, 2
Is sorted = true
Swapped first and last vertex:
2, 7, 11, 3, 8, 9, 10, 5
Is sorted = false

3
----------------------------------------------------------------------------
Original vertex order:
10, 9, 11, 2, 3, 8, 5, 7
Topologically sorted using `qsort`:
5, 3, 7, 8, 11, 2, 9, 10
Is sorted = true
Swapped first and last vertex:
10, 3, 7, 8, 11, 2, 9, 5
Is sorted = false

4
----------------------------------------------------------------------------
Original vertex order:
9, 3, 5, 2, 10, 7, 11, 8
Topologically sorted using `qsort`:
3, 5, 7, 11, 10, 2, 8, 9
Is sorted = true
Swapped first and last vertex:
9, 5, 7, 11, 10, 2, 8, 3
Is sorted = false

5
----------------------------------------------------------------------------
Original vertex order:
7, 9, 5, 8, 3, 10, 2, 11
Topologically sorted using `qsort`:
3, 5, 7, 8, 11, 2, 10, 9
Is sorted = true
Swapped first and last vertex:
9, 5, 7, 8, 11, 2, 10, 3
Is sorted = false

6
----------------------------------------------------------------------------
Original vertex order:
5, 8, 9, 10, 2, 11, 3, 7
Topologically sorted using `qsort`:
7, 3, 8, 5, 11, 2, 10, 9
Is sorted = true
Swapped first and last vertex:
9, 3, 8, 5, 11, 2, 10, 7
Is sorted = false

7
----------------------------------------------------------------------------
Original vertex order:
10, 5, 2, 7, 9, 8, 11, 3
Topologically sorted using `qsort`:
5, 7, 11, 2, 3, 8, 9, 10
Is sorted = true
Swapped first and last vertex:
10, 7, 11, 2, 3, 8, 9, 5
Is sorted = false
[/output]

Cheers,

- Alf (perplexed)

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]