C++ only Dijkstra Algorithm, graphs and graph algorithms , using STL sets

Objctivs: 1) Implmnt graphs and graph algorithms; 2) Us STL sts.

Ovrviw: Writ a class that implmnts a graph and oprations that ar carrid out on graphs. Both undirctd and dirctd graphs must b supportd.

Projct dscription: Th program should hav a class that implmnts a graph, consisting of distinct vrtics and dgs, as wll as graph oprations that may b prformd on graphs. In addition to constructors for graphs and dgs, functionality will includ dpth-first graph travrsal, and th application of Dijkstras algorithm to dtrmin th shortst path. Th implmntation will us STL sts to stor vrtics for calculating th singl-sourc shortst path using Dijkstras algorithm.

Rquirmnts: 1. Your program must b split into 3 fils. Thr will b a class (with sparat intrfac and implmntation fils), and a drivr fil. Th rquirmnts for ths ar spcifid blow:

a) Th Graph class This class rprsnts a graph and oprations on graphs

Fils must b namd graph.h and graph.cpp

Class must b namd Graph

Th intrfac (hadr fil) is providd.

o You should implmnt th intrfac fil in a .cpp implmntation fil

o All data mmbrs must b of th typ spcifid in th hadr fil

o All mmbr functions in th intrfac fil must b implmntd as dclard Howvr you hav flxibility in how you choos to implmnt ach, without changing function signaturs.

Th following functions ar part of th Graph class:

printDF(int vrtx) This function should xcut and output a dpth-first travrsal of th graph, bginning with th vrtx spcifid as th argumnt. Th output simply shows ach vrtx as it is visitd.

o DijkstraPaths(int vrtx) This function dtrmins th singl-sourc shortst path for all vrtics in th graph, bginning with th vrtx spcifid as th argumnt. It must us a st to stor th cost-so-far for vrtics as thyr procssd. Th output for ach vrtx will show its total cost from th sourc vrtx, along with th prcding vrtx through which th shortst path is obtaind. For th sourc (first) vrtx, th prcding vrtx is shown as -1.

b) A drivr, or clint, fil that

Must b namd proj8.cpp

Rads an input fil namd graphs.txt that contains two graphs: on graph will b undirctd, and th othr dirctd. ach graph is rprsntd in th fil as:

o A hadr lin containing two intgrs: Th first intgr is th numbr of vrtics in th graph (minimum of 3 vrtics for ach graph); and th scond is th numbr of dg rcords that follow th hadr lin.

o ach dg rcord consists of: two intgrs rprsnting a From vrtx and a To vrtx; a doubl for th dgs wight or cost; and a string with ithr valu tru or valu fals (cas snsitiv) that indicats whthr th dg is dirctd (tru) or not.

o Not th following rgarding dg rcords:

Vrtics ar numbrd from 0 to numbr of vrtics minus 1.

dg rcords bgin with From vrtx 0, and prsnt ach To vrtx in ordr (s sampl fil and output)

Undirctd dgs hav a singl dg rcord nding with th fals string. Dirctd dgs nd with tru. x: an undirctd dg btwn vrtx 0 and vrtx 2 with wight 5.5 will b stord as: 0 2 5.5 fals

Instantiats th two graphs by invoking th singl argumnt constructor (with th numbr of vrtics) Th graphs should b instantiatd in sparat variabls.

For ach graph (in turn), invoks printDF and DijkstraPaths with vrtx 0 as th argumnt. Othr valus for th starting vrtx will b tstd.

Th input fil usd to produc th sampl output is providd as a tsting aid.

2. Sampl output:

a) Th output on th nxt pag shows program xcution with two graphs rad from th input fil. Graph 1 is a dirctd graph, whil Graph 2 is undirctd.

Graph 1 dge to 1 weight 2 true dge 0 to 3 weight 1 true dge 1 to 3 weight 3 true dge 1 to 4 weight 10 true dge 2 to 0 weight 4 true dge 2 to 5 weight 5 true dge 3 to 2 weight 2 true dge 3 to 4 weight 2 true dge 3 to 5 weight 8 true dge 3 to 6 weight 4 true dge 4 to 6 weight 6 true dge 6 to 5 weight 1 true epth-First Traversal from vertex : isiting vertex 0 Uisiting vertex 1 Uisiting vertex 3 Uisiting vertex 2 Uisiting vertex 5 Visiting vertex 4 Uisiting vertex 6 hortest path from vertex to: Uertex cost: 0 through vertex -1 Uertex 1 cost 2 through vertex 0 Uertex 2 cost: 3 through vertex 3 Uertex 3 cost: 1 through vertex 0 Uertex 4 cost 3 through vertex 3 Uertex 5 cost: 6 through vertex 6 Uertex 6 cost: 5 through vertex 3 Graph 2 dge 0 to 2 weight 7 false dge to 4 weight 9 false dge 1 to 2 weight 5 false dge 1 to 5 weight 6 false Edge 2 to 3 weight 1 false dge 2 to 5 weight 2 false dgre 3 to 5 weight 2 False Edge 4 to 5 weight 1 false epth-First Traversal from vertex 0: Uisiting vertex 0 Uisiting vertex 2 Visiting vertex 1 Uisiting vertex 5 Visiting vertex 3 Visiting vertex 4 hortest path from vertex to: Uertex cost: 0 through ertex-1 Uertex 1 cost: 12 through vertex 2 Uertex 2 cost: 7 through vertex 0 Uertex 3 cost: 8 through ertex 2 Uertex 4 cost: 9 through vertex 0 Uertex 5 cost: 9 through vertex 2