[GRAPHS] Probleem met doorlopen

[Verwijderd]

Hoi!

Ik ben al een tijdje aan het knoeien om een graaf op een systematische manier te doorlopen.

Stel ik heb een samenhangende (dus geen losse delen, alles is met elkaar verbonden), gerichte (1-richtingspijlen) graaf. Nu wil ik een functie maken die de graaf zo doorloopt, zodat de pijlen een "afhankelijkheids"-betekenis krijgen: als knoop a wijst naar knoop b, moet eerst a uitgeprint (uitgevoerd, ... wat dan ook) worden om b te kunnen printen. Vergelijk het met processen die eerst moeten uitgevoerd worden, vooraleer een andere proces kan starten.

Na wat knoeien kwam ik tot volgende functie: (pseudeocode!)

code:

zet heel de array D (lengte = aantal knopen van de graaf) op false /* D[v] = true => knoop v is reeds bezocht */
knoop1 = een willekeurige knoop uit de graaf
functie (knoop1)

functie (knoop kn)
{
    D[kn] = true; /* markeer knoop 'kn' als bezocht */

    while (alle ouders (x1, x2, x3, ...) van kn) /* doorloop alle ouders van knoop 'kn' */
    {
        if (D[ouder x] == false) /* als de ouder nog niet bezocht is, ga naar die ouder */
            functie(ouder x);
    }

    printf kn; /* alle ouders zijn uitgeprint, we mogen nu de knoop zelf uitprinten */

    while (alle kinderen (y1, y2, y3, ...) van kn) /* doorloop alle kinderen van knoop 'kn' */
    {
        if (D[kind y] == false) /* als een kind nog niet bezocht is, ga naar dat kind */
            functie(kind y);
    }
}

Dit is een aangepaste versie van first-depth search van grafen (waarom? omdat je hier verschillende 'roots' kunt hebben die als eerste moeten geprint worden)

Nu werkt dit algoritme niet altijd Stel ik heb volgende graaf:



Een oplossing van deze graaf zou dus zijn: 1-3-4-2-5-6-7

Stel nu dat ik knoop '1' (ps: willekeurig!) neem om de recursieve functie te starten. Kort gezegd krijg ik dan deze werking:

· knoop 1 heeft geen ouders, print knoop 1
· ga naar het enige kind van knoop 1: knoop 2
· knoop 3 is ouder van knoop 2, ga naar knoo^p 3
· knoop 3 heeft geen ouders, print knoop 3
· knoop 3 heeft geen niet-bezochte kinderen
· ga naar ouder knoop 4 van knoop 2
· knoop 4 heeft geen ouders, print knoop 4
· knoop 5 is een niet bezocht kind van knoop 4, ga naar knoop 5
· knoop 5 heeft geen niet bezochte ouder, print knoop 5
· knoop 6 is een niet bezocht kind van knoop 5, ga naar knoop 6
· hier loopt het mis: knoop 6 heeft geen niet bezochte ouder, print knoop 6; hij beschouwt hier knoop 2 als bezocht (volgt uit algoritme), maar dat mag hier net niet!
· niet meer relevant ...

Ik zit er al een tijdje op te kijken, maar ik kom er niet echt uit. Iemand een idee hoe ik het moet aanpakken of wat ik mis doe?

Een probleem is dat de "gebruikelijke" doorlooptechnieken, zoals first-dept en first-breadth, hier niet toe te passen zijn, omdat de volgorde van uitprinten die ik wil, niet terug te vinden is in deze algoritmen.

Hopelijk kan iemand mij helpen

[ Voor 8% gewijzigd door Verwijderd op 30-11-2002 21:15 . Reden: phoutjuuh ]

[mbravenboer]

DiEana: Dit is een aangepaste versie van first-depth search van grafen (waarom? omdat je hier verschillende 'roots' kunt hebben die als eerste moeten geprint worden)

Waarom denk je dat je hier niet depth-first search voor kan gebruiken? Je moet de knopen namelijk niet gaan printen tijdens de uitvoer van de dfs, maar erna. Als je het afdrukken in een aparte traversal doet kan je er denk ik ook wel goed uitkomen met een kleine aanpassing van de normale depth-first search.

Volgens mij wil je namelijk gewoon een topologische sortering. Daar is een goed algoritme voor bekend wat een hele eenvoudige uitbreiding van dfs is.

hier loopt het mis: knoop 6 heeft geen niet bezochte ouder, print knoop 6; hij beschouwt hier knoop 2 als bezocht (volgt uit algoritme), maar dat mag hier net niet!

Als je verder wilt gaan met je huidige werk moet je denk ik net zoals bij dfs niet gaan werken met twee statussen (bezocht, niet bezocht) maar met drie. In het dfs algoritme wordt dit meestal aangegeven met wit, grijs, zwart.

[mbravenboer]

Ik zal je nog even matsen met het algoritme: Voer een dfs uit met als doel om de finishing times van knopen te berekenen. Als een knoop is afgerond zet je hem vooraan in een lijst. Aan het einde van de dfs uitvoering is de lijst een topologische sortering.

Er is echter alleen een topologische sortering als er geen cycles in je graaf zijn (nogal logisch ). Deze cycles kan je detecteren tijdens het uitvoeren de dfs. Ik hoop dat je zelf nog weet hoe je dat goed kan doen . Het algoritme werkt volgens mij ook op niet samenhangende grafen, dus die eis kan in principe vervallen.

[Verwijderd]

mbravenboer schreef op 30 November 2002 @ 21:28:
[...]

Waarom denk je dat je hier niet depth-first search voor kan gebruiken? Je moet de knopen namelijk niet gaan printen tijdens de uitvoer van de dfs, maar erna. Als je het afdrukken in een aparte traversal doet kan je er denk ik ook wel goed uitkomen met een kleine aanpassing van de normale depth-first search.

Wel, waarom ik denk dat dfs niet te gebruiken is hier: als je kijkt naar het voorbeeld van hierboven, en ik ga de eerste keer dfs toepassen op knoop1, dan gaat hij toch knoop3 en knoop4 totaal negeren? Bij de volgende keer (knoop3 resp. knoop4 als argument aan de dfs functie), worden die toch pas uitgeprint? Misschien snap ik de werking van dfs niet goed.

Volgens mij wil je namelijk gewoon een topologische sortering. Daar is een goed algoritme voor bekend wat een hele eenvoudige uitbreiding van dfs is.

Cool, daarmee kan ik verder! Ik vond niets op google omdat ik geen goede term kon bedenken voor dit probleem.

Als je verder wilt gaan met je huidige werk moet je denk ik net zoals bij dfs niet gaan werken met twee statussen (bezocht, niet bezocht) maar met drie. In het dfs algoritme wordt dit meestal aangegeven met wit, grijs, zwart.

Ik zal me wel vergissen hoor, maar is dfs niet rechtoe-rechtaan? En is het nie bfs dat gebruikt maakt van de 3 statusflaggen? Dat verandert natuurlijk niets aan je argument

Thanks!

[Verwijderd]

mbravenboer schreef op 30 november 2002 @ 21:38:
Ik zal je nog even matsen met het algoritme: Voer een dfs uit met als doel om de finishing times van knopen te berekenen. Als een knoop is afgerond zet je hem vooraan in een lijst. Aan het einde van de dfs uitvoering is de lijst een topologische sortering.

Je bedoelt grafen die bijvoorbeeld PERT schemas voorstellen en dus daarop de volgorde van uitvoeringen bepalen ahv. de tijd dat een proces inneemt? Ik snap niet goed hoe je dit kan zien als een "leidraad" voor het dfs algoritme, want het probleem is toch identiek?

Er is echter alleen een topologische sortering als er geen cycles in je graaf zijn (nogal logisch ). Deze cycles kan je detecteren tijdens het uitvoeren de dfs. Ik hoop dat je zelf nog weet hoe je dat goed kan doen . Het algoritme werkt volgens mij ook op niet samenhangende grafen, dus die eis kan in principe vervallen.

Jup, cycles detecteren is niet zo moeilijk lijkt me (heb het wel nooit gedaan, maar ik heb al een idee). En jup, dfs werkt ook op niet samenhangde grafen.

[ Voor 3% gewijzigd door Verwijderd op 30-11-2002 21:45 ]

[mbravenboer]

DiEana: Wel, waarom ik denk dat dfs niet te gebruiken is hier: als je kijkt naar het voorbeeld van hierboven, en ik ga de eerste keer dfs toepassen op knoop1, dan gaat hij toch knoop3 en knoop4 totaal negeren?

Nee: dfs zal blijven zoeken naar witte knopen. Als er geen knopen meer zijn die bereikbaar zijn vanuit 1 (via de normale edges dus) zullen er nieuwe wortels onstaan. DFS kan dus zorgen voor meerdere knopen zonder predecessor. Bij deze knopen is het algoritme dan steeds opnieuw begonnen om de graaf te verkennen.

Bij de volgende keer (knoop3 resp. knoop4 als argument aan de dfs functie), worden die toch pas uitgeprint? Misschien snap ik de werking van dfs niet goed.

Op zich snap je het denk ik wel goed, maar je ziet de ruime toepassingen nog niet. Ik heb ze helaas ook niet zelf bedacht: ze staan gewoon in de dikke algoritme boeken . De eenvoud van de topologische sortering laat de enorme veelzijdigheid van dfs mooi zien .

Ik zal me wel vergissen hoor, maar is dfs niet rechtoe-rechtaan? En is het nie bfs dat gebruikt maakt van de 3 statusflaggen? Dat verandert natuurlijk niets aan je argument

Nee, DFS gebruikt er in principe ook 3. Met behulp van de grijze flag kan je onderscheid maken tussen back-edges (cycles) en edges naar delen van de boom die al eerder volledig bezocht zijn. In principe is de grijze flag volgens mij daarbuiten niet nodig, dus het kan best zijn dat er beschrijvingen zijn die maar 2 flags gebruiken.

[mbravenboer]

DiEana: Je bedoelt grafen die bijvoorbeeld PERT schemas voorstellen en dus daarop de volgorde van uitvoeringen bepalen ahv. de tijd dat een proces inneemt? Ik snap niet goed hoe je dit kan zien als een "leidraad" voor het dfs algoritme, want het probleem is toch identiek?

Ik heb geen idee wat PERT schemas zijn, maar een topologische sortering is bedoeld om een mogelijke lineaire uitvoering van afhankelijk onderdelen te bepalen. Het standaard voorbeeld is een boek waarin hoofdstukken van elkaar afhankelijk zijn: in welke volgorde kan je het boek lezen?

Jup, cycles detecteren is niet zo moeilijk lijkt me (heb het wel nooit gedaan, maar ik heb al een idee).

Ik heb het net al verklapt

[Verwijderd]

mbravenboer schreef op 30 November 2002 @ 21:46:
[...]

Nee: dfs zal blijven zoeken naar witte knopen. Als er geen knopen meer zijn die bereikbaar zijn vanuit 1 (via de normale edges dus) zullen er nieuwe wortels onstaan. DFS kan dus zorgen voor meerdere knopen zonder predecessor. Bij deze knopen is het algoritme dan steeds opnieuw begonnen om de graaf te verkennen.

Jup, dat weet ik, dat dfs blijft zoeken naar knopen die nog wit zijn (hij moet immers alle knopen uitprinten, niet enkele). Maar dfs houdt op zich geen rekening mee met de witte knopen die NIET in de "huidige" gevormde tree/graph voorkomen. Vanuit dat standpunt dacht ik dus dat dfs onbruikbaar was, omdat dfs dus alleen een volgorde legt (jup! de volgorde die ik wil) op de "huidige" graph, en niet met de andere graphen die gaan komen/al voorbij zijn.

Op zich snap je het denk ik wel goed, maar je ziet de ruime toepassingen nog niet. Ik heb ze helaas ook niet zelf bedacht: ze staan gewoon in de dikke algoritme boeken . De eenvoud van de topologische sortering laat de enorme veelzijdigheid van dfs mooi zien .

[...]

Nee, DFS gebruikt er in principe ook 3. Met behulp van de grijze flag kan je onderscheid maken tussen back-edges (cycles) en edges naar delen van de boom die al eerder volledig bezocht zijn. In principe is de grijze flag volgens mij daarbuiten niet nodig, dus het kan best zijn dat er beschrijvingen zijn die maar 2 flags gebruiken.

Jup, om eerlijk te zijn ben ik nog nooit een beschrijving van dfs tegen gekomen met 3 flags

[Verwijderd]

mbravenboer schreef op 30 november 2002 @ 21:49:
[...]

Ik heb geen idee wat PERT schemas zijn, maar een topologische sortering is bedoeld om een mogelijke lineaire uitvoering van afhankelijk onderdelen te bepalen. Het standaard voorbeeld is een boek waarin hoofdstukken van elkaar afhankelijk zijn: in welke volgorde kan je het boek lezen?

PERT schemas: dat wat jij zegt, maar dan toegepast op machines die een bepaald proces uitvoeren, met elk zijn eigen tijd. We zeggen dus beide hetzelfde

Ik heb het net al verklapt

"DFS kan dus zorgen voor meerdere knopen zonder predecessor.", maar dan omgekeerd?

Thanks! Ik heb op google al wat nuttigs gevonden ivm. topological sort. Ik ga het morgen of na het weekend uitproberen en ik laat het zeker weten of het gelukt is. Bedankt mbravenboer

[ Voor 14% gewijzigd door Verwijderd op 30-11-2002 22:01 ]

[mbravenboer]

DiEana: Maar dfs houdt op zich geen rekening mee met de witte knopen die NIET in de "huidige" gevormde tree/graph voorkomen.

Nou ja, dat hangft er vanaf: een visit van knoop v gaat uiteraard alleen de knopen verkennen die bereikbaar zijn vanuit v en nog wit zijn. In de hoofdloop van dfs wordt er echter nagegaan of er nog witte knopen over zijn nadat er 1 keer door de graaf heen is gegaan.

Vanuit dat standpunt dacht ik dus dat dfs onbruikbaar was, omdat dfs dus alleen een volgorde legt (jup! de volgorde die ik wil) op de "huidige" graph, en niet met de andere graphen die gaan komen/al voorbij zijn.

Yepz, maar door dus handig gebruik te maken van de eindtijd ipv de begintijd en de knopen dan vooraan in de lijst te zetten krijg je prachtig een juiste sortering .

Jup, om eerlijk te zijn ben ik nog nooit een beschrijving van dfs tegen gekomen met 3 flags

Dat is vreemd/jammer want veel van de bijzondere kenmerken van dfs kan je alleen maar beschrijven als je onderscheid maakt met 3 verschillende flags.

DiEana: [ontdekken van cycles] "DFS kan dus zorgen voor meerdere knopen zonder predecessor.", maar dan omgekeerd?

Nou eigenlijk niet . Cycles kan je ontdekken door gebruik te maken van de 'middelste' kleurcode. Een edge die naar een knoop met die kleurcode toe gaat wordt een back-edge genoemd en geeft een cycle aan.

Thanks! Ik heb op google al wat nuttigs gevonden ivm. topological sort. Ik ga het morgen of na het weekend uitproberen en ik laat het zeker weten of het gelukt is. Bedankt mbravenboer

Succes . Ik was er toevallig zelf ook mee bezig (maar dan in een functionele taal ). Normaal is mijn aktieve kennis over dit soort algoritme toestanden niet zo groot .

[Verwijderd]

mbravenboer schreef op 30 november 2002 @ 22:08:
[...]

Nou ja, dat hangft er vanaf: een visit van knoop v gaat uiteraard alleen de knopen verkennen die bereikbaar zijn vanuit v en nog wit zijn. In de hoofdloop van dfs wordt er echter nagegaan of er nog witte knopen over zijn nadat er 1 keer door de graaf heen is gegaan.


[...]

Yepz, maar door dus handig gebruik te maken van de eindtijd ipv de begintijd en de knopen dan vooraan in de lijst te zetten krijg je prachtig een juiste sortering .

Beter kan het niet!

Dat is vreemd/jammer want veel van de bijzondere kenmerken van dfs kan je alleen maar beschrijven als je onderscheid maakt met 3 verschillende flags.

Komt nog wel, ben er nog niet zo lang mee bezig

Nou eigenlijk niet . Cycles kan je ontdekken door gebruik te maken van de 'middelste' kleurcode. Een edge die naar een knoop met die kleurcode toe gaat wordt een back-edge genoemd en geeft een cycle aan.

Zo kan het ook ja. Ik bedoelde: probeer een knoop te zoeken zonder ouder. Vind je die niet: cycle! Maar achteraf bekeken is dat niet juist: je kan ook een cycle hebben midden in je graph, en niet aan de uiteinden

Succes . Ik was er toevallig zelf ook mee bezig (maar dan in een functionele taal ). Normaal is mijn aktieve kennis over dit soort algoritme toestanden niet zo groot .

Ditto that!

PS: dit was tot nu toe bijna een chatbox asl?

[ Voor 3% gewijzigd door Verwijderd op 30-11-2002 22:20 ]

[Verwijderd]

Uit google:

code:

1) Call DFS ( G ) to compute f[v] " v Î V 
2) As each vertex is finished put it into the front of a linked list 
3) Return the linked lise of vertices

Neem deze graaf:



Stel ik neem eerst knoop 1 (maakt normaal gezien niet uit): uit de dfs komt: '1 - 2 - 3 - 4'.
Nu doe ik knoop 2: er komt niets uit de dfs.
Nu doe ik knoop 3: er komt niets uit de dfs.
Nu doe ik knoop 4: er komt niets uit de dfs.

Ik krijg: 1 - 2 - 3 - 4. En dat is dus mis! De enige juiste oplossingen zijn 1 - 2 - 4 - 3 en 1 - 4 - 2 - 3.

Zie ik het verkeerd?

[ Voor 16% gewijzigd door Verwijderd op 01-12-2002 09:47 . Reden: (100%)(15%)(87%)(9%) ]

[mbravenboer]

DiEana: Uit google:
...
2) As each vertex is finished put it into the front of a linked list
...

Even zorgvuldig uitvoeren, dan zie je wel dat het werkt.

[mbravenboer]

Ik heb ze even gedraaid op mijn eigen implementatie:

Het kleine graafje:

code:

[1,2,4,3]

De eerste graaf:

code:

[4,5,3,1,2,7,6]