Bright Paths (Teaching MST)

The purpose of Bright Paths is to teach students about Minimum Spanning Trees (MSTs). Node A is the source and all of the other nodes have a certain weight (cost) to get to them. This teaching aid shows that cost by dimming each node, depending on the cost to that node. I plan on talking about the nodes as if they are stores that need deliveries and depending on the path that is taken, the cost of light (weight) will be too great. The result of this is an LED that is either dim or off depending again on the weight. Overall, a great way to simplify this problem for students. This problem is also known as the Traveling Salesman Problem.

Supplies

• Foamcore to hold your MST
• Some Jumper Wires to connect your beadboard to the MST
• Some Jumper Wires to connect the Arduino to the breadboard
• Eight LEDs, of the same color, to represent nodes
• Eight 220ohm Resistors for the LEDs
• An Arduino to control the Brightnesses
• A Shift Register to gain more PWM outputs

Tools

• Hot Glue Gun to hold the LEDs
• Art Supplies to draw the MST
• Computer for programming

1. I printed out one from an old textbook of mine and poked holes, through the nodes on the print, on the foam core.
2. I drew the edges with their respective weights on the foamcore also labeling the nodes A-H.
3. I pushed the LEDs through the board (on top of the nodes) keeping the long pin facing up so I knew what pin to send the signal to later. Also, pushing the pins down to hold them in place.
4. Hot glue the LEDs in place.
5. Put the female to male wires on the LED pins. I did lighter colored wires on our high pins, or the ones facing up.

Sparkfun has a great guide for the shift register and you can follow this for all of the wiring. The only difference is that the LEDs are wired in by the long jumper cables, not directly to the board. For my code, pin 0-7 on the shift register line up with A-H on the MST.

The code's purpose is to change the brightness of the LEDs based on the weights of nodes. In the picture to the right, it shows the wgtA through wgtH. These are the values that you can change in order to show the amount of weight on a certain LED. The change in brightness is achieved by:

sr.set(ledA, 255/wgtA*1.1) 

This line sets the led to the max brightness divided by weight times an amount to keep light visible. The brightness can then go down as the weight increases and this is done for every LED.

I started off this project with four blue LEDs and four green LEDs but I ran into a problem when trying to compare brightnesses. I fixed this by finding four more blue ones but just keep this in mind when picking LEDs. I also need have to carry the Arduino, breadboard, and laptop separately so making an enclosure to hold the Arduino and breadboard would be a great future improvement. It would also be cool to add animations to the LEDs to help visualize what path is being taken. Overall, a great way to show how MSTs work and I look forward to using it more.