#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

typedef std::size$\_$t vertex$\_$t;

typedef std::tuple weighted$\_$edge$\_$t;

$/*$ Get the source of a weighted edge.

$*$

$*$ This function returns the source of a weighted edge.

$*$

$*$ @param edge $-$ the edge

$*$

$*$ @return std::get$<0>($edg$)$

$**/$

vertex$\_$t get$\_$source$($const weighted$\_$edge$\_$t &edg$)$;

$/*$ Get the destination of a weighted edge.

$*$

$*$ This function returns the destination of a weighted edge.

$*$

$*$ @param edge $-$ the edge

$*$

$*$ @return std::get$<1>($edg$)$

$**/$

vertex$\_$t get$\_$destination$($const weighted$\_$edge$\_$t &edg$)$;

$/*$ Get the weight of a weighted edge.

$*$

$*$ This function returns the weight of a weighted edge.

$*$

$*$ @param edge $-$ the edge

$*$

$*$ @return std::get$<2>($edg$)$

$**/$

vertex$\_$t get$\_$weight$($const weighted$\_$edge$\_$t &edg$)$;

$/*$ Determine the number of vertices in the graph.

$*$

$*$ This function determines the number of vertices in the graph represented

$*$ by a vector of weighted edges. It is assumed that the number of vertices

$*$ is given by the largest source or destination vertex in the list of edges

$*$ plus one.

$*$

$*$ @param edges $-$ a vector of weighted edges defining a graph

$*$

$*$ @return the number of vertices in the graph represented by edges

$**/$

unsigned int get$\_$vertex$\_$count$($const std::vector &edges$)$;

$/*$ Reads weighted edges from a file.

$*$

$*$ This function reads weighted edges from filename and returns them as a

$*$ std::vector. each line of the file is assumed to be of the

$*$ form $"$src dst wt$"$ where src is the source vertex, and dst is the destination

$*$ vertex, and wt is the weight of the edge. All vertices are assumed to be

$*$ unsigned integers that can be stored as a std::size$\_$t $($i$.$e$.,$ in a vertex$\_$t$).$

$*$ Duplicate edges found in the file are ignored.

$*$

$*$ @param filename $-$ name of the file to read

$*$

$*$ @return a vector of edges read from filename

$*$

$*$ @throws std::runtime$\_$error $-$ thrown if there is an error reading the file

$**/$

std::vector read$\_$graph$($const std::string &filename$)$;

$/*$ Solves the traveling salesman problem by brute force.

$*$

$*$ This function solves the TSP via brute force. It accepts a vector of

$*$ weighted edges and count of the number of vertices. These two values

$*$ together define a weighted graph.

$*$

$*$ @param edges $-$ a vector of weighted edges in the graph

$*$

$*$ @param n$\_$vertices $-$ the number of vertices in the graph;

$*$ the vertices are $0...$ n$\_$vertices$-1$

$*$

$*$ @return the cost of the minimum Hamiltonian cycle or infinity if none exists

$**/$

double TSP$($const std::vector &edges, unsigned int n$\_$vertices$)$;

double TSP$($const std::vector &edges, unsigned int n$\_$vertices$)\{$

$/*$ IMPLEMENT THIS FUNCTION $*/$

double min$\_$cost $=$ std::numeric$\_$limits::infinity$()$;

return min$\_$cost;

$\}$

vertex$\_$t get$\_$source$($const weighted$\_$edge$\_$t &edg$)\{$

return std::get$<0>($edg$)$;

$\}$

vertex$\_$t get$\_$destination$($const weighted$\_$edge$\_$t &edg$)\{$

return std::get$<1>($edg$)$;

$\}$

vertex$\_$t get$\_$weight$($const weighted$\_$edge$\_$t &edg$)\{$

return std::get$<2>($edg$)$;

$\}$

unsigned int get$\_$vertex$\_$count$($const std::vector &edges$)\{$

unsigned int n$\_$vertices $=0$;

if$(!$edges.empty$())\{$

std::set vertex$\_$set;

$/*$ add the source vertices to vertex$\_$set $*/$

std::transform$($

edges.begin$(),$

edges.end$(),$

std::inserter$($vertex$\_$set, vertex$\_$set.end$()),$

get$\_$source

$)$;

$/*$ add the destination vertices to vertex$\_$set $*/$

std::transform$($

edges.begin$(),$

edges.end$(),$

std::inserter$($vertex$\_$set, vertex$\_$set.end$()),$

get$\_$destination

$)$;

$/*$ get the largest vertex from vertex$\_$set and add $1*/$

n$\_$vertices $=*$std::max$\_$element$($vertex$\_$set.begin$(),$ vertex$\_$set.end$())+1$;

$\}$

return n$\_$vertices;

$\}$

std::vector read$\_$graph$($const std::string &filename$)\{$

std::vector edges;

std::ifstream file$($filename$)$;

if$($file$)\{$

$/*$ read edges into a set to remove duplicates $*/$

std::set edge$\_$set;

vertex$\_$t src$,$ dst;

double wt;

while$($file $>>$ src && file $>>$ dst && file $>>$ wt$)\{$

edge$\_$set.insert$($ weighted$\_$edge$\_$t$($src$,$dst$,$wt$))$;

$\}$

$/*$ check if there was an error reading in the file $*/$

if$($file$.$bad$())\{//$ i$/$o error

std::ostringstream oss;

oss $<<$ filename $<<"$: $"<<$ strerror$($errno$)$;

throw std::runtime$\_$error$($oss$.$str$())$;

$\}$

else if$(($file$.$fail$()$ && $!$file.eof$()))\{//$ conversion error

std::ostringstream oss;

oss $<<$ filename $<<"$: error reading file";

throw std::runtime$\_$error$($oss$.$str$())$;

$\}$

$/*$ copy the edges read to the edges vector $*/$

std::copy$($edge$\_$set.begin$(),$ edge$\_$set.end$(),$ std::back$\_$inserter$($edges$))$;

$\}$

else $\{//$ error opening f