Graph Builder

Library

We decided to switch from react-d3-graph to graphin.
The main reasons why we changed the library were that react-d3-graph is very limited in the features provided and generally had many minor and major visualization errors.
Looking for an alternative library, we evaluated the two most suitable libraries we could found (State SoSe24):

1. react-digraph
2. graphin

Graphin is a React component library, which uses the graph visualization engine G6 under the hood.

Layout

The main layout idea of the graph builder consists of 3 components (as seen in Img01):

• Graph-Canvas
• Toolbar
• Left Sidebar

{width="686" height="367"}
Img01: Sample screenshot of current graph implementation

Graph-Canvas

The main component of the whole feature which takes the most space of the screen. It offers the main functionality of creating the graph consisting of nodes and edges and a button to apply algorithms on the created graph. The canvas is controlled by the toolbar component. It should also be possible to change the settings of each node/edge individually by a context menu (more on this later on).

Toolbar

As mentioned above, the toolbar main task is to control the canvas interaction and offer different operations on the graph. Since there are many different usecases, which have to be handled by the graph builder, we decided to solve the different operations by simply selecting them and not adding some (complex) clicking rules. So far it is not planned to toggle between the operations by hotkey-shortcuts, but this is definitively a feature that enables faster working.
After some evaluation, we decided to add the following operations, divided into 6 logical groups:

1. Graph creation
   • Click select
   • Add node
   • Add directed/undirected edge
   • Delete node/edge
2. Canvas interaction
   • Move canvas
   • Complex select
3. Undo/Redo
4. Node style
   • Color
   • Size
5. Edge style
   • Color
   • Size
6. Set node labels

Operations in groups 1 and 2 change the mouse clicking behavior and have their intuitive effect. The selection operation should enable the dragging of groups of nodes/edges and also applying individual settings on a subset of nodes/edges via the toolbar or context menu. Changes to the style of elements (groups 3-6) are applied to all selected nodes/edges. The node/edge style settings are also applied to newly created nodes/edges.
The icons used are fairly descriptive of what the operation should do, but especially for first time users they should also display a hint while hovering over them. Img04: Toolbar operations grouped by functionality (blue: currently selected)

Left Sidebar

The sidebar should contain operations related to the view of the graph(-canvas). It is currently split into the following two groups:

1. Graph auto layout
2. Graph canvas view
   • Zoom
   • Fit view to the graph
   • Fullscreen

{width="27" height="133"}
Img05: Current left sidebar split into two groups

Graph Information

It should be possible to access information about the graph e.g. whether it has negative edges or is a complete graph. This is currently done by hovering over the information icon in the top right corner as seen in Img06.

{width="226" height="252"}
Img06: Graph Information shown when hovering over the information icon

Context Menu

Not really considered as main components, the context menus still offer a lot of functionality to customize the graph.
There exists a special context menu for nodes and one for edges and both are "triggered" by right-clicking the specific element.
A context menu offers settings which are only applied to the specific element. For nodes this could be e.g.

• color
• size
• shape
• ...
  and for edges
• toggle directed/undirected
• color
• weight
• ...

Both context menus also offer a delete option, by clicking on the trashcan symbol (as seen in Img07). Deleting a node also removes all the edges which have an end on that node.
Generally, we decided to directly apply the changes and not use an "apply button". These changes are applied to the node/edge the context menu was openend from and other selected nodes/edges.
{width="188" height="247"}
Img07: Current node-context menu of the selected node

Code

Graphin and G6 Library

As mentioned in the beginning Graphin uses G6 under the hood and many operations manipulating the graph e.g. adding/removing edges, changing style of nodes/edges etc. rely on functionality from G6. The documentation is a decent starting point to look for information if needed.

Store

The graph builder offers many different operations, which also might depend on or exclude each other. To handle this common problem a state machine is usually used. It offers the advantage of bundling all states in one file therefore it cleans up other files and offers a more understandable and maintainable code base.
Components which depend on specific states are able to load the required flags and methods to change the state machine.

For this reason a folder ./stores is created, which contains the graph-builder store. This store should contain all graph builder depending settings and should also apply the business logic on these. To add new states and functionality just follow the current code layout.

History State

One special usecase is that of resetting changes that are currently applied on the graph. To handle this usecase we introduced a historyState, which manages the last changes to the graph (see useHistoryState). Currently, the file is placed in the ./hooks folder.
This file basically handles 2 stacks (past, future) and a present state and manages the applied operations by shifting them between the stacks.
To use this historyState, a facade pattern was added such that it can be easily used by calling undo, redo and set.
Currently, the component GraphAutoSave adds a new historyState after applying an operation by adding an event listener:

useEffect(() => {
[...]
	graph.on(eventName, updateGraph);
[...]	
}, [graph]);

function updateGraph(): void {
        if (graph !== null) {
	           setGraphData(graph.save());
        }
}

Graph Component

We build a Graph Wrapper component around the graphin library. This component initialises the Graphin component with a few styling defaults and guarantees that a weird bug in Graphin is fixed where the graph just did not show.

This component should be always the wrapper for any code that will deal with the graph. It is used by the Graph Builder as well as the basic visualiser.

This wrapper component (or to be more specific the Graphin one) offers a context which allows us to manipulate the graph via the underlaying G6 library. We decieded for a code structure that added dedicated independent behaviour components to this wrapper that use this context.

<Graph props={...}>
    <GraphAddNode />
    <GraphProcessParallelEdge />
    <GraphAutoSave />
    <GraphEventListeners onNodeClick={() => console.log("do anything")} />
    <AnotherGraphBehaviourComponent />
    ...
</Graph>

We build a lot of these components for the visualizer and the builder but you can reuse them anywhere else, where you deal with the Graphin Library and the Graph wrapper.

The inside of such a component may look like this:

/**
 * This component extracts the graph from the GraphinContext and hands it to the given callback function.
 * @constructor
 */
interface IGraphGetGraph {
	callback: (graph: GraphinContextType) => void;
}

function GraphExtractGraphObject({ callback }: IGraphGetGraph): React.JSX.Element {
	const graph = React.useContext(GraphinContext); // Load the GrapinContext to manipulate the graph

        // On mount the code is executed which will pass the current graph as prop to a callback function
	useEffect(() => {
		if (graph !== null) {
			callback(graph);
		}
	}, []);

        // We don't want to render anything, therefore we render an empty fragment (which will not be shown in the dom)
	return <></>;
}

export default GraphExtractGraphObject;

Custom Nodes

To create a new NodeType (in GraphCustomNodes.tsx):

1. Add the node to the list of customNodes with all the attributes: keyshape, "halo-shape", "shadow-shape", label, badge, and bagesLabel.
2. Create a Path function for the keyshape, "halo-shape", and "shadow-shape" of the node.
3. Add the new node to setNodeShape and implement the change into it.
4. Add the new node to setNodeSize and implement the size change. For further docu look here or here

Storage of graphs in local storage

The graphs that are created in the graph builder are automatically saved to the local storage of the browser. This is persistent over several sessions in the same browser as long as the user do not deletes its session.

In the local storage we have an object that holds all ids for the graphs stored in the local storage. This is the graph-locator. The id of the graph is used as key to store the graph in the local storage. With this key we can access the graph and its metadata:

export interface IGraphStorage {
	id: string;
	graph: GraphinData;
	name: string;
	createdAt: Date;
	updatedAt: Date;
        // Build for a specific algorithm in the visualiser
	restrictedToAlgorithm: string | undefined;
}

And this is then loaded to the builder or visualiser to show the graph.

An example item looks like this: