NB: Da alle oppgaver for denne uken er ganske direkte relatert til Oblig2, og hver enkelt student skal skrive sin egen løsning for Oblig2, vil det IKKE bli utdelt løsningsforslag for disse oppgavene. I tillegg er dette sannsynligvis det siste oppgavesettet for semesteret. Gruppemøtene vil likevel fortsette fram t.o.m. uken før innlevering av Oblig2.

Presisering av Punkt 2.1 'Valg av Drosje' for Oblig2: Drosjen som skal velges av ditt program til å betjene en ordre fra A til B med starttidspunkt t skal kjøre fra sin nåværende holdeplass til startholdeplassen A langs den raskeste ruten mellom disse to holdeplassene. Blant alle de drosjene som kan rekke fram i tide skal man velge den drosjen for hvilken denne raskeste ruten har kortest avstand. Et eksempel: Anta vi har kun 3 drosjer D1, D2 og D3 som er ledige på hhv holdeplasser H1, H2, H3, fra hhv klokken l1, l2 og l3. Anta raskeste ruten fra H1, H2 og H3 til A tar tid hhv t1, t2 og t3, og at disse tre rutene har avstand hhv a1, a2 og a3. Da har vi all informasjon vi trenger for å avgjøre hvilken av disse 3 som skal betjene ordren. Om f.eks. l1+t1 > t så kan drosje D1 ikke brukes, den rekker ikke fram. Om både D2 og D3 rekker fram i tide, så skal D2 betjene ordren om a2 < a3, D3 om a2 > a3, og valgfritt om a2=a3.
 

Oppgave 1

1. Se på javadoc for denne klassen, og angi hvilke klasser SILGraph utvider (extends) og hvilke interface den implementerer. Forsikre deg om at du vet forskjellen på et 'interface', en 'abstract class', og en 'class'.
2. Lag et testprogram som bruker metodene incidentEdges(Vertex v), outAdjacentVertices(Vertex v)  og opposite(Vertex v, Edge e). Se f.eks. Java-kode på side 406 i læreboka som bruker incidentEdges.

Oppgave 2

1. Vi skal utvide oppgave 1 fra oppgavesett 7 med noen flere algoritmer for vektede grafer.  Modifiser først metoden readGraphFromFile slik at den nå leser inn filer med følgende format:

 

 

v11 v12 w1
v21 v22 w2
.
vm1 vm2 wm

vi1 og vi2 har samme mening som i oppgavesett 7, men i tillegg har vi en vekt wi for hver kant. Testfilene fra oppgavesett 7 men med vekter + noen nye testfiler finner du her.
 

2. Implementer Dijkstras algoritme for å finne korteste sti mellom to noder x og y i grafen G, programmer for eksempel en metode

 

 

Path Dijkstra_SPSS(Graph G, Position x, Position y,
                         Comparator c)

der Path er en klasse som inneholder:
- en sekvens av posisjoner som tilsvarer den korteste stien.
- et objekt som tilsvarer kostnaden (vekten) av hele stien. I testfilene er vekten et heltall, så her vil Path inneholde for eksempel et heltallsattributt.
 

3. Test algoritmen fra punkt 2 på testfilene lest inn med metoden fra punkt 1.

Oppgave 3

• Tid: for å representere tidspunkt
• CpTime: inneholder statiske metoder for å gjøre operasjoner, som f.eks. sammenligning og aritmetikk, på objekter av type Tid
• CpTid: Comparator for Tid-objekter

1. Oppretter et Tid-objekt for et gitt tidspunkt
2. Skriver ut et tidspunkt for et Tid-objekt
3. Skriver ut dagen for et tid-objekt
4. Legger sammen to Tid-objekter
5. Finner det største av to Tid-objekter
6. Finner ut hvor mange timer det er i 1000 minutter