1

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?

Don Stewart
  • 137,316
  • 36
  • 365
  • 468
nnythm
  • 3,280
  • 4
  • 26
  • 36

2 Answers2

3

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.

Community
  • 1
  • 1
Don Stewart
  • 137,316
  • 36
  • 365
  • 468
  • I've know I'm describing a grammar, I've already written a parser to parse the description of the flags. I don't know how to store the idea of mutual exclusivity, and a syntax tree does not seem like it will be useful. I am not going to have a problem parsing it once I know what I need to do, as you have shown, it is extremely straightforward. My problem is just passing the data on what is mutually exclusive to the parser generator. – nnythm Jun 04 '12 at 15:40
  • "a syntax tree does not seem like it will be useful" -- the AST for your command language is precisely the data type that describes the invariants for your language. I'm not sure what else you could possibly be expecting. – Don Stewart Jun 04 '12 at 15:59
  • A syntax tree will be how I parse it, but it isn't that easy to actually use the syntax tree once I have it. I want to be able to feed it actual flags, like -afch and let it tell me quickly whether or not it is valid under the rules that my language has specified. For that, I need a data structure that lets me look that kind of thing up easily. I could eventually traverse my AST and figure that out, but it is nontrivial. Hence, I need a data structure that will describe mutual exclusivity. – nnythm Jun 04 '12 at 16:20
  • "I want to be able to feed it actual flags, like -afch and let it tell me quickly whether or not it is valid under the rules that my language has specified." -- that's what the parser does. If it can parse the input, then the input is valid. It is your parser that should be enforcing the validity of the input -- derived from the grammar of your language. No other lookups or checks are needed. Have you written a grammar? From your grammar you should be able to write a parser that enforces valid input, and also a result data type. – Don Stewart Jun 04 '12 at 16:28
  • Ok, I see what you mean now, sorry I was so thickheaded. My plan was to generate an AST based on the flags I was passed by a user and then to compare it against my data structure, but you're right that it makes more sense to make my parser do it. – nnythm Jun 04 '12 at 17:09
1

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.

brubsby
  • 388
  • 2
  • 13