Introduction

Thank you for joining the pilot!

Today, you will be testing SYGA(See Your Graph Algorithm), our in-house graph algorithm visualization software. There is a lot of room for improvement and that is why we need your help!

Some explanations are in order

  1. With our visualizer, you can set up the graph structures and the visualization logic in the setup portion of the algorithm. You don't need to worry about this. We already did it for you. Just take care to modify only the parts where it is commented that you should modify.
  2. With every exercise, there is a goal - whether it is to modify the code to get some visualization outcome or to predict what the algorithm will do visually.
  3. You can accomplish this by manipulating some property of G. For example G.nodes[u]['some_property'] = value_a Don't worry. We explain what to change for each exercise.

Let's get into it!

The explanation are in the page itself. Go here

Cycles are fun

Go here Your goal is to detect a cycle in this graph using depth-first search. We have already setup the graph + the coloring functions for you.

Before you modify it, run it once! It visualizes vanilla DFS.

Modify only the dfs function and how it is called. For instance, it is allowed to add additional parameters and call it like dfs(1, some_arg)

When you find a cycle, call add_cycle(edges). add_cycle(edges) takes a list of 2-tuples. For example, you can pass add_cycle([(1,2),(2,1)]). Of course, pass only edges that are in the graph! Each cycle that you add will be assigned a distinct color and the visualization will reflect it.

Is it bipartite?

Go here Your goal is to determine whether the given graph is bipartite.

You may use console print statements but usage of visualization is encouraged.

In your code, you may use G.nodes[u]['partition'] = "A" or G.nodes[u]['partition'] = "B" in order to visualize the 2 partitions. A will color it red and B dark blue.