Introduction:

The attached file code is based on a train game about tracks and assigning your trains, and then commuters pop up wanting to go somewhere. The code will involve graph algorithms and data structures. Your task is to create a simpler and more abstract representation of the problem. You will be given a set of stops, their neighbourhood type and x,y coordinates. A stop will be represented by the following struct:

typedef struct stop {

int type;

int x;

int y;

} Stop;

You will also be provided with the following function that generates an array of stops.

Stop* get_stops(int num_stops);

The main task is to build a new graph using a subset of these edges that connects all stops. You will attempt to build a track of minimal cost, where the cost is a function of the edge weights (the cost of building the track) and the time taken for simulated commuters to complete their journey. You will be provided with a function that calculates the cost for a given graph:

float get_score(Graph *self);

This function calculates the cost for edges, and then simulated 1000 random trips. Each trip is from a random stop to the nearest stop of a random type. It needs to have a working Dijkstra’s algorithm to work properly (but we don’t need to worry about this at this stage).

YOUR TASK: Converting the Data into Graph Format.

Your first task is to convert the stop information into a complete weighted graph where every stop is connected to every other stop with the weight calculated as the distance between stops. Even if you get the weight calculations wrong you will show that you know how to add edges to a graph and understand the basic adjacency list types. The distance can be calculated using

sqrtf((x1 – x2)*(x1 – x2) + (y1 – y2)*(y1 – y2));

where <x1,y1> and <x2,y2> are the coordinates of two cities (this function will be provided in the code attached).

You should store this initial graph using an adjacency list as specified below (given that this is a complete graph, an adjacency matrix might be preferred, but our algorithms are going to work with adjacency list representations, so we will stick with that). We are building an undirected graph for this problem. To represent this as an adjacency list, each edge from u->v needs to have a matching edge from v->u.

The code below will be provided for you to use.

typedef struct edge {

int to_vertex;

float weight;

} Edge;

typedef struct edgeNode {

Edge edge;

struct edgeNode *next;

} *EdgeNodePtr;

typedef struct edgeList {

EdgeNodePtr head;

} EdgeList;

typedef struct graph {

int V;

int *vertex_types;

EdgeList *edges;

} Graph;