Layout options:

Create Nodes

To create a node, you can just click the 'add a node' button, which will create a node with the minimal id that is not in the graph. If you want to create multiple nodes, enter the number of nodes you want to create in the 'number' field.

Remove Nodes

To remove a node, enter the id of this node and click remove. You can remove multiple nodes by entering their id respectively, separated by commas, or entering the range.
Example: enter 1,2,3,4 or 1-4 to remove node 1, node 2, node 3, and node 4.

Create Edges

To create an edge connecting node src and node tg, enter the src-tg-num input box, which stands for source-target-number. If the '-num' part is omitted, it will create one edge connecting node src and node tg.
Example: 1-2-3 will add three edges connecting node 1 and 2.

Alternatively, you can create edges by selecting nodes and clicking the 'add edge(s) between selected' button. This will create edges connecting all nodes that you've selected. Or you can use the edge handle plugin: Click the "enable drawing" button below the canvas and start adding edges by simply dragging.

Remove Edges

To remove an edge, just enter the src-tg-num for this edge, where num is the number of edges connecting src and tg that will be removed. If the '-num' part is omitted, it will remove one edge connecting node src and node tg. Or you can just select all the edges that you want to remove, then click 'remove selected' button. Example: 1-2-2 means remove 2 edges connecting node 1 and node 2.

Create Graph from Adjacency Matrix / Weight Matrix

Graph can also be created from the adjacency matrix or weight matrix. The matrix must be declared as a javascript nested array format.

In the adjacency matrix, the element in ith row and jth column denotes the number of edges connecting node i and node j.

In the weight matrix, the element in ith row and jth column denotes the weight of the edge connecting node i andnode j. If weight <= 0, it means that these two nodes are not connected

Examples of creating from matrix

Matrix type	Input	Result
Weight matrix	[[0,4,3,0,0],  [4,0,4,4,0],  [3,4,0,2,4],  [0,4,2,0,0],  [0,0,4,0,0]]
Adjacency matrix	[[0,1,0,0,0,2,1],  [1,0,1,1,1,1,1],  [0,1,0,0,1,0,1],  [0,1,0,0,0,0,2],  [0,1,1,0,0,2,0],  [2,1,0,0,2,1,0],  [1,1,1,2,0,0,0]]

The whole matrix must be enclosed by a pair of square parentheses, and each row also should be enclosed by a pair of square parentheses. Rows and columns are separated by commas.

In theory, the matrix should be symmetric about the major diagonal (because the graph is undirected), yet this is not checked. My program only take the half above the major diagonal.

Context menu

A circular menu will be shown when you right click on a node, an edge, or the canvas. Thanks FontAwesome for creating these icons.

Key bindings

Algorithms

Breadth First Search

Source canvas	Result canvas	Animation
Highlight the path which the algorithm has visited	Show the tree generated by this algorithm	Traverse the nodes and edges visited by order of visits

Depth First Search

Source canvas	Result canvas	Animation
Highlight the path which the algorithm has visited	Show the tree generated by this algorithm	Traverse the nodes and edges visited by order of visits

Dijkstra's Algorithm

Source canvas	Result canvas	Animation
Highlight the minimal weight connector	Show the minimal weight connector	Trace the minimal weight connector

Dijkstra's Algorithm (Detailed)

This version of Dijkstra's algorithm will trace every single step, including the label updates.

Source canvas	Result canvas	Animation
Highlight the minimal weight connector, all temporary labels, and all permanent labels. The meaning of the labels: Note id|Temporary labels|Permanent label	Show the minimal weight connector	Trace the algorithm step by step

Kruskal's Algorithm

Find a minimal spanning tree in a given connected graph

Source canvas	Result canvas	Animation
Highlight the minimal spanning tree on the original graph	Show the minimal spanning tree obtained	Traverse the edges in the tree by order of visits

Prim's Algorithm

Find a minimal spanning tree in a given connected graph

Source canvas	Result canvas	Animation
Highlight the path which the algorithm has visited on the original graph	Show the minimal spanning tree obtained by this algorithm	Traverse the nodes in the tree by order of visits

Bridge Finding Algorithm

Find all bridges in an undirected graph. A bridge is an edge whose removal causes the number of connected components to increase.
Reference: https://www.geeksforgeeks.org/bridge-in-a-graph/

Source canvas	Result canvas	Animation
Highlight all bridges. The format of node labels is p: 'id of the parent node' 'node id'|'lowest discovery time'|'discovery time'	Show all the bridges only	N/A

Minimal Weight Cycle

Find a minimal weight cycle, which can be local (starting from a selected vertex) or global, in a connected graph with no edge of negative weights

Source canvas	Result canvas	Animation
Highlight the minimal weight cycle found	Show the minimal weight cycle found	None

Eulerian Trail/Cycle

Find an Eulerian cycle in an Eulerian graph or an Eulerian path in a semi-Eulerian graph, by Hierholzer's algorithm.

Source canvas	Result canvas	Animation
No change	Show the original graph	Traverse the nodes and edges by order of visits in the Eulerian cycle obtained

Minimal Weight Matching

Find the minimal weight matching in a weighted undirected graph by Edmonds' algorithm, also known as "paths, trees and flowers"

Source canvas	Result canvas	Animation
Highlight the matches	Show the matches	None

Chinese Postman Problem

Solve the CPP by finding the minimal weight perfect matching between vertices of odd degrees, thereby making the graph Eulerian.

Source canvas	Result canvas	Animation
Highlight all odd nodes and edges that need to be duplicated (visited twice)	Show the graph after the duplication of these edges	Traverse all nodes and edges by order of visits in the Eulerian cycle obtained on the graph after duplication of these edges

Hamiltonian Path/Cycle

Find a Hamiltonian path or cycle in a graph. If both are present, a Hamiltonian cycle is returned. The time complexity of this algorithm is exponential, and it will start to take a considerable amount of time on a graph with more than 20 vertices.

Source canvas	Result canvas	Animation
Highlight the Hamiltonian cycle obtained	Show the Hamiltonian cycle	Traverse the Hamiltonian cycle

Nearest Neighbor Algorithm

Find a Hamiltonian cycle of low but not necessarily of minimal weight in a complete graph. If a node is selected, then it will be the starting point of the algorithm. Otherwise this algorithm will be performed at every node, and the one of minimal total weight is returned. This algorithm can run in a non-complete graph, but it may get stuck.

Source canvas	Result canvas	Animation
Highlight the Hamiltonian cycle obtained	Show the Hamiltonian cycle	Traverse the Hamiltonian cycle

TSP Lower Bound

Find the lower bound for the travelling salesman problem in a graph by vertex deletion algorithm. If a node is selected, then it will be the starting point of the algorithm. Otherwise this algorithm will be performed at every node, and the one of maximal total weight is returned.

Source canvas	Result canvas	Animation
Highlight the two edges deleted and the minimal spanning tree for the remaining graph	Show the graph formed by these two edges and the minimal spanning tree	None

Third-party code and dependencies

Update catalog