CODEWITHSUNDEEP
parsingdata-structures
nnythm
nnythm

Reputation: 3320

Canonical mutual exclusive data structure

Note: this is unrelated to the concurrency problem of mutual exclusion, but I couldn't think of a better way of describing the problem.

I have a problem that I have a case where I want to let a user select some flags, but some flags are mutually exclusive. I want to describe which flags are mutually exclusive using a data structure, but everything I've thought of has been clunky.

Basically, I want to be able to specify how flags will be used like so:

[ -fa | -e | -d ] [ -c ] [ -g | -h ]

This should semantically mean, I can have any one of -fa, -e, -d, but not two or more (however, f can be used with a, and you don't need to use both). I can either have a -c or not, and I can have either -g or -h, but not both.

Here's my "best" solution.

Map[Flag, MutexGroup] (and its inverse, Map[MutexGroup, List[Flag]]) Map[MutexGroup, List[MutexGroup]]

What it would look like for my example would be

Map("f" -> 1, "a" -> 1, "e" -> 2, "d" -> 3, "c" -> 4, "g" -> 5, "h" -> 6) Map(1 -> List(2, 3), 2 -> List(1, 3), 3 -> List(1, 2), 4 -> List.empty, 5 -> List(6), 6 -> List(5))

I haven't included the Map[MutexGroup, List[Flag]] for brevity.

This solution makes me shudder just thinking about having to work with it. Is there a canonical way for dealing with this kind of thing?

Upvotes: 1

Views: 325

Answers (2)

brubsby
brubsby

Reputation: 478

Although it seems you found a satisfactory answer about a decade ago, I couldn't help but come across this when I had a similar question about compactly storing information for enforcing mutual exclusivity in a different context. I don't think a grammar would really work for my situation, so I'll leave my thoughts here for passersby.

The most compact and tidy data structure I can imagine to represent arbitrary mutual exclusion between N entities is an edge list for an undirected graph, where each entity is a node, and an edge between them represents mutual exclusivity. Then when you need to validate that the constraints haven't been violated, you can simply iterate through the edge list and check that at most one of the entities is included per edge.

This way, the validation can be done in a reasonable time, the data structure doesn't have unnecessary duplication (as would an adjacency matrix or adjacency list), and it's applicable to situations regarding mutual exclusion that aren't parsed or don't have an apparent ordering.

So for example, your flags' mutual exclusion edge list would be stored and validated as so (python):

mutual_exclusion_edge_list = {
    ("fa", "e"),
    ("e", "d"),
    ("d", "fa"),
    ("g", "h"),
}

def validate_flag_mutual_exclusion(flags):
    return all(not (edge[0] in flags and edge[1] in flags) for edge in mutual_exclusion_edge_list)

And while this example is a bit trivial and seemingly wants to just be stored as a list of two sets, storing larger amounts of arbitrary relationships this way is more readable than the alternatives, especially if the mutual exclusions do not all form fully connected subgraphs as they do here. (fully connected subgraphs could be represented most compactly as a set or list of elements)

Depending on the application, it might also be desirable to store a list of sets for which the elements form a fully connected mutual exclusion subgraph. Either in addition to, or instead of the edge list.

Upvotes: 1

Don Stewart
Don Stewart

Reputation: 137957

You're describing a grammar.

The best thing for representing grammars is an abstract syntax tree. The tree being the canonical structure that represents (mututally exclusive) choice.

You can represent syntax trees in many ways, but one nice approach is to use algebraic data types, as they statically guarantee only well-formed expressions can be constructed. The flags themselves form a set, so using a Set data type to enforce the no-duplicates property is also good.

-- can have any one of -fa, -e, -d, but not two or more
-- (however, f can be used with a, and you don't need to use both).
-- I can either have a -c or not, and I can have either -g or -h, but not both.
--

-- zero or more flags
type Flags = Set Flag

-- Flags come in three groups
data Flag
        = F1 FAED
        | F2 C
        | F3 GH
    -- equality up to the first constructor. 

-- one of: -f or -a; -e; -d
data FAED
        = FA FA 
        | E
        | D

-- a type for: -f ; -a ; -f -a
data FA = F
        | A
        | FA

-- the -c flag
data C  = C

-- either -g or -h
data GH = G
        | H

There are other ways to encode your language as well, but this is enough to start you down the path of representing the language using a syntax tree.

Upvotes: 3

Related Questions