search

SupposeNot / RAMP

Research Assistant for Maps and Polytopes
4 stars 0 forks source link

Define < on maniplexes so that sets of maniplexes work #134

Closed CunningGabe closed 2 years ago

CunningGabe commented 2 years ago

In GAP, a "Set" is essentially a sorted list, and it assumes that the objects are totally ordered using <. Trying to create a set of maniplexes throws an error.

We should define some arbitrary total order on maniplexes so that we can overcome this. A natural choice would be alphabetical by ID, once we have a comprehensive ID scheme.

Mixer2021 commented 2 years ago

If the user generates a maniplex using some odd construction, then RAMP won't know the ID right? I guess if the ID isn't already stored, a random hash could be used to give it some sort of name (rather than hunting for the correct ID).

CunningGabe commented 2 years ago

Right, good point. There is a slight challenge in that different maniplexes have different sets of defining information. So for example, we don't want to always compute a hash from the Connection Group, say, because not every maniplex knows its Connection Group.

So here's an idea for a scheme:

  1. Arbitrarily decide on an order of the types of defining information that a maniplex can have. (Aut gp, Conn gp, flag graph, poset, and "formal output of an operation" e.g. Pyramid(stuff))
  2. Then for each type of possible defining information, define a hash function that will be fast for that type.
CunningGabe commented 2 years ago

Actually, I just realized another wrinkle - a given maniplex might be represented in two different ways, and so this scheme would lead to the possibility that M1 < M2 but also M1 = M2. I guess this would probably cause problems. (I mean, maybe some things would work okay, but I'm not sure we should count on that.)

Unfortunately, I'm not sure if there's an easy, computationally cheap way to define < so that M1 < M2 implies M1 is not equal to M2...

SupposeNot commented 2 years ago

This is a really interesting question to think about... I'll see if I can come up with any useful ideas...

Is there some problem in particular we are trying to solve by treating collections of maniplexes as sets rather than lists? In some use cases, it would make sense for the ID to be tied to a particular enumeration/set of associated properties, but not appropriate in more general contexts. Not everything has to be a set after all...

CunningGabe commented 2 years ago

Sort of - there are some set operations that aren't implemented for lists, like Difference. It's not hard to code a workaround; it's just annoying.

Buuuuuut if we can't find a good way to define <, then maybe I'll just add a utility function for Difference(list, list) that assumes each list is duplicate-free.

Mixer2021 commented 2 years ago

Another option would be to include that [not (M1 = M2)] in the check for (M1 < M2). I don't know if that would slow things down to a point where the Set operation is no longer useful.

CunningGabe commented 2 years ago

Yeah, I think it might slow things too much. So let's nix this and I'll build some alternate versions of set operations as necessary.