Home

Many real-world computational tasks involve networks (or graphs, e.g. finding the optimal route in a road network, finding the critical path in a supply chain, etc... Networks can be visualized and animated. There are many interesting and sophisticated algorithms involving networks. Networks provide an important and appealing entry point into computer science. We would like to extend Snap! to support graph algorithms, possibly along the lines of this mockup. The current prototype is available here.

Graph representation

We require a comprehensive graph library for efficient storage and manipulation of network 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:

• Add node/edge
• Delete node/edge
• Get edge from nodes
  • Assume edge is from first to second node for directed graphs
• Get/set node attribute
• Get/set edge attribute
• Get nodes/edges with attribute
• given node exists
• check if a graph is empty
• check two graphs are isomorphic (once JSNetworkX supports this)
• set node/edge color to C (do we want a pen interface?)
• set color of node/edge X to C
• Undirected graphs
  • Get neighbors of node
  • Is connected?
• Directed graphs
  • Get adjacent nodes of node ("outgoing")
  • Get incident nodes of node ("incoming")
  • Is strongly connected?
  • Is weakly connected?
  • topological sort of nodes

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/delete node/edge
• Modify selected nodes'/edges' attributes
• Tentative: find node by name
• (select rendering algorithm http://marvl.infotech.monash.edu/webcola/)

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 new tabs.

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.

Open Issues

• what will we name this?

  • we have cellular, scribble, enchanting...
  • avoid words based on "graph"; favour terms: network, edgy, connect, ...

• do programs pass around graph objects, or is everything added to a single global graph object?

  • note that NetworkX functions let you pass in a graph object to which the result will be disjoint-unioned
  • use cases:
    • compare two algorithms side-by-side, each running on a different graph instance
    • two algorithms operating on the same graph, e.g. competing on a playing surface (cf cellular agents)
      • we probably don't want this for a game, because "players" would take turns, which is tantamount to a single thread
    • create a forest by disjoint-unioning the trees into a single graph (what for?); doing experiments with scale-free graphs?
  • solutions:
    • one global graph per thread?
      • new graph block just adds the graph to that one (disjoint-unioned into the global graph)
        • need a block that re-initializes the empty graph (clear)
      • alternatively, new graph block replaces the existing one
    • allow versions of blocks that allow you to add a new graph to an existing graph (create a new graph inside the graph, but then how do you refer to that new graph)
    • have an unspecified graph parameter default to the global graph (for that thread?)
    • NB we can already add a new disjoint piece of graph to an existing graph just by using the addnode/addedge blocks; is there convenience in being able to add a graph to a graph

• a program could interpret a graph as an FSA; but we could consider supporting FSAs as a special type of digraph

  • related to this, will the drawing interface allow self-loops? (yes)
  • how do we distinguish graphs and digraphs in the interface: "new graph" vs "new digraph"?

• do we need a "new empty (di)graph" block? (yes)

• do we need to support conversion from graphs to digraphs and vice versa?

  • maybe, loading from CSV defaults to digraphs

• API keys and scalability

  • built-in vs school-assigned vs individual specification for API keys
    • depends on API provider

• Dictionary support in general

  • resolved through attributes

• Do we want to have distinct block shapes for nodes vs edges?

Development

• 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