search

oulan / oppia

Automatically exported from code.google.com/p/oppia
Apache License 2.0
0 stars 0 forks source link

Code review request: improve graph layout #670

Open GoogleCodeExporter opened 9 years ago

GoogleCodeExporter commented 9 years ago 
Branch name: layout-experiment

Link to the relevant commit(s): 
https://code.google.com/p/oppia/source/detail?r=172bb6383114f708194cdd433ebd4fc2
5b9b66d8&name=layout-experiment

Purpose of code changes on this branch: Try to make the graph look nicer by 
changing the layout algorithm (it used to be simple BFS). This results in some 
significant improvements to e.g. Project Euler Problem 1 and Three Balls. I 
think The Lazy Magician looks somewhat better, too.

When reviewing my code changes, please focus on:
  - Amit: what do you think of the layout? I'm particularly interested in anything you think is obviously 'bad', and what you think a 'good' version of that would look like. Also, I'm wondering how to handle the arrows connecting non-consecutive states in the long vertical chains. (Note that the left column of the graph can be read as a series of consecutive states, so maybe one day we can have 'continuous scroll' down this column.)
  - Xinyu: what do you think of the layout? My current algorithm is: find longest path in the graph by backtracking using DFS (truncating if this is doing too much work) and then using a sort of BFS to fill in the locations of the other nodes, so that they appear a level below their earliest predecessor. I have two thoughts:
      * maybe I could do better with articulation points (e.g. see the graph for Parameterized Adventure -- the 'troll' section)
      * in cases where I have A --> B --> C and A --> C, the left column will be A --> B --> C straight down and there will be an overlapping A --> C arrow. In cases like this I feel like the right fix is to move the 'B' node one column to the right. Not sure yet how to generalize/formalize this.
    I plan to think about this more, but was wondering if you have any ideas. (This would be pretty useful for something like the 'Pitch Perfect' exploration, which manages to orient itself in a single column but looks a bit of a mess with regards to the arrows.)

After the review: I will not merge this branch anywhere; I'll try to improve 
this based on any suggestions received and further ideas that I come up with.

Thanks!

Original issue reported on code.google.com by s...@seanlip.org on 23 Mar 2015 at 7:35

GoogleCodeExporter commented 9 years ago 
UPDATE: Tried to handle the overlapping arrows in the layout-experiment-2 
branch; PTAL at that too.

Original comment by s...@seanlip.org on 23 Mar 2015 at 8:55

GoogleCodeExporter commented 9 years ago 
Oops, forgot to add link.

    https://code.google.com/p/oppia/source/detail?r=f113ceb06a74013e82469c20e365635df5724800&name=layout-experiment-2

(Also, just to be clear, please don't worry about reviewing the code. It's 
quite icky! I plan to redo this properly once we figure out what we want the 
graphs to look like :P)

Original comment by s...@seanlip.org on 23 Mar 2015 at 8:56

GoogleCodeExporter commented 9 years ago 
I think layout-experiment is a *huge* improvement, way to go! For the 
overlapping arrows, would it be possible to have the arrows 'stick out' instead 
of overlapping with the states below them? I attached a mockup to demonstrate 
this.

layout-experiment-2 makes sense to me conceptually but in practice it feels 
messy with all the gaps. I think that as an author I wouldn't expect to have 
consecutive states be so far apart from each other.

Thanks,
Amit

Original comment by amitdeut...@google.com on 23 Mar 2015 at 4:44

Attachments:

GoogleCodeExporter commented 9 years ago 
Thanks for the feedback!

Any thoughts on something in between, like having the nodes indented slightly 
(but by less than a full node's width)? I had similar feelings as you did -- I 
do like the insight given by layout-experiment-2, but felt a bit uncomfortable 
with it and just couldnot put my finger on why.

Original comment by s...@google.com on 23 Mar 2015 at 4:52

GoogleCodeExporter commented 9 years ago 
Attached a new screenshot, is that what you meant? Would it be possible to 
prototype this in layout-experiment-2 and see how it looks?

Original comment by amitdeut...@google.com on 23 Mar 2015 at 4:58

Attachments:

GoogleCodeExporter commented 9 years ago 
I prototyped it in layout-experiment-3 -- sort of. The catch is that it's going 
to take some nontrivial work to change where the arrows originate from, and I 
don't think I have the time to do this in the near future.

So, I'm going to ask: suppose we could do either (a) what currently exists in 
develop, (b) layout-experiment as-is, (c) layout-experiment-2 as-is, or (d) 
layout-experiment-3 as-is; which would you prefer? I'll take that as an interim 
solution for the time being.

Original comment by s...@seanlip.org on 24 Mar 2015 at 6:02

GoogleCodeExporter commented 9 years ago 
Actually, I think layout-experiment-3 is quite nice, that's my top preference. 
Well done with this, I think both layout-experiment and layout-experiment-3 are 
big improvements over develop.

Original comment by amitdeut...@google.com on 24 Mar 2015 at 1:14

GoogleCodeExporter commented 9 years ago 
I like layout-experiment-3! I think the indenting long paths method works quite 
well, and it's a significant improvement over develop. 

The only strange thing I found is still when a state leads to a bunch of 
choices which are linked, and finally leads to another state (this creates the 
diagonal structure, which I think does not really express the exploration 
structure). I think they should be on the same vertical level, but I'm still 
unsure how to implement this. I've looked around and this only happens for the 
lazy magician and pitch perfect explorations. For the others 
layout-experiment-3 works really well, so that's great.
It may also be good to still have a limit on the max width of the graph.

Original comment by wxy.xi...@gmail.com on 24 Mar 2015 at 5:36

GoogleCodeExporter commented 9 years ago 
I think you're right about the "bunch of choices" issue. It would be nice to be 
able to detect 'clusters' somehow -- maybe the dominator stuff we were looking 
into before might help. But this is probably future work.

Yeah, I am concerned about the max width too -- especially on the history and 
stats tabs where the graph does not have its own frame. This could get a bit 
complicated, though, because with the indentation we have less space on the 
right to stick the extra nodes (and it might also be weird if we abruptly stop 
the indentation after some point, e.g. imagine the music exploration). Still, 
I'm also thinking that we might want to implicitly encourage explorations 
without too much indentation anyway, so maybe it's OK if these edge cases look 
a bit weird for now until we find some way to handle them gracefully.

Leaning towards implementing layout-experiment-3 and just putting a hard stop 
on indentation at around 3 node widths -- sounds good? If so, I will try and 
send a code review request later this week.

Again, thanks a lot for the feedback!

Original comment by s...@google.com on 24 Mar 2015 at 5:48

GoogleCodeExporter commented 9 years ago 
Yeah, I'm not sure if stopping the indentation would cause some explorations to 
look weird too. Perhaps we can try limiting the indentation and see how it 
looks. Why would we want to encourage explorations not to indent too much? For 
the stats and history pages, we could also change them to have the graph in a 
pan-able window (like the graph modal in the editor).

Original comment by wxy.xi...@gmail.com on 24 Mar 2015 at 6:01