Add random graph trivia questions

[jonathan-d-zhang]

Description

Created from discussion in #1491.
Me:

A question I thought would be fun is generating a random directed graph and asking people to find the shortest path between two randomly selected nodes. Variations could be solving TSP, and so on. Would need to send images though, which would require some modifications to a lot of code.

@wookie184 :

The graph idea also sounds cool, though I think it would require a bit more discussion first - I think it would be good to open a separate issue for it. It could be worth looking into if there's a Python package or API that could handle converting a graph to an image so we don't need to worry about installing graphviz.

Reasoning

These questions would be fun and cool.

Proposed Implementation

1. Add a dynamic_id question in the CS section
2. Add question list as constant. Questions asked could be:

• Find the shortest path between two nodes.
• Find the longest path between two nodes.
• Find a minimal spanning tree.
• Solve TSP given a start node.
• Simpler ones like "is this connected", "how many edges", "find a path from source to destination"
  Each of these would have an associated function for validating a given answer.

3. Create a function to generate a Erdos-Renyi random graph suitable for each question. E.g., don't pick a disconnected graph for solving TSP. https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model.
4. Create function for generating image representing the graph.

Functionality exists to send images already, but it would need to be slightly modified, since the current code only supports sending via URLs read from the config.

The "proper" way to generate the images would be via graphviz. We would use pygraphviz to interface with a graphviz installed in the container. Would require modifying the Dockerfile to install graphviz.
 

Additional Details

Performance

Should be fine: graph sizes will be small, furthermore we don't need to precompute answers for computationally hard questions, we only need to validate. p != np or something.

Alternative impls

• We can install networkx to generate LaTeX that uses tikz, and use the existing LaTeX api that we use for the .latex command. (kinda reasonable)
• Alternatively, we can try to avoid the extra dependency by generating LaTeX ourselves. (sounds really annoying)

These two should work, the LaTeX api we use supports tikz.

Would you like to implement this yourself?

• I'd like to implement this feature myself
• Anyone can implement this feature

[wookie184]

Thanks for writing up a detailed issue. I think adding graphviz for this is fine, and is the best option here. Marked as approved, feel free to work on this.