# Event Planning

## The Problem

Given a set of events, each of which having 0 or more prerequisite events, output a suggested ordering such that all of a given events pre-requisites appear before it.

## Data Representation

- Not super intuitive, but a directed graph works very well for this problem
- Directed meaning that edges are
*not*bidirectional

- Directed meaning that edges are
- Each event represents a node in the graph
- An edge going from event A to event B denotes that A is a pre-requisite of B

## Building the graph

- We can use a graph structure similar to that in week 2, with a few minor modifications (seen later)
- A full description of this structure can be found here
- Simply read in the end points and connect them on the graph

## Base Graph (without modifications)

## Algorithm for generating sequence

- There is a well known algorithm for sorting graph nodes based on pre-requisites
- Known as
*topological sort*- Produces a linear ordering of vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering

- Note that this is only possible if the given graph is a DAG (directed acyclic graph)
- Also note that more than 1 valid topological sort may exist for a given DAG

## The Algorithm

- The first step is to find all events with no pre-requisites, these will always come first in the ordering

## The Algorithm

- We add these events to a queue to be processed, and begin a loop while the queue is not empty
- For each iteration, we pop an element off the queue, and disconnect it from its children
- The reason for this is because it has already been processed, so we are “fulfilling” the pre-requisite

## The Algorithm

## The Algorithm

- We then check if this disconnecting has caused any nodes to have fulfilled pre-requisites

## The Algorithm

- Continue this way until we have processed every node in the graph
- At this point we have our ordering
- Our base graph class just needs a way of checking how many incoming edges each node has and we can implement this algorithm