/
Graph Visualiser Implementation

Graph Visualiser Implementation

Owned by Tim Zhang (Unlicensed)
Last updated: Aug 13, 2022
3 min read

This page outlines some practical ideas around how to implement the graph visualiser.

Note: Graph-drawing is an interesting problem in computer science, and a lot of research has been done on scalable and generalisable approaches.

How do you lay out the nodes in a ‘sensible’ way?

One method that is often used is the force-directed graph layout. There seems to exist a few libraries that support this

“While graph drawing can be a difficult problem, force-directed algorithms, being physical simulations, usually require no special knowledge about graph theory such as planarity.”

In essence:

  • Nodes will always repulse each other, like 2 positive electrically charged particles.

  • Edges will always work to 'attract' two nodes, like a spring connecting 2 electrically charged particles.

This means that densely connected sets of vertices will cluster together and sparsely-connected vertices will distribute themselves around the edges of the graph (which forms a natural-looking layout overall).

 

Some points to consider:

  • This is one of the simplest possible graph-drawing strategies that works well for small graphs.

  • Doesn’t display very large graphs well (> hundreds of vertices). This shouldn’t matter if we set a hard limit on number of vertices.

    • Also, the algorithm for force-directed layout is O(N^3) which makes it not scalable for large graphs anyway.

 

Libraries:

It would be possible (and possibly better) to not use a library. The force-directed layout shouldn’t be too hard to implement given that there are some resources for how to do it.

These are some libraries that are worth considering:

 

Core Operations to Implement

Variants of the following algorithms should be implemented for unweighted/weighted and undirected/direct graphs.

Algorithm

Requirements

Forseeable Challenges

Algorithm

Requirements

Forseeable Challenges

addEdge(u, v)

Play an animation to ‘spawn’ an edge between u and v.

 

removeEdge(u, v)

Play an animation to delete the edge between u and v.

 

bfs(v) – where v is the starting vertex.

When executed, it should highlight what the current vertex is, and what edges are being considered for traversal. They should be entered into a queue (perhaps even labeled with a number on the graph so it’s very clear).

In essence we need:

  • An animation to highlight an edge between 2 vertices u and v.

  • An animation to highlight a vertex (to mark it as visited).

  • A way to indicate the visit queue.

Needs some data structures to store references to SVGs and quickly look them up (maybe a slightly modified adjacency matrix would suffice).

dfs(v) – where v is the starting vertex.

Similar to bfs, but just substitute the queue for a stack.

Same as bfs.

addVertex(v)

Likely not worth implementing.

Play an animation to ‘spawn’ a vertex into view.

Idea: fade in the vertex at a designated coordinate or origin every time, then let the graph layout algorithm move it to a ‘correct’ place.

Should be easy, assuming we have a force-directed layout system.

Since the underlying data structure is usually an array/matrix, adding a vertex would mean replacing that data structure.

removeVertex(v)

Likely not worth implementing.

Play an animation to delete a vertex.

Idea: fade out the vertex and all its incoming/outgoing connections.

Same as addVertex.

Additional Algorithms

Algorithm

Requirements

Forseeable Challenges

Algorithm

Requirements

Forseeable Challenges

dijkstra(v) – where v is the starting vertex.

To be discussed.

Should be easier if bfs and dfs are implemented (since we can reuse the same animations).

One challenge would be showing the ‘helper’ data structures like the pred array, distances array, visited set, etc.

kruskal()

To be discussed.

It could be confusing/complicated for the user if we show the cycle-checking every time.

Same as dijkstra.

prim()

To be discussed.

 

floydWarshall()

To be discussed.

 

It would be insightful to also show the underlying representation of the list, which might be an adjacency matrix, adjacency list, or list of edges, and allow the user to toggle between them.

 

 

 

 

 

 

 

 

Related content