Assignment — Sugiyama Layout

​This repository is your starting point for the assignment and includes instructions below.

Aim of the assignment

The goal of this assignment is to re-familiarize you with the classic Sugiyama layout algorithm for layered graph drawing, as well as help you get a more complete understanding of its intricacies. As the best way to learn all the ins and outs is to build it yourself, in this assignment you'll create your own implementation of Sugiyama.

About GitHub Classroom

Accepting an assignment

1. Click the GitHub Classroom link on the Canvas assignment to set up a git repository for you to work in.

   • The first time you accept an assignment for the course, you will need to connect your GitHub account with our roster imported from Canvas. If you do not have a GitHub account yet, you will need to create one before connecting it.

   • Your interface will look something like this.

2. Accept the Assignment.

3. Wait for it to create a repository.

4. Click on the link to where the Assignment repository has been created.

Assignment instructions

Follow the instructions included in this README.md file at the root of your repository.

GitHub nicely displays this for you when you go to the repository online. Many text editors will also display previews for you. E.g., Visual Studio Code has a nice Markdown preview and extensions.

Invitation links vs. forking

The GitHub Classroom invitation link we provide is creating a copy of a template repo we created that gives you a starting place.

Do not just fork this repo or use it as a template directly! Instead, use the GitHub Classroom invitation link.

Instructions

Setup instructions

1. Clone the repo.

2. CD to the repo directory.

Add your documentation here!

Run instructions

Add your documentation here!

Implement

Write the code to implement Sugiyama's layout and visualize the result for a graph.

You're welcome to use any language you like for the algorithm and any visualization frontend (including printing a beautiful text version of the layout to the terminal), as long as you can get all the code into this repo.

Here are three good references on how the algorithm works:

Sugiyama et al. (1981) Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics. doi: 10.1109/TSMC.1981.4308636. The original article.

Sugiyama (2002) Graph drawing and applications for software and knowledge engineers. doi: 10.1142/4902 Canvas access-controlled PDF. In particular, starting page 61.

Healy & Nikolov (2013) Hierarchical Drawing Algorithms. Author PDF. Mixed in with other methods.

Note that we expect you to implement all four steps of the algorithm:

1. Cycle removal
2. Layer assignment
3. Vertex ordering
4. Final positioning

Please see the /data folder for example data you can use in GraphML and GraphViz formats. The data is originally in GraphML from the Rome-lib dataset. Your resulting visualization should be something like this:

This image was generated using Tulip and it's included Sugiyama layout from OGDF, described here.

For testing, you're welcome to use other graphs from Rome-lib, or the exciting Unix history graph (GML file, not the same as GraphML).

Document

Add sufficient documentation to the top of this README.md file under Setup Instructions and Run Instructions so that we can install and run your code and view the output.

Add a screenshot of the output

In case we can't run your code for some reason, take a screenshot of your output and include it in this README.md file here:

Put your image here!

Commit and push your code

1. Make sure to add all your required files to the git repo, and not any temporary or unnecessary files. You can use a .gitignore file to avoid accidental commits.

2. Finally, commit all your local files and push them to the remote repository on GitHub which was generated by GitHub Classroom.

Submission instructions

1. Ensure that:

   • all of your required files and your final image are pushed to the remote repository on GitHub which was generated by GitHub Classroom.

   We will grade based on what is available in that repository.

2. Submit the URL of your GitHub Classroom-generated repository (not a GitHub Page — we're not using it for this assignment anyway) to the associated assignment on Canvas. Do not submit a link to a personal repository. It must be within our class GitHub organization.

Grading

Please see the rubric on Canvas.

Late Policy

Partial credit up to 24 hours late as detailed on the syllabus.