auroraptor / sugiyama-algorithm

A layered approach for optimal directed graph visualization with minimal edge crossings, based on the innovative method developed by Kozo Sugiyama.

📊 Coding Challenge Solution

It is a React application written in TypeScript. The application is structured to meet the following requirements:

1. Fetch a list of available graphs from /api/graphs via a GET request.
2. Fetch the selected graph data from /api/graphs/:id via a GET request.
3. Organize nodes into columns.
4. "Untangle" the connections between the columns of nodes using the Sugiyama algorithm.
5. Render the graph into the DOM using minimal inline styling and SVG for edges.

For more details about the original challenge, read through this file.

Getting started

1. Clone this repository

git clone [email protected]:auroraptor/df_designer_frontend_coding_challenge_solution.git

2. Navigate to the cloned directory

cd df_designer_frontend_coding_challenge_solution

3. Run npm install.
4. Run npm start to run the dev server.

Project Structure

The application logic is mainly handled in four custom hooks: useGraphsList, useGraph, useCreateColumns and useMinimizeCrossing.

• useGraphsList fetches the list of available graphs from /api/graphs.

• useGraph fetches the selected graph data from /api/graphs/:id.

• useCreateColumns and useMinimizeCrossing are responsible for "untangling" the graph. The former organizes the nodes into columns, and the latter rearranges the nodes within the columns to minimize edge crossing, implementing the Sugiyama algorithm.

Minimal inline styles are used for a cleaner look, and the graph edges are rendered using SVG.

Checklist of Submitted Features

• There is a dropdown to select one graph to show from all the available graphs.
• The selected graph is immediately rendered.
• The rendered graph is organized into columns.
• The nodes in columns are ordered such that their edges cross as little as possible.
• The graph looks visually pleasing.
• The solution passes the test suite npm test.

Extra challenge

• Make the nodes draggable with the mouse without using a library.

The extra challenge of making the nodes draggable without a library was implemented in this solution. However, in some cases, the edge rendering behavior during node dragging may be unpredictable. This is an area of active investigation, and any insights or suggestions are welcome.

Issues

If you encounter any issues or have any suggestions for improvement, please feel free to open an issue in this repository. Your feedback is greatly appreciated!

---

The Sugiyama Algorithm

The Sugiyama algorithm is a method for drawing directed graphs in a layered style with minimal edge crossings, named after Kozo Sugiyama. It works by assigning nodes to different layers or ranks and then rearranges the nodes to reduce edge crossings.

Unfortunately, a detailed resource or blog that exhaustively explains the Sugiyama algorithm for graph visualization with minimal edge crossings is hard to come by. The information seems quite scattered across various sources, including research papers, textbooks, and forum discussions.

However, a good starting point is the Wikipedia page on Layered Graph Drawing - Sugiyama's method. Also, the original paper by Sugiyama et al., Methods for Visual Understanding of Hierarchical Systems, provides valuable insights into the algorithm.