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 edge from nodes
  • Assume edge is from first to second node for directed graphs
• Get/set node/edge attribute
• Get nodes/edges with attribute
• Get subgraph from nodes/edges
• Contains given node?
• Undirected graphs
  • Get neighbors of node
  • Is connected?
• Directed graphs
  • Get adjacent nodes of node
  • Get incident nodes of node
  • Is strongly connected?
  • Is weakly 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, under a new Graph tab.

The Looks and Sensing tabs will be purged of blocks which can't be repurposed into meaningful operations on graphs. (Things like user input and minor visual effects will be retained.)

For the sake of being able to compare algorithms on different graphs without much effort, there will also be blocks for creating instances of parameterized "standard" graphs. We will at least include:

• r-ary trees
• complete graphs
• random graphs
• cycle graphs
• 2D grids
• star graphs
• path graphs
• wheel graphs

Storage and retrieval

In order to present and analyse more interesting subjects (e.g. social network graphs), we need to be able to load pre-made graphs. To this effect, there will be items in the File menu to "Export graph" and "Import graph". The latter will ask for a URL to a graph file which will then be loaded into the workspace.

At the time of writing, JSNetworkX does not have any of graph read/write modules ported. However, the JSON module is not very complex and should be very easy to port. As such, we are mainly interested in serialising to JSON. This will also be necessary for save/load within the Snap! environment.

• 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 CS4HS