Algoritmer og Datastrukturer/Datalogi C

ForelÊsning 15/10-2002

Henning Christiansen

Grafer og grafalgoritmer

Hvad mener vi med en graf?

NEJ!

Graf: En matematisk abstraktion over ting som er ≥logisk≤ forbundet med hinanden

Dagens program:

∑ Terminologi og anvendelser

∑ ReprÊsentationer af grafer

∑ Algoritme til korteste vej

∑ Algoritme til korteste vej ã med vÊgte (=omkostninger)

∑ Kort om netvÊrksplanlÊgning

o Princippet

o Skitser af algoritmer, topologisk sortering, kritisk vej m.v.

Grafer, terminologi og baggrund

Udspringer af matematisk disciplin Grafteori

Leonard Euler 1736: ≥De 7 broer i Kˆnigsberg≤ (nu Kaliningrad)

≥Er det muligt at g en tur, s man passerer alle broer, men ikke mere end Èn gang≤?

Svaret er nej... beviset baseret p abstraktion = grafer:

(Interesserede kan finde bevis p nettet eller i en bog p biblioteket)

Grafteori: Stort og spÊndende omrÂde, mange spÊndende sÊtninger ã og anvendelser!

Terminologi:

En graf bestÂr af

∑ knuder (vertices); en eller anden (abstrakt mÊngde)

{1,2,3,4}

∑ kanter (edges), en binÊr relation over knuder.

{(1,2), (2,3), (2,2), ...}

Forskellige typer grafer:

Ikke-orienteret graf:

Kanter uden retning, dvs. (1,2) â (2,1)

Orienteret graf:

Kanter har retning, dvs. (1,2) Ç (2,1), dvs. Pile

Vi taler om ind-kanter og ud-kanter for given knude

VÊgtet graf (typisk orienteret, men ogs ikke-orienteret):

Hver kant har en vÊgt (âprisâomkostningâ...)

TÊtte og tynde grafer:

TÊt: Alle kan se alle,

dvs. antal kanter â O(antal-knuder²)

Tynd: Hver knude har lille antal kanter til/fra

dvs. antal kanter â O(antal-knuder)

Eksempel 2D-strukturer uden krydsende kanter

FÊnomener i grafer:

En vej (path) fra K1 til Kn:

En sekvens af kanter (K1,K2),(K2,K3),...,(Kn-1,Kn).

En kreds/cyklus (cycle): En vej fra K til K.

Klassifikation af grafer:

∑ Acyklisk: ingen kredse

∑ SammenhÊngende: For vilkÂrlige knuder K1, K2, altid vej fra K1 til K2 eller omvendt

∑ Skov: Aldrig mere end Èn vej mellem to knuder

∑ TrÊ: en sammenhÊngende skov :)

o NB: et trÊ har altid Èn ≥top-knude≤

(burde hedde dets rod, men nu er det alts etableret)

Anvendelser

Infrastruktur/forsyningslinjer

Knuder = Byer/Forbrugere-Producenter

/Computere-Servere-Printere

Kanter = Veje/Lastbilsruter/TogstrÊkninger/Vandr¯r

/el-ledninger/datanetforbindelser

Interessante sp¯rgsmÂl:

∑ Er grafen sammenhÊngende (ellers ¯er)

∑ Billigste vej mellem to knuder

∑ Billigste vej som involverer givet punktmÊngde

SammenhÊngsgrad â et mÂl for forsyningssikkerhed:

∑ hvor mange forskellige veje mellem to vilkÂrlige punkter

RejseplanlÊgning:

Knuder = stationer/stoppesteder/adresser

Kanter = trafikforbindelser; pris = rejsetid

Ekstra komplikation: K¯replan => ventetid

PlanlÊgning af projekter:

Knuder = Produkter (=aktivitet afsluttet)

Kanter = Hvilke ting forudsÊtter hvilke andre

Hvor lang tid tager aktivitet X?

Programstrukturer:

Kaldegrafer: Hvilke metoder kalder hvilke?

∑ Fejls¯gning, optimering p compiletime

UML: Hvilke klasser benytter hvilke og hvordan (f.eks. nedarver fra, indeholder objekter fra, ...)

∑ Vedligeholdelse af programmer...

ReprÊsentation af grafer

Matrice: bool [ 5][ 5] graf

00d 0	1ss1 1	0 0	1 1	0 0
0 0	0 0	1 1	0 0	0 0
0 0	0 0	0 0	0 0	0 0
0 0	0 0	1 1	0 0	0 0
0 0	0 0	0 0	1 1	0 0

0 1

0 2

3

4

Lister:

For hver knude, en liste over dens ud-kanter

0: [1, [3, null]]

1: [2, null]

2: null

3: [2, null]

4: [4, null]

Eksempel p listereprÊsentation af vÊgtede grafer:

Hvordan var det nu med java.util.LinkedList

Constructors

LinkedList()

Constructs an empty list.

boolean add(Object o)

Appends the specified element to the end of this list.

Object getFirst()

          Returns the first element in this list.

Object getLast()

          Returns the last element in this list.

int indexOf(Object o)

Returns the index in this list of the first occurrence

of the specified element, or -1 if the List does not

contain this element.

int lastIndexOf(Object o)

          Returns the index in this list of the last occurrence of the

specified element, or -1 if the list does not contain this element.

ListIterator listIterator(int index)

          Returns a list-iterator of the elements in this list

(in proper sequence), starting at the specified position in the list.

Object remove(int index)

          Removes the element at the specified position in this list.

boolean remove(Object o)

          Removes the first occurrence of the specified element

in this list.

Object removeFirst()

          Removes and returns the first element from this list.

Object removeLast()

          Removes and returns the last element from this list.

Osv. osv.

ReprÊsentation med lister benytte i lÊrebogen

(her renset for diverse ekstrainformation og fejlcheck ved indlÊsning)

Ä Attributter har her tekstlige navne som benyttes ved indlÊs og udskriv

class Edge // start vertex given by position in list (below)

{public Vertex dest; // Second vertex in Edge

public double cost; // Edge cost

public Edge( Vertex d, double c ) {dest = d; cost = c;}}

class Vertex

{ public String name; // Vertex name

public List adj; // Adjacent vertices //liste over ud-kanter

public Vertex(String nm){name=nm;adj=new LinkedList( );}}

public class Graph

{private Map vertexMap = new HashMap( ); // String to Vertex

private Vertex getVertex( String vertexName )

{Vertex v = (Vertex) vertexMap.get( vertexName );

if(v==null)

{v=new Vertex(vertexName); vertexMap.put(vertexName,v);}

return v;}

public void addEdge( String sourceName, String destName, double cost)

{Vertex v=getVertex(sourceName); Vertex w=getVertex(destName);

v.adj.add( new Edge( w, cost ) );}

public static void main( String [ ] args )

{Graph g = new Graph( );

FileReader fin = new FileReader( args[0] ); //file name

BufferedReader graphFile = new BufferedReader( fin );

// Read the edges and insert

String line;

while( ( line = graphFile.readLine( ) ) != null )

{StringTokenizer st = new StringTokenizer( line );

String source = st.nextToken( ); String dest = st.nextToken( );

int cost = Integer.parseInt( st.nextToken( ) );

g.addEdge( source, dest, cost );};

System.out.println( "File read..." );

System.out.println( g.vertexMap.size( ) + " vertices" );

.....

}

Korteste vej mellem to knuder

ã beregner korteste veje fra startknude til alle andre knuder

a la princippet i dynamisk programmering;

vi har mÂske brug for at g via andre knuder

Version 1: Orienterede grafer uden vÊgte; vejlÊngde = antal kanter.

Datastruktur:

hver knude tilf¯jes hjÊlpevariable:

double dist; //hidtil bedst fundne afstand fra start; init=INFINITY

Vertex previous; // Previous vertex on shortest path; init=null

Metode clearAll, som initialiserer alle hjÊlpevariable i graf

global k¯ ≥q≤ over knuder som skal bes¯ges.

Princip i algoritme:

Givet knude kalde start.

F¯rst bes¯ges start;

SÂ bes¯ges alle knuder i afstand 1 fra start

ã dvs. alle som kan nÂs via Èn kant fra start

DernÊst alle knuder i afstand 2 fra start;

ã dvs. alle som kan nÂs via Èn kant fra dem i forrige skridt,

dog ikke dem som allerede har vÊret bes¯gt!

osv.

Implementation i Java

public void unweighted( String startName )

{ clearAll( );

Vertex start = (Vertex) vertexMap.get( startName );

LinkedList q = new LinkedList( );

q.addLast( start ); start.dist = 0;

while( !q.isEmpty( ) )

{ Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )

{ Edge e = (Edge) itr.next( );

Vertex w = e.dest;

if( w.dist == INFINITY )

{ w.dist = v.dist + 1;

w.prev = v;

q.addLast( w );}}}}

Sluttilstand:

Alle knuder med pÂskrevet afstand fra start.

Incl. dem som ikke kan nÂs fra start: ≥INFINITY≤

Korteste vej med vÊgte, ≥Dijkstras algoritme≤

Princip, som f¯r men ekstra komplikation i og med

∑ ikke nok med bes¯gt/ikke bes¯gt

∑ vÊgt for knude kan tÊlles ned flere gange

10 5

15 14

12 2

Vi skelner mellem

∑ fÊrdigbehandlede knuder (≥visited≤)

∑ ufÊrdige naboer til fÊrdigbehandlede knuder (≥unseen≤)

For at generalisere algoritmen fra f¯r bruger vi en prioritetsk¯, som indeholder den sidste slags.

Alle knuder tildeles fra start afstand fra startknude = uendelig.

Abstrakt algoritme:

indsÊt start-knude med afstand=0 i k¯;

while( der-er-flere-k¯ ) {

lad v = knuden i k¯en med mindst afstand... v fjernes fra k¯en;

for alle vπs naboer w, som ikke allerede er fÊrdigbehandlede,

{ hvis v.afstand + lÊngde(v--> w) < w.afstand sÂ

{ w.afstand= v.afstand + lÊngde(v--> w);

sÊt w i k¯ (hvis den ikke allerede er der; }

notÈr v som fÊrdigbehandlet }}

Hvorfor virker den?

Lad os formulere et matematisk induktionsbevis over antal genneml¯b af while-l¯kken:

Hypotesen:

∑ Afstand for alle fÊrdigbehandlede er korrekt, og

∑ Afstand for ≥ufÊrdige nabo≤ w = lgd. af korteste vej i delgraf som udover w kun indeholder fÊrdigbehandlede.

Induktionsstart, lad os vÊlge nÂr startknuden er fÊrdigbehandlet:

c1 c1

start 0

c2 c2

c4 c3 c3

c4

OK!

Antag nu at algoritmen har k¯rt korrekt op til skridt k:

v

Skridt k+1: Lad v vÊre ≥hvid≤ knude med mindst vÊgt:

vπs naboers vÊgte justeres (mÂske)

v forfremmes til fÊrdigbehandlet

1. Redeg¯re for at vπs afstand D er den mindst mulige. Men kan der vÊre en anden vej fra start til v, som er billigere? Per induktionshypotese del 2, kan der ikke vÊre en anden vej grÂ->grÂ->...->grÂ->v. Ergo m en sÂdan vej P vÊre af formen .... -> hvid -> grÂ. Kald denne hvide v1 og dens noterede afstand D1. Udfra valget af v m vi have D1 Ñ D. Kan lÊngden af P = D1 + noget-positivt s vÊre mindre end D?? Nej vel? Modstrid!

2. Redeg¯re for at de nye afstande for vπs naboer er korteste vej i delgrafen bestÂende af de gr ã nu udvidet med v. Hvis en sÂdan nabo w fÂr talt sin vÊgt ned, s er det netop fordi ny vej via v er kortere end tidligere

grÂ->grÂ->...->grÂ-> w.

Q.E.D.

Bogens algoritme i Java:

Prioritetsk¯en implementeres lidt snusket med BinaryHeap... (NB: ikke i Javas std. pakker)

BinaryHeap er en datastruktur,

∑ med underligt navn,

∑ hvis indmad vi ikke kender

men som implementerer metoderne

∑ insert(Comparable x)

∑ Comparable deleteMin( )

hvor ≥Min≤ er bestemt ved objekternes compareTo.

Problem ved denne BinaryHeap: Objekternes rÊkkef¯lge bestemmes p indsÊttelsestidspunktet.

Dvs. hvis objekt Êndres undervejs, s det pÂvirker resultat af compareTo, opf¯rer deleteMin sig ikke korrekt!!!

Teknik (lÊs: hÊsligt b¯jet s¯m):

∑ I algoritmen Êndres knudernes ≥afstand≤ altid nedad

∑ Vi vÊlger altid knude med mindst ≥afstand≤

∑ NÂr knude er valgt, sÊttes den ≥scratch≤ felt = 1 (init=0).

∑ Hvis en knude med ≥scratch =1≤ fremkommer ved deleteMin, ignoreres den.

F¯lgende ≥Path≤ objekter indsÊttes i BinaryHeapπen_

class Path implements Comparable

{ public Vertex dest; // w

public double cost; // d(w)

public Path( Vertex d, double c ) {dest = d; cost = c;}

public int compareTo( Object rhs )

{ double otherCost = ((Path)rhs).cost;

return cost < otherCost ? -1 : cost > otherCost ? 1 : 0;}}

Dijkstras algoritme for korteste vej i vÊgtede grafer ved brug af ≥BinaryHeap≤:

public void dijkstra( String startName )

{ PriorityQueue pq = new BinaryHeap( );

Vertex start = (Vertex) vertexMap.get( startName );

clearAll( );

pq.insert( new Path( start, 0 ) ); start.dist = 0;

int nodesSeen = 0;

while( !pq.isEmpty( ) && nodesSeen < vertexMap.size( ) )

{Path vrec = (Path) pq.deleteMin( );

Vertex v = vrec.dest;

if( v.scratch != 0 ) continue; // already processed v

v.scratch = 1; nodesSeen++;

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); )

{ Edge e = (Edge) itr.next( );

Vertex w = e.dest;

double cvw = e.cost;

if( w.dist > v.dist + cvw )

{ w.dist = v.dist +cvw;

w.prev = v;

pq.insert( new Path( w, w.dist ) );}}}}

Acykliske grafer

Typisk anvendelse: PlanlÊgning

0 1 2 3

0: tagspÊr

1: lÊgter

2: tagsten

3: rejsegilde

A --> B: A forudsÊtter B

Acykliske grafer nemmere at programmere om: man kommer aldrig tilbage til samme sted!

Eksempel: Topologisk sortering

at ordne knuderne i en graf i rÊkkef¯lge, s afhÊngigheder er overholdt.

≥tagspÊrene skal p f¯r lÊgterne≤

≥hvorvidt du sÊtter vinduer i f¯r eller efter tagstenene er ligegyldigt≤

Algoritme som udskriver knuderne i topologisk sorteret rÊkkef¯lge

G = vor graf;

while(flere-knuder-tilbage) {

find knude V med nul indgÂende kanter; //findes fordi G acyklisk

udskriv V;

fjern v og alle dens udgÂende kanter fra G; }

Bogens algoritme i Java (udsnit af fig. 14.32)

(fig. 14.32 blander top.sort. med en kortestevej algoritme)

Princip: hver knudes ≥scratch≤ benyttes som tÊller for antal ind-kanter

der bruges en k¯ til at holde de knuder som p givet tidspunkt

har 0 ind-kanter

LinkedList q = new LinkedList( );

// Compute the indegrees

Collection vertexSet = vertexMap.values( );

for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); {

Vertex v = (Vertex) vsitr.next( );

for( Iterator witr = v.adj.iterator( ); witr.hasNext( ); )

( (Edge) witr.next( ) ).dest.scratch++;}

// Enqueue vertices INITIALLY of indegree zero

for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); ) {

Vertex v = (Vertex) vsitr.next( );

if( v.scratch == 0 ) {q.addLast( v ); UDSKRIV v; } ;

// Loop: Remove 0-nodes from queue and count down in-degrees

while(!q.isEmpty( )) {

Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); ) {

Edge e = (Edge) itr.next( );

Vertex w = e.dest;

if( --w.scratch == 0 ) {q.addLast( w );; UDSKRIV v; }}}

Eksempel fra bogen

Korteste vej for acykliske grafer

Tricket:

Knuderne bes¯ges i rÊkkef¯lge svarende til topologisk sortering

Dvs. nÂr en knude bes¯ges, er alle dens forgÊngere bes¯gt

(og med garanti ikke Êndrer sin korteste vej)

Algoritmen for topologisk sortering med 4 ekstra linjer i stedet for udskrift:

LinkedList q = new LinkedList( );

// Compute the indegrees

Collection vertexSet = vertexMap.values( );

for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); {

Vertex v = (Vertex) vsitr.next( );

for( Iterator witr = v.adj.iterator( ); witr.hasNext( ); )

( (Edge) witr.next( ) ).dest.scratch++;}

// Enqueue vertices INITIALLY of indegree zero

for( Iterator vsitr = vertexSet.iterator( ); vsitr.hasNext( ); ) {

Vertex v = (Vertex) vsitr.next( );

if( v.scratch == 0 ) q.addLast( v ) ;

// Loop: Remove 0-nodes from queue and count down in-degrees

while(!q.isEmpty( )) {

Vertex v = (Vertex) q.removeFirst( );

for( Iterator itr = v.adj.iterator( ); itr.hasNext( ); ) {

Edge e = (Edge) itr.next( );

Vertex w = e.dest;

if( --w.scratch == 0 ) q.addLast( w );

if( v.dist == INFINITY ) continue; // on ≥island≤; avoid overflow

if( w.dist > v.dist + cvw )

{ w.dist = v.dist + cvw;

w.prev = v;}}}

Skitse af netvÊrksplanlÊgning

Udgangspunkt: En aktivitetsgraf

Knuder: Aktivitet m. forventet tidsforbrug

Kanter: ForudsÊtningsforhold

Obs: Omkostninger p knuder passer ikke ind i vores hidtidige model.

I stedet: En begivenhedsgraf:

Knuder: aktivitet-start, aktivitet-slut

Kanter. ForudsÊtningsforhold, Aktivitet m. tidsforbrug

Hvor lang tid tager projektet hvis arbejdet planlÊgges optimalt?

Kritiske vej = lÊngste vej fra start til slut

Algoritmer a la korteste vej kan tilpasses ≥lÊngste vej≤ â

for hver aktivitet, tidligst mulige slutpunkt

Yderligere algoritmer til:

Senest mulige starttidspunkt

Tidligts mulige sluttidspunkt

Hvor meget der kan slÊkkes

Yderligere forfining af modellen med ressourcer:

Aktivitet A krÊver 1 gravko m. f¯rer, 1 rendegraver m. f¯rer

Aktivitet E krÊver 1 rendegraver m. f¯rer, 1 bobcat, 5 gartnere,

3 river, 2 skovle

Vi har ialt f¯lgende ressourcer:

1 gravko, 2 rendegraver, 1 byggekran, ...

Alt dette kan behandles med algoritmer

sm forbedringer = store penge

heuristikker til at behandle usikkerheder,

robusthed for forudset og uforudsete Êndringer