Home

Graph Representation

We require a comprehensive graph library for efficient storage and manipulation of graph data. Many standard graph algorithms should already be implemented so we can easily expose these (e.g. is_connected) or else use them to provide key functionality (e.g. topological_sort). We also need to be able to initialize our graph with standard graphs. It appears that JSNetworkX is the most suitable library for this.

Graph Visualisation

Since this project is geared toward teaching the basics of graph theory, it is important to be able to present meaningful, concrete ("real world") instances of graphs.

A good example might be a neighbourhood's power grid: the houses are the nodes, and the power cables are the edges. Perhaps we want to lay out the grid so as to minimize the amount of cable used (an example of the minimum spanning tree problem). In order to make this seem more intuitive, we would like to:

1. Make the analogy obvious by drawing the nodes and edges as houses and power lines, respectively (i.e. the ability to use user-supplied images for nodes and edges).
2. Show the algorithm in action by showing how the tree changes as the algorithm progresses (i.e. dynamically updating the display in response to changes in the graph).

JSNetworkX comes with support for the D3.js visualisation library. It mostly fulfils the above requirements, with the exception of custom images for edges, which will require modifications to the visualiser. For cases of graphs where the nodes are not required to be at fixed positions (e.g. social networks) we are also provided with force-directed graph layout to improve readability.

Graph Algorithm Primitives

Data structures

The following data structures have so far been identified as useful for implementing elementary graph algorithms and will be provided as primitives for the sake of convenience:

• stack
  • depth-first search
• queue
  • breadth-first search
• priority queue
  • Shortest path(s) algorithms
    • Dijkstra's algorithm
    • uniform-cost search
    • A* search
  • Minimum spanning tree
    • Prim's algorithm
• set
  • topological sort
  • A* search

Graph operations

We wish to expose the following operations and queries on graphs:

• Get node by name
• Add node/edge
• Delete node/edge
• Get node neighbours
• Get edge from nodes
• Get/set node/edge attribute
• Get nodes/edges with attribute
• Get subgraph from nodes/edges
• Contains given node?
• Is connected?

User Interface

Graph display

The turtle graphics widget will be replaced with a graph display widget. The user must be able to create and modify graphs within the graph display using a drag and drop interface. The following operations will be provided:

• Create standard graph
• Create/delete node/edge
• Modify selected nodes'/edges' attributes
• Tentative: find node by name

Block palette

Since the turtle graphics will be removed, the Pen and Motion tabs are no longer needed and will also be removed.

All of the operations outlined above in Graph Algorithm Primitives must be available as blocks, most likely under the Operators tab.

To discuss: what to do with Looks and Sensing tabs (user input, effects during iteration),

To discuss: usefulness of programmatically creating standard graphs; which standard graphs to include.

---

• preliminary design document for discussion with team

  • underlying graph library: JSNetworkX
  • graph layout library: use D3 for rendering (can we supply images for nodes and edges?)
  • any other primitives (e.g. stack, queue, priority queue?)
  • gui mockup (already have)
    • small-scale manually drawn graphs: graph display needs an add-node, add-edge, move node, delete-node, delete-edge, assign-label (to node or edge), assign-costume functionality
    • graphs that were set up by the code (using New node/edge blocks)
    • graphs that were set up following a template (e.g. regular grid, trees)
  • ideas about styling including highlighting during execution
  • example tasks: e.g. Dijkstra, Prim, topological sort
  • embedding in ibooks and other delivery frameworks

• graph API we want to expose

  • natural operations to express using blocks
  • add a new standard graph: need to be able to specify the name of one of its nodes
  • OR: need to be able to specify the attribute of all of its edges (or all of its nodes) for later retrieval, cf NetworkX subgraphs
    • if we created a tree, the block might return its root, which we can then name
    • we need to be able to access all nodes of a subgraph

• applications

  • finite state machine? (plays music?)

• remove the pen and motion tabs

• milestones

  • 1 October: draft of the design document
  • 15 October: some chunk of the design is agreed, and work is underway
  • 1 November: some components have been prototyped
  • 15 November: something to show at