linkedin

CSS3 and AV revisited (with flexible box layout)

In the first post about CSS3 and algorithm visualization, I had demos showing how to animate sorting algorithms using CSS3 transforms. Yesterday, when watching CSS3 First Look on Lynda.com, I learned about the CSS3 Flexible Box Layout Module and wanted to give it a try and improve the previous animations.

Flexible Box Layout

The flexible box layout gives an excellent way to control the layout and ordering of elements on a page. All in all, it's really flexible. To give an example, let's work with the following HTML. 

  <div id="container">
    <div id="box1">Box 1</div>
    <div id="box2">Box 2</div>
    <div id="box3">Box 3</div>
  </div>

Now, without any styling, this would become a page where the divs are vertically on top of each other. With just one line of CSS3 magic, we can change that:

    #container  { display: box; }

Actually, we need at least three lines until the specification is ready and vendor prefixes are dropped:

    #container {
      display: -webkit-box;
      display: -moz-box;
      display: box;
    }

This will arrange the boxes horizontally next to each other (see the demo, example 2). The feature I was most interested in related to the sorting algorithm animation is the box-ordinal-group property. It allows to change the order of the child elements inside the box. To give you an example, the following CSS3:

    #box1 { 
      -webkit-box-ordinal-group: 2;
      -moz-box-ordinal-group: 2; 
      box-ordinal-group: 2;
    }
    #box2 {
      -webkit-box-ordinal-group: 3;
      -moz-box-ordinal-group: 3;
      box-ordinal-group: 3;
    }
    #box3 {
      -webkit-box-ordinal-group: 1;
      -moz-box-ordinal-group: 1;
      box-ordinal-group: 1;
    }

would change the boxes to be in order box3, box1, box2 from left to right (view the demo, example 3).

Visualizing Sorting Algorithms

One of the problems with the original CSS3 algorithm visualizations was the calculation of pixels when translating the elements to animate array item swaps. The box model seems like a great solution for replacing the pixels with just changing the box-ordinal-group property.

After creating a simple test case, I realized that it did not work as I suspected. The elements changed places, but no smooth animation was shown. After spending some time trying to fix my CSS I turned to Google. To my disappointment, it wasn't my code that was broken. Nor was it the browser. The box-ordinal-group just isn't one of the animatable properties according to the CSS3 Transitions specification.

So, to sum up the experiment: flexible box model could be used to visualize sorting algorithms, if no smooth animation is needed. In modern browsers, that is. According to caniuse.com, browsers that support this currently are Firefox 3.5+, Safari 3.2+, and Chrome 9.0+. In addition, Mobile Webkit on iOs and Android support it.

CSS3 Transformations and Transitions for Algorithm Visualization

CSS3 offers some interesting new properties that could be used for algorithm visualization. Here, I'll first introduce the new properties and then proceed to show and explain some demos that I've created. You can skip the nonsense and view the demos: bubble sortselection sort

CSS3 (or Cascading Stylesheets 3)

CSS3 includes several modules useful for web designers and web developers. Here, we are only interested in a couple: CSS Transforms, CSS Transitions, and CSS Animations. These are the modules that make it possible to add animation effects to web pages using CSS classes.

CSS Transforms CSS3 transforms allows translation, rotation, and scaling of elements in 2D and 3D. A two-dimensional transformation is applied to an element through the transform property. This property contains a list of transform functions. The transform-origin property establishes the origin of transformation for an element.

The transform functions in the specification are translate, scale, rotate, and skew. There are also versions of translate, scale, and skew to transform only X or Y dimension, that is, translateX and translateY, for example. Furthermore, the matrix transform functions allows for matrix transformations. Multiple transform functions can be used in a single transform property.

CSS Transitions The new CSS3 Transitions module defines CSS properties that can be used to change values of properties smoothly from one value to another over a specified duration. The transition behaviour is specified using a number of CSS properties.

  • transition-property specifies the properties that are smoothly changed. All animatable properties (not all CSS properties can be transitioned) that have changed can be animated using the value 'all'.
  • transition-duration is used to specify the length of the transition and transition-delay when the transition will start.
  • transition-timing-function describes the way the intermediate values are calculated. This allows a transition to change speed. There are several timing functions specified, for example, linear, ease-in, and ease-out.
  • transition property is a shorthand property that allows setting all of the above with one CSS property.

Listing below gives an example of how one would specify a transformation and a smooth transition.

    #selected {
      transition-property: transform, background-color, opacity;
      transform: translate(200px) scale(0.6);
      background-color: yellow;
      opacity: 0.2;
    }

The specified transformation would look like something in the picture below, assuming the original object had a red background and was not transparent.

css3transition-example

CSS Animation The CSS3 Animations module includes features to enable more fine-grained animation. This includes properties like keyframes that enable composing more controlled transitions. The module is an extension of the Transitions module.

Algorithm Visualizations with CSS3

To test how the new CSS3 properties work for visualizing algorithms, I created a couple of demos of sorting algorithms. Check out the bubble sort and selection sort demos. You'll need a browser that supports the new features, such as recent version of Chrome or Safari. If you don't have such browser, go install one or see the picture below.

CSS3 Algorithm Visualization demo screenshot

You can move backward and forward in the animation obviously using the links. When moving, the current codeline is highlighted, variable values updated, and the swaps of array elements animated. In addition to moving backward and forward, you can also change the layout to focus on the code or the data structure.

Technical Details

The animations are generated by an (ugly) Python script. This script is general enough that it would allow creation of animations of other sorting algorithms (or other algorithms working with arrays) by writing and annotating the python code. The code in the created animations is the actual Python code used to run the algorithm.

The Python code generates a JavaScript array of CSS class names as well as the corresponding CSS3 properties. An example of a highlight operation is shown below. 

/* codeline highlight */
.css-line2-5 { background-color: #afa; }
/* array element highlight */
.css-elem2-5 { background-color: yellow; }
/* moving an array element */
.css-elem2-6 {
   -webkit-transform: translate(-102px,0);
   -moz-transform: translate(-102px,0);
   transform: translate(-102px,0);
}

When moving backward or forward in the animation, JavaScript updates the CSS class attributes of the codelines, variables, and array cells changed in the operation. The browser then animates the changes according to the CSS properties.

Conclusion

While the browser support for CSS3 transformations is improving, they still can't be used for learning material that all students need to be able to access. But, they work well enough on some mobile browsers (such as iPhone and Android phones) to be useful when building AVs for mobile devices.

New Publication List with bib-publication-list

I finally got tired of updating my old HTML publication list by hand. I wanted something that would be automatically generated from my BibTeX file, without me having to remember to run any scripts or copy files. So, I wrote bib-publication-list. With it, I can just include the BibTeX into my HTML page and tell the script to turn it into a sortable and searchable table. Besides loading the required JavaScript files, all that is needed is to add a table where the data should be added and include the BibTeX:

    @article{Karavirta:JVLCTaxonomy,
        title = {A comprehensive taxonomy of algorithm animation languages},
        journal = {Journal of Visual Languages \& Computing},
        volume = {20},
        number = {1},
        pages = {1--22},
        year = {2010},
        issn = {1045-926X},
        doi = {DOI: 10.1016/j.jvlc.2009.09.001},
        author = {Ville Karavirta and Ari Korhonen and Lauri Malmi and Thomas Naps}
    }

Alternatively, the bibtex can be loaded from a file. I prefer including it in the HTML, though. This way, browsers without JavaScript enabled get at least to see the bibtex instead of a blank page.

Finally, the bib-publication-list needs to know the input data element and the output table. So, one line of JavaScript:

bibtexify("#bibtex", "pubTable");

The result looks like the figure below (or my new publication list).

The source code for the library is available on GitHub. The code uses some great libraries: jQuery, DataTables, Protovis, and JavaScript BibTeX Parser.

Let me know what you think. Especially comment if you have problems with it, I haven't tested it on all browsers (yet).

Fun with MozOrientation in Firefox 3.6

The already not so new Firefox 3.6 ships with a way for websites to detect the orientation of the laptop/device of the user. This opens interesting new possibilities for web applications similar to some iPod/iPhone/etc games. Some interesting demos are already available online:

Technically, using the new feature in JavaScript web application is really simple. It is  be done by listening to the MozOrientation event. So, in Javascript:

//register a listener
window.addEventListener("MozOrientation", updateOrientation, true);
function updateOrientation(orientation) {
    // do something with orientation.x, orientation.y
}

Since it seemed easy to use, I wanted to give it a try. The result is a simple game where you need to "collect" a number of targets on the screen. Try it yourself if you have a laptop that is supported and has an accelometer, for example MacBook(Pro). Can you come up with an application for the use of accelometer in education?

A Comprehensive Taxonomy of Algorithm Animation Languages

The article "A comprehensive taxonomy of algorithm animation languages" was finally published in the Journal of Visual Languages & Computing in volume 21, issue 1 (doi). I'd like to thank my co-authors Lauri Malmi, Ari Korhonen, and Thomas Naps for their hard work in writing this article. The abstract of the article:

In this paper, we present a taxonomy of algorithm animation languages that augments Price's well-known taxonomy of software visualization. Whereas Price's taxonomy is directed to classifying features and characteristics of visualization systems, the new taxonomy focuses on evaluating current animation languages. The taxonomy can be used by algorithm visualization system designers as a tool to compare visualization system languages with each other as well as for designing and implementing new systems and language features. In addition, the taxonomy provides guidelines to the features that are needed for transferring animations between systems. This is an ongoing project that elaborates upon the work reported on in a briefer version of the taxonomy.

The main categories of the presented taxonomy are Visualization, Dynamics, User Interaction, and MetaLanguage:

  • The category Visualization describes the features of the language used to create static visualizations for describing one state in the animation. In essence, it considers the variety of supported object types, that is, the building blocks used in the animation as well as ways to position and style the objects.
  • The category Dynamics describes the level and versatility of animation effects available in the language and how the final animation can be customized through the language. These are the ways the visualizations can be changed when moving from state to state.
  • The category User Interaction describes the type and level of interaction provided for the end-user of animations that can be specified using the language.
  • The category MetaLanguage describes the support of features that are not directly related to algorithm animation but instead are useful in the animation creation process. These are features that are not directly visible to the end user.

The figure below shows the two highest levels of the taxonomy. The paper also includes an evaluation of many of the existing AA languages. So, go read it and let me know what you think!

Interactive Questions in JSXaal

Update (March 2012): The JSXaal project is not actively worked on anymore. See JSAV for a JavaScript algorithm visualization framework.

Interactive Questions

Interactive questions in algorithm animations are questions shown to the student. Typically, the questions require students to predict what is going to happen in the following steps of the animation based on the current state and the algorithm in question. The main motivation behind the questions is the belief that the more engaging the animations are, the better the learning results (see Engagement Taxonomy, especially level Responding). For this reason, interactive questions have been used in many visualization systems, such as Animal, JHAVÉ, Jeliot, and ViLLE.

Interactive Questions in JHAVÉ..

Interactive Questions in JHAVÉ..

Since the usage of interactive questions has become more and more popular in AV systems, several studies of their effectiveness in learning has been carried out. Here I'll introduce only some of them

  • In 2000, an experiment comparing levels viewing and responding was conducted by Jarc et al. The results of the survey found no statistically significant differences. However, the data indicated that the students working on level responding scored better on difficult topics, but poorly overall. The study used the Interactive Data Structure Visualizations system to visualize the data structures.
  • Grissom et al. experimented in 2003 to compare levels no viewing, viewing, and responding using JHAVÉ system. The results show that learning improves as the level of student engagement increases. The difference between no viewing and responding was statistically significant.
  • A recent study in 2009 by Taylor et al. compared students using passive and predictive animations of graph algorithms. They conclude that students working on the responding level learned better than students viewing passive animations. It is unclear, though, whether or not their results were statistically significant.

Interactive Questions in XAAL

The roots of XAAL come from the ITiCSE 2005 working group "Development of XML-based Tools to Support User Interaction with Algorithm Visualizations" (see also the Working Group report). The working group specified and gave examples for different parts of an XML-based algorithm animation language. One of the parts that was specified in detail were the interactive questions. Thus. those specifications have been adopted in XAAL. Below are examples and explanations of the different question types supported by XAAL (the working group report specifies more), see the documentation for the XAAL XML schema for interaction for details.

  • select: for multiple-choice questions where multiple answers can be selected by student
    <select id="selectQuestion">
      <contents type="label">Which do you want to select?</contents>
      <item id="sit1" grade="2">
        <contents type="answer">Select me!</contents>
      </item>
      <item id="sit2" grade="1">
        <contents type="answer">Select me also!</contents>
      </item>
      <item id="sit3" grade="-2">
        <contents type="answer">I hope you won't select me..</contents>
      </item>
    </select>
    
  • select-one:for multiple-choice questions where only one answer can be selected by student
    <select-one id="selectOneQuestion" solutionId="it3">
      <contents type="label">How many <i>children</i> does 
                 the rootnode of the tree have?</contents>
      <item id="it1">
        <contents type="answer">1</contents>
      </item>
      <item id="it2">
        <contents type="answer">3</contents>
      </item>
      <item id="it3">
        <contents type="answer">4</contents>
      </item>
    </select-one>
    
  • fill: for fill-in-the-blanks questions that can contain several blanks where the student should enter her aswers

..and in JSXaal

When an animation with interactive questions is viewed in JSXaal, the questions are shown to the user. The user will also get feedback on whether or not her answers were correct. The figure below shows an example question in JSXaal. You can also view an example online. Currently, JSXaal supports questions of type select-one and select.

Example question in JSXaal
Example question in JSXaal

When integrating with online material and some learning environment, it's often necessary to communicate the student answers back to the server. In JSXaal, this can be done by implementing a simple JavaScript class. The class has to have two functions:

  • questionAnswered(question): This function is called whenever a student answers a question. It gets as a parameter the question as an instance of JSXaal.Question.
  • annotationAdded(annotation): This function is called whenever a students adds an annotation to the animation.

So, a simple example of doing this is:

Event.observe(window, 'load', function() {
  viewer = new JSXaalViewer("animation", {}, {fileUrl: "xaal-interaction-demo.xml"});
  MyServerInterface = Class.create({
    annotationAdded: function(annotation){
      // handle the annotation
    },
    questionAnswered: function(question){
      // handle the question
    }
  });
  viewer.setServerInterface(new MyServerInterface());
});

What you do with the annotation and question is completely up to you. One possible way is to store the complete XAAL animation on the server, as the question response and the annotation are added to the current animation.

JSXaal Goes Open Source

Update (March 2012): The JSXaal project is not actively worked on anymore. See JSAV for a JavaScript algorithm visualization framework.

JSXaal viewer, the JavaScript viewer for XAAL animations is now an open source project at Google Code. You can find the project here.

Getting Started

First of all, make sure to check the brief introduction to XAAL. Then follow the three simple steps below.

Step 1: Check out the source

To checkout the source code, you will need Subversion installed. Then you can checkout the code by typing: svn checkout http://jsxaal.googlecode.com/svn/trunk/ jsxaal-read-only

Step 2: Play with the Example

The directory that you just checked out includes an example in doc/example.html (imaginative naming, don't you think?). You can also view the example online. What you should see when opening that file is something like the image below. The controls for the animation should be quite self-evident: forward moves you forward and backward one step backward.

JSXaal Viewer Example

JSXaal Viewer Example

Step 3: Modify the XAAL document

The example loads the XAAL file doc/example.xml. Try modifying it by, for example, changing the positions or colors of the objects. You can also add new objects or animation effects according to the XAAL specification. Note, that the viewer does not support the whole specification yet.

XAAL has a new home at xaal.org

Main page of xaal.org
Main page of xaal.org

As I aim to publish XAAL and the related tools for the whole AV community to benefit from, XAAL has moved to xaal.org. The site has all the important information about XAAL:

  • Publications - There are already several publications available about XAAL. These are all listed on xaal.org.
  • Documentation - Documentation is something I'm working on improving. At the moment, the site includes some examples on how to use XAAL.
  • Schemas - The XML Schemas for XAAL are available from the site. The documentation for these is also work in progress.

Now that you all non-existing readers of this blog :) know what is available from the site, it's a good time to explain why you should (or shouldn't) visit the site.

What is XAAL?

In short, XAAL (eXtensible Algorithm Animation Language) is an algorithm animation language designed to be used in multiple algorithm animation (AA) systems. The goal is to unify the AA world by allowing interchange of animations between the existing systems. The language has primitives for working with graphics such as rectangles and circles, as well as data structures like arrays and graphs.

XAAL Example

The following is an example of using graphical primitives in XAAL.

<polyline id="poly">
  <coordinate x="210" y="210"/>
  <coordinate x="220" y="220"/>
  <coordinate x="210" y="230"/>
  <coordinate x="230" y="230"/>
  <coordinate x="230" y="210"/>
  <closed value="false"/>
  <style>
    <color name="lime"/>
    <fill-color name="black"/>
    <stroke width="4"/>
  </style>  
</polyline>
graphical-example-150x150.jpg

In addition to the polyline, the building blocks available include

  • point, polyline, line, polygon;
  • arc, ellipse, circle and circle-segment;
  • square, triangle, rectangle;
  • text.

Data structures available include array, graph, list, tree, and binary tree. Below is an example of a graph.

<graph>
  <node id="n1"><key value="D"/></node>
  <node id="n2"><key value="E"/></node>
  <node id="n3"><key value="M"/></node>
  <node id="n4"><key value="O"/></node>
  <edge from="n1" to="n2" directed="true"/>
  <edge from="n2" to="n3" directed="true"/>
  <edge from="n3" to="n4" directed="true"/>
  <edge from="n4" to="n1" directed="true"/>
</graph>
XAAL graph example

Tools for working with XAAL

There are also tools for creating and working with XAAL animations. These include a Java parser, classes for creating animations, and adapters for converting XAAL animations for some of the existing algorithm animation systems. These are not, however, published yet but they will be. So, stay tuned for more updates on that!

Currently, the animations can be used in JHAVÉ or using the JavaScript viewer.

My article "Seamless Merging of Hypertext and Algorithm Animation" in TOCE

My article "Seamless Merging of Hypertext and Algorithm Animation" was finally published in ACM Transactions on Computing Education (TOCE) in volume 9, issue 2 (in ACM digital library). The abstract of the article:

Online learning material that students use by themselves is one of the typical usages of algorithm animation (AA). Thus, the integration of algorithm animations into hypertext is seen as an important topic today to promote the usage of algorithm animation in teaching. This article presents an algorithm animation viewer implemented purely using HTML and JavaScript. The viewer is capable of viewing animations in Xaal (eXtensible Algorithm Animation Language), a language designed to allow easy transformation of AAs between various formats. This solution is extremely suited for use in hypertext learning material due to the advanced interaction possibilities between learning material (HTML) and the animation.

I'll try to post some demos of the viewer soon. Below is a picture explaining the main parts of the viewer.

JSXaal viewer
JSXaal viewer