HW2: Distributed Breakout Analysis

In this homework you will do a bit more NetLogo programming and explore both NetLogo's ability to analyze a simulation as well as Distributed Breakout's limits at solving problems.

You will start by downloading my breakout.nlogo file, which ia a slightly updated version of the one I wrote in this video. Note that this is a simplified version of breakout since each link has only one weight, whereas in the real algorithm each node has a weight associated with each edge (so, two weights per edge). But, I think the basic functionality is the same, at least for the purposes of this exercise.

This homework will have several parts.

1. Graph Generation

In the code I gave you, when you click 'setup' the graph generate is a random graph: num-edges pair of nodes are chosen at random and an edge attached between them (if one was already there, no edge is added). You will modify the code to also generate graphs that use preferential attachment.

Specifically, first create num-nodes nodes, then create num-nodes * edge-ratio (a number between 1 and 10, from a slider) edges, each one created by picking two nodes chosen with a probability proportional to their degree (number of incident edges). For example, if there are 3 nodes, one with two edges and the other two with one edge each (the graph is a line) then the one with two edges gets chosen with probability 2 / 4 = 1/2, while each other two nodes is chosen with probability 1/4. The denominator is always the total number of edges and the numerator is the degree for that node.

You will add a switch to your model to select between the two topologies (random vs. preferential attachement).

2. Graphs with a Coloring

You will then add a toggle switch to your model solvable? If it is false then you generate the graph as before. But, if it is true then the graph you generate will have a solution.

The way you ensure your graph has a solution is simply by giving each node a random color to start with and then making sure you only connect it to other nodes that have a different color. You will need to make modifications to the two previous graph-generation methods.

3. How good is Breakout Anyway?

In this last part you will implement some methods that will plot some nice line charts to show how well breakout works.

The first button will plot generate a plot where the x-axis is the number of nodes (say from 5 to 50, or some suitable range) and the y-axis is the average number of steps (over 10 runs) that breakout took to find the solution. In this test all graphs generated are guaranteed to have a solution (using the method from step 2).


The second button will generate a plot where the x-axis is the edge-ratio, from 1 to 10 and then plot the average number of constraint violations (over 10 runs) after running breakout for 10 steps. The graphs generated for this test will be determined by the settings in the buttons.

Email me the .nlogo file by Monday, February 11 @10am.