The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Tree Boolean Formula UI

I've been tasked with prototyping a UI for creating a boolean formula (only AND and OR operators) for determining pass/fail for a course. 

The fomula must be displayed as a tree.  An example follows (they nixed my reverse polish notation prototype with good reason):

Course Name (root node)
  Exam 1
  AND
      Exam 2
      OR
      Exam 3
  AND
      Exam 4
      OR
      Exam 5

The formula displayed is: 1 && (2 || 3) && (4 || 5)

I'm really stumped on how to the UI to create the formula.  Has anyone seen another app that has similar functionality?  How did they do it?  Any ideas of your own?
JK Send private email
Thursday, March 08, 2007
 
 
Must you have a UI?  Could you get by with a single text widget into which the user could just enter the formula?

I remember working on a custom reporting system many years ago.  The 4GL in use at the time was too slow, so I was hired to re-write certain reports in C and hopefully achieve a speed-up.

For one custom report, I was able to allow free-form conditional expressions with AND, OR and the like.  It took the UI group more time to implement the UI for that than it took me to write the parser and evaluator in C.

For anyone reasonably adept at formulae, a simple entry widget is much easier.
David Jones Send private email
Thursday, March 08, 2007
 
 
What is stumping you?  I don't clearly understand what you need help with.
Franklin Send private email
Thursday, March 08, 2007
 
 
Recursive descent parser.
Mikkin
Thursday, March 08, 2007
 
 
My issue is not with computing the formula.  That I can do.

My question is:  How should I design the form in which the user will create the tree graphically?

Is there an app out there that has similar functionality?
JK Send private email
Thursday, March 08, 2007
 
 
You could look at it as a table with collapsable bands.  Each band is a grouping with zero or more subgroupings (the Os would be selectors):

+ Course 1
- Course 2
  -|Exam Group 1|
    Exam 1
    -|Exam Group 2|
      O Exam 2
      O Exam 3
    -|Exam Group 3|
      O Exam 4
      O Exam 5
+ Course 3

There are controls out there that do this already. Unless you need more flexibility there's no need to make a new one.
Angstrom
Thursday, March 08, 2007
 
 
Just use a tree widget that allows the user to add/edit and remove nodes.

There are many available. Check out IEWebControls, which are now integrated with .net 2.0 IIRC.

Also, check out ComponentArt's controls, again for .Net

I'm sure others will be able to direct you towards solutions for different platforms.

Is it always the case that level one nodes should be ANDed and level 2 nodes should be ORed? If not, you'll need to come up with a method of defining the operator between the nodes.

The recursive algorithm to generate the formula from the Node Collection should be fairly easy.
JJ Send private email
Thursday, March 08, 2007
 
 
The way I've seen this done before is that parent/child relationships indicate AND and sibling relationships indicate OR, so:

  A
      B
      C
        D
  E

becomes

  (A && (B || (C && D))) || E

It's got the twin merits of being unambiguous and parsimonious, it's pretty easy to parse conditions into trees and vice versa, and users generally come to grips with it sooner or later.
Robert Rossney Send private email
Thursday, March 08, 2007
 
 
I know the default .NET controls will do at least most of what I want.  The issue is the interaction between the controls in order to create the tree.  It's a little tough to describe in text.

Here's idea #1 I came up with:
- a list of operands (AND and OR)
- a list of terms
- a treeview on which the operands and terms can be click-and-dragged
- an indent and outdent button for nesting


However, this interface sounds clumsy and a pain to implement.  Are there any custom controls out there anyone knows of?
JK Send private email
Thursday, March 08, 2007
 
 
Oh, and this is a Windows Forms application.
JK Send private email
Thursday, March 08, 2007
 
 
WinForms... wow... I really can't see why you are having difficulty visualizing this.

Start with a blank tree, with only a root node.

User right clicks on root node, chooses Add node (or exam, whatever).

Perhaps they get a dialog box to enter node details or else a new node appears on tree with the text highlighted in edit mode (like creating a new folder in windows explorer) or there is a pane on the right where they enter the details.

In fact, if you just think of it like a cut down version of windows explorer, starting with one node (the root) and allowing the user to add successive nodes (folders) at any level (or up to the level you want) by right clicking on an existing node then you're done.

If you aren't familiar with windows explorer, I think we have more fundamental issues to contend with here.
JJ Send private email
Thursday, March 08, 2007
 
 
Go read up about trees.  If you inorder traverse a tree, you get infix.  If you postorder traverse a tree, you get RPN.

Sincerely,

Gene Wirchenko
Gene Wirchenko Send private email
Thursday, March 08, 2007
 
 
JJ:
Any any given depth, the operator may only be AND or OR.  However, which operator appears at which depth is up to the user.

The Windows Explorer analogy only goes so far because it doesn't have operands, but yes, I do have a general clue.  :)
JK Send private email
Thursday, March 08, 2007
 
 
You can simplify your job by constraining the input a bit ... if you always require sum-of-products format, you'll never need to worry about parenthesis or unlimited depth trees.

Of course, your users will have to learn how to change a equation into this format (I learned it programming PALs).
Steve Moyer Send private email
Thursday, March 08, 2007
 
 
Unfortunately, I believe a sum-of-products constraint wouldn't be acceptable to the users.
JK Send private email
Thursday, March 08, 2007
 
 
Without sum-of-products, you will need to treat your nodes as values and your branches as operators.  After that, it's easy to generate infix or postfix notation (or convert to sum-of-products).  The internal representation will be dependent upon how you're going to process the "formula".
Steve Moyer Send private email
Thursday, March 08, 2007
 
 
Think of a treeview that offers those little +/- in a box for expansing/collapsing subtrees.

Ditch collapsing, and replace the little box contents with symbols for AND and OR.  Maybe "click to toggle" action on them to flip between AND and OR.

Perhaps use the standard V-shaped boolean operator symbols rather than something from a CBCS (comic book character swearing) programming language like C.  Maybe even just small-text AND and OR in the box?
Codger
Thursday, March 08, 2007
 
 
How about this instead: nodes are operators (AND, OR) and leaves are values.

So this tree:

AND
  |
  |-- OR
  |  |
  |  |-- A
  |  |-- B
  |
  |-- AND
      |
      |-- OR
      |  |
      |  |-- C
      |  |-- D
      |
      |-- E

would turn into, in lispish notation:

(AND ( OR A B ) ( AND (OR C D) E ) )

or, for humans:

(A or B) and ( (C or D) and E )
Chris Tavares Send private email
Thursday, March 08, 2007
 
 
I’ve never seen anyone make a Boolean interface like this, but it sounds like an interesting approach for non-technical users who have a hard time grasping nested parentheses (getting them to understand the difference between logical AND, OR, and XOR is another matter). It’s hard to try to talk about this with just text, but here’s a shot. I’m assuming users typically use a subset of all terms available.

You have three elements:
1. a text control (e.g., a drop-down list) for entering the term (Exam),
2. a button (or equivalent) for an operator insertion (symbolized below with a “+”), and
3. a label to represent the operator (symbolized by a “&” or “|” below).
The UI starts as a blank pane except for one text control. Once the user enters a term, an operator button appears:

Exam1
+

Clicking the + adds a text control (to set another term) plus additional +’s.

Exam1+
&
Exam2+
+

When the user presses the first +, either default to one of the operators (and allow the user to change it) or provide a dialog for the user to pick & or |.

A + at the end of the text control “splits” the text control into two and automatically indents them. For example clicking the + after Exam2 gets:

Exam1+
&
      Exam2+
      |
      Exam3+
      +
+

Given you’re limited to just & and |, because the outer level operator is &, the inner operator must be |, so that’s selected automatically. The + at the bottom of a branch adds another text control to the same level, which must be a & since that’s the operator for that level.

Exam1+
&
      Exam2+
      |
      Exam3+
      +
&
Exam4
+

Following the same algorithm, clicking the + beside Exam 3 gets:

Exam1
&
      Exam2+
      |
          Exam3+
          &
          Exam5+
          +
      +
&
Exam4
+

The main difference over your original design is that the indenting is automatic and the operator is determined by the + clicked (you could dynamically label the +’s to show what operator the user gets). As an alternative, you could have your bank of terms, and the +’s become “landing zones” for drag and drop. That may be faster than clicking through drop down lists (especially for editing an existing tree), but you’re right that some users find drag and drop awkward and poorly self-documenting. It shouldn’t be the only way to do something.

As for implementation, if this is a thick-client app in .Net, I’d probably create combo boxes, command buttons, and label controls programmatically, and position them on the form by the algorithm implied above, keeping references of them in a data structure that represents their relations to each other (and is used to generate the ultimate Boolean string). I don’t see a good way of doing this with a single control, if that’s what you were looking for.
Michael Zuschlag Send private email
Thursday, March 08, 2007
 
 
This looks like a case of overspecification to put the $400 dollar to shame.  Why not just incorporate Visio into the application?
Mikkin
Thursday, March 08, 2007
 
 
You can use the GOLD parser system to generate a parser for the language of your choice. Then all you have to do is iterate through the resulting token tree to fill in your UI.
Wayne B Send private email
Thursday, March 08, 2007
 
 
OP: You might want to take a look at this:
http://www.devexpress.com/Products/NET/WinForms/XtraGrid/datafiltering.xml#autolist4

I for one never liked this UI too much, but I think it's almost exactly what you are after.
Alan
Friday, March 09, 2007
 
 
I want to thank everyone for all their help on this.

FYI, though - the issue is not how to parse the equation.  The issue is how to do the UI so it's easier for non-technical users to set up the equation.  Some of you understood this perfectly, some of you didn't, so I probably didn't express it clearly.

If anyone is particularly interested and wants to scribble down a drawing on a piece of paper and post a link to the image, that might help the discussion.

I'm still working on a solution.

Thanks for all your input!
JK Send private email
Friday, March 09, 2007
 
 
I used to work with a product called FormScape which did this.

The interface was like a tree control on steriods.

Each node on the tree was an object, there were different types of object (interfaces) for tests (boolean), text, numbers and few other types.

So for instance to compare two numbers you had:

Equals
--Number
--Number

or to compare text you would have

Equals
--Text
--Text

Objects like text or number generally linked to some other part of the tree or other data.

If you wanted to combine tests you could have something like:

And
--Equals
----Text
----Text
--Greater Than
----Number
----Number
Add node

The add node is a button to extend objects like And/Or to add more tests.

You could drag and drop these objects about.

The software went way beyond tests, there were enough objects to create a whole forms/output management application.

The main developer Daniel Earwicker has a post about it at http://www.earwicker.com/index.html?article=Component%20Trees.txt

It does provide a very quick development environment for people who are skilled with it but it can't make up for a room temperature iq.
Tony Edgecombe
Friday, March 09, 2007
 
 
Does it *have* to use the vertical tree view? I wonder if that might make things more confusing for simple cases. What if you start with just two blanks:

At least one of these: ____________
and all of these: ____________

For simple cases or less advanced users, this would be easy to fill in. You could have some GUI to insert items into the blanks. The result, of course, would be to OR the first box, AND the second box, and AND them together.

Then for complex cases, you could insert a special kind of item into one of the boxes. Call it an "Expression" or something. When you click on that item, you get another instance of the two-box panel, layered on top of it. In there you could enter another set of items, including more Expression items, and so on.

You could choose to display the complete tree in different ways -- maybe a regular tree would be more clear, or a series of nested boxes. Anyway, it's just a thought.
JW
Friday, March 09, 2007
 
 
How big is the formula going to be? Regardless of how nice your interface is, the tree is going to get huge pretty quickly; you might want to try displaying a reduced BDD if that's going to be a problem.
28/w
Sunday, March 11, 2007
 
 
"The fomula must be displayed as a tree."

Why must the formula be displayed as a tree?  If the UI is important you can use a regular list where the columns are anded and the rows are ored.  This may be simpler to understand.

"The formula displayed is: 1 && (2 || 3) && (4 || 5)"

To implement this as a list you give x columns and y rows and the user fills it up.  Display the text "and" between the columns and the text "or" between the rows.  Now all the user has to do is to fill the fields.  He does not have to bother with choosing "and" or "or".

 1 &&  2 &&  4 && __
      or
 1 &&  2 &&  5 && __
      or
 1 &&  3 &&  4 && __
      or
 1 &&  3 &&  5 && __
      or
__ && __ && __ && __


Of course if the number of permutations are many then this method may become cumbersome soon.
Donald Duck
Tuesday, March 13, 2007
 
 
This may be too late but here are some suggestions.

1.  First don't worry about dynamically updating your view of the formula as parts change.  Just rebuild and redraw the whole tree view when the formula changes.

2.  Focus first a good hierachical formula class and the properties and methods you need for it. 

3.  You need a tree view with a multi-select option.  If yours doesn't have one it may be better to just use a list view and simulate the tree by indenting the list view items.

4.  Your UI will have various buttons to manipulate selected items.  Possible buttons would include Add Simple Formula, Delete, Combine as OR, Combine as And, Split combination,  Move Up, Move Down.

5.  When you click one of the buttons use the methods of the Formula class to update the formula (not the tree view).  Then when the formula is updated just redraw the tree.

Bill Hamaker
Bill Hamaker Send private email
Wednesday, March 28, 2007
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz