java

GraphConversionProject

Overview

Forthisprojectyouwillwriteaprogramwhichconvertsagraphstoredusinganadjacency matrixtoagraph storedusingadjacency lists.  Agraphisasetofverticesandasetofedges.  Figure1isanexampleofagraph withthecirclesrepresenting theverticesandthelinesconnecting verticesrepresenting theedges.  Twovertices are adjacenttoeachotherifthere isanedge connectingthetwovertices.  Forexample,verticesAandEinthe graphoffigure 1are adjacent.  Avertexcanbeadjacenttoitselfifthereis anedgewhichstartsandendsatthat same vertex.

A                                           E

B                                            D

C

Figure1.

Anadjacencymatrixisonemethodofrepresenting theedgesofagraphinacomputerprogram.  Thenumberof columnsintheadjacencymatrixisequaltothenumberofrowsintheadjacencymatrix.   Eachrowinthe adjacencymatrixcorrespondstoauniquevertexinthegraph.   Eachcolumnintheadjacencymatrixalso corresponds toauniquevertexin thegraph.

Eachelementintheadjacencymatrixhasavalueof0or1.  Avalueof0fortheelementmeansthere isnoedge betweenthevertexthatrepresentstheelement’srowandthevertexthatrepresentstheelement’scolumn.Avalue of 1for the elementmeansthere isanedge betweenthe vertexthatrepresentsthe element’srow andthe vertex thatrepresentstheelement’scolumn.  Theverticesforthegraphinfigure1are:A,B,C,D,andE.  Figure 2is the adjacencymatrixforthe graph in figure1.

Figure2.

Your programwillreadinthenameof eachvertexof thegraph.  Then,your programwillreadinthegraph’s adjacency matrix.  Usingthegraph’slistofverticesandthegraph’sadjacencymatrix,yourprogramwillcreate thegraph’sadjacencylists.  Eachvertexinthegraphhasanadjacencylist.  Theadjacencylistforavertexisa

listofalltheverticesadjacenttotheadjacency list’svertex.  Forexample,theadjacency listforvertexAofthe graph in figure1 is:B, D,and E.

Creatingtheadjacency listforavertexisasimpleprocess.  Examineeveryelementintherowforthevertexin theadjacency matrix.  Iftheelement’svalueis0,donothingandmoveontothenextelement.  Iftheelement’s valueis1,addthevertexforthatelement’scolumntotheadjacencylist.Forexample,creatingtheadjacencylist forvertexAinthegraphoffigure1usingtheelementsintherowforvertexAintheadjacency matrix.  The elementsinthecolumnsforvertexB,D,andE haveavalueof1.  Therefore,only B,D,andEareaddedtothe adjacencylist forvertexA.

Design

1.   Theinputtoyour program will be read from a plain textfile calledproject1.txt.  This is the statementyou’ll

useto open thefile:

FileInputStream fstream = new FileInputStream("project1.txt");

Assumingyouare usingEclipsetocreateyourproject,you’llstoretheinputfileproject1.txt intheparent directoryofyoursourcecode,.javafiles,which happenstobethemaindirectoryofyourprojectinEclipse. Ifyou’reusingsomeother developmentenvironment,you’ll haveto figureout whereto storethe input file.

Thefirstlineintheinputfilecontainsthenamesoftheverticesofthegraphwitheachnameseparatedby 1 or morespaces.  Starting on the second lineof theinputfileis the adjacencymatrixforthegraph, thesecond lineintheinputfileisthefirstrowoftheadjacencymatrix,thethirdlineintheinputfileisthesecondrow oftheadjacencymatrix,andsoforth.Theorderofthevertexnamesinthefirstlineoftheinputfilecorrespond to therows and columns in the adjacencymatrix.Thefirst vertexname corresponds to the first rowand first columnintheadjacencymatrix,thesecondvertexnamecorrespondstothesecondrowandsecondcolumn in the adjacencymatrix, and so forth.  Each value(0 or1) onalineis separated by1 ormorespaces.

Hereisasampleinputfile,  project1.txt,whichwouldbetheinputfilefor thegraphinfigure1.  Youshould createyourownexamplegraphsandtheirinputfiletoproperly testyourprogram.  Yourprogramshould makesuretheinputdoesnotproperly formatted.  Iftheinputisnotproperly formatted,youcouldproperly terminate theprogram and let the user know aboutthe input error.

2.   Makethe name of thedriver classProject1 and itshould onlycontain onlyonemethod:

public staticvoidmain(String args[]).

Themain method willopen the file project1.txtand hand off theinputto another class orclasses toperform the graph conversion process.  Therefore, themain methoditself should be fairlyshort.

3.   WriteaclasscalledVertexwhichstoresthenameofavertexinthegraph.TheonlymethodsoftheJobclass aretheget and set methods forthevertexname, the toStringmethod, and the constructorforthe class.

4.   Downloadthefile  DoublyLinkedList.javacontainingmostoftheimplementationofthedoublylinkedlist class.  Youcannotadddatamemberstoormodifythedatamembersofthedoubly linkedlistclass.  You cannotmodify thenestedprivateclassNodeofthedoubly linkedlistclass.  Youcannotmodify thenested privateclassLinkedListIteratorofthedoublylinkedlistclass.  Youcannotmodify thedoublylinkedlist classconstructorandtheclear,size,isEmpty,add(AnyType newValue),remove(int index),iterator,and getNode(int index)methods.

YouwillwritethecodeforthegetNode(intindex,intlower,int upper)method.  Thismethodreturnsthe pointertothenodewhosepositioninthelistcorrespondtothevalueoftheparameterindex.  This method shouldensure indexisa valuewhichisgreater thanor equaltotheparameter lower andlessthanorequalto the parameterupper.  Ifneeded,you canwrite additionalmethodstohelpinyour implementationof this getNode method but theymustbedefined asprivate.

Youwillwritethecodefortheadd(intindex,AnyTypenewValue),remove(Node<AnyType>currNode), get,andsetmethods.EachofthesemethodswilluseoneofthegetNodemethods.Recallfortheaddmethod, theindexcanbeavaluefrom0tosize().   Ifneeded,youcanwriteadditionalmethodstohelpinyour implementation of each of thesemethods but theymustbedefined asprivate.

5.   Yourprogramwillreadinthegraphfromtheinputfile,converttheadjacencymatrix intotheadjacencylists, oneadjacencylist(adoublylinkedlistofvertices)foreachvertex,andfinallyprinttheadjacencylistforeach vertex.

6.   DoNOTuseyourownpackagesinyourprogram.  DoNOTuseanygraphicaluserinterfacecodeinyour program.

7.   Makeyourprogramasmodularaspossible,notplacingallyourcodeinone.javafile.  Youcancreateas manyclassesasyouneedinadditiontotheclassesdescribedabove.  Methodsshouldbereasonably small followingtheguidancethat "Afunction should do onething, and do itwell."

8.   Document and commentyourcodethoroughly.