Grote graaf zo compact mogelijk opslaan

[user109731]

Ik wil een grote graaf in een zo klein mogelijk bestand opslaan.

Wat ik zelf had bedacht: elke node krijgt een nummer, en dan word opgeslagen welke node met welke andere node verbonden is, bijvoorbeeld zo (letter = node):

a bcde
b cd
d b

Geeft aan dat node 'a' verbonden is met 'b', 'c', 'd' en 'e'. Node 'b' is verbonden met 'c' en 'd', enzovoort.
Dat werkt nu wel, maar ik vraag me af of het niet efficienter kan. Node 'b' bijvoorbeeld komt in bovenstaand voorbeeld 3 keer voor, ik vraag me af of dat niet handiger kan. Bovenstaande voorbeeld sla ik nu op in 13 bytes (elke node een byte + 3 seperators), maar bij grote hoeveelheden loopt dat al snel op. Andere manier waar ik aan zit te denken is een matrix maken, maar ik betwijfel of ik daarmee veel opschiet en ik wil de volgorde van de verbindingen ook behouden

Mijn vraag is dus: is er een efficiëntere manier om een graaf op te slaan in een bestand, met behoud van de volgorde van de verbindingen?

Ik heb al gezocht, maar ik weet niet goed waar ik op moet zoeken, en sowieso is het zoeken op 'graph' best lastig, omdat je allerlei informatie over grafieken e.d. krijgt

[Verwijderd]

Mijn vraag is dus: is er een efficiëntere manier om een graaf op te slaan in een bestand, met behoud van de volgorde van de verbindingen?

Wat bedoel je hier mee? Heb je een gerichte graaf of begrijp ik je dan verkeerd. Is dit namelijk niet het geval dan het opslaan van b-d en d-b natuurlijk volkomen overbodig. Het is dan voldoende om alle zijden (lijnen) op te slaan en eventuele losse knopen (punten).

Dus het is zowieso belangrijk om te weten wat voor graaf het is (zie hier). Afhankelijk van het type graaf (!!!) zijn er verschillende manieren om deze efficiënt op te slaan, dus iets meer info is zeker gewenst .

[user109731]

OK, ik zal proberen wat meer details te geven.

d-b en b-d moeten apart opgeslagen worden, een gerichte graaf dus.
De volgorde van verbindingen moet behouden blijven, dus bijvoorbeeld: a is verbonden met c, a is verbonden met b en a is verbonden met d. In die volgorde. Ik sla nu in zo'n geval ACBD op, dat is wat anders dan wanneer ik ABDC op zou slaan. Nodes kunnen trouwens ook met zichzelf verbonden zijn, en de hoek van de vertex is niet van belang

[Verwijderd]

In die volgorde - puur uit nieuwsgierigheid, waarom dat?

Leuk probleem... een "kort door de bocht" manier waarover verder niet echt is nagedacht kan ik je wel geven. Verder zal ik er nog eens over nadenken.

Bepaal het aantal nodes (n). Er zijn dus n+1 keys nodig om iedere node en een seperator te onderscheiden in een bestand. Codeer iedere key met een minimaal aantal bits (hiervoor geldt: 2^bits >= n+1). Vervolgens kun je het bestand eenvoudig vullen, bijvoorbeeld: "A BECD B CDB C C D EBA E AB". Misschien dat daarna comprimeren nog iets oplevert.

[Verwijderd]

Wat je in ieder geval kan stellen is dat elke verbinding tussen nodes opgeslagen moet worden en alle afzonderlijke nodes. Zou je ook wat meer informatie kunnen verschaffen van het nut van zo'n 'meest compact mogelijke' graaf?

Je zou misschien nog kunnen kiezen om de eerste keer dat een Node voorkomt hem te definieren;

code:

a b{cd{b}}cde

Dit bevat precies de informatie van jou voorbeeld, maar het scheelt drie line breaks...

[user109731]

Verwijderd schreef op woensdag 20 december 2006 @ 22:11:
In die volgorde - puur uit nieuwsgierigheid, waarom dat?

De belangrijkste verbindingen komen eerst, meer kan ik er niet over zeggen

Bepaal het aantal nodes (n). Er zijn dus n+1 keys nodig om iedere node en een seperator te onderscheiden in een bestand. Codeer iedere key met een minimaal aantal bits (hiervoor geldt: 2bits >= n+1). Vervolgens kun je het bestand eenvoudig vullen, bijvoorbeeld: "A BECD B CDB C C D EBA E AB". Misschien dat daarna comprimeren nog iets oplevert.

Jep, zoiets doe ik nu ongeveer. Probleem is dat het aantal nodes best groot is, dus ik kan niet heel veel winst halen met 'minder bits per node'

Verwijderd schreef op woensdag 20 december 2006 @ 22:31:
Zou je ook wat meer informatie kunnen verschaffen van het nut van zo'n 'meest compact mogelijke' graaf?

Kleiner bestand, zeker bij grotere/meerdere grafen. En gewoon nieuwsgierig.

Je zou misschien nog kunnen kiezen om de eerste keer dat een Node voorkomt hem te definieren;

code:

a b{cd{b}}cde

Dit bevat precies de informatie van jou voorbeeld, maar het scheelt drie line breaks...

Maar het zorgt voor extra accolades Die linebreaks staan er enkel voor de leesbaarheid, in het 'echt' gebruik ik daar een 0-byte voor. Jouw voorbeeld komt op ongeveer 13 bytes, dat is net zoveel als de mijne... Misschien dat de eerste accolade weg kan, ik ga hier wel naar kijken morgen, want dit is wel de richting waarin ik 'het' zoek.

Nu ik de juiste zoekwoorden weet lijkt het erop dat er twee veelgebruikte mogelijkheden zijn, en die had ik zelf al bedacht...

[MSalters]

Kort antwoord: Ja, maar niet heel erg veel. De meest efficiente methode voor dit soort kleine, maar redelijk verbonden soort is een bitwise opslag. In jouw voorbeeld: 1111 0110 0000 0100 0000. Dat zijn 20 bits. Elke nibble geeft de uitgaande verbindingen aan; ik heb aangenomen dat a->a nooit voorkomt en die bit weggelaten.

In een beperkt verbonden matrix kan het efficienter zijn om geen bitmask te gebruiken, omdat de meeste bits dan 0 zijn.

[Verwijderd]

Na enig denkwerk kom ik op een manier die wellicht wat winst op kan leveren.

In plaats van een gerichte graaf heb je eigenlijk een gerichte, gewogen graaf waarbij de volgorde de gewichten zijn. Ik begin in de node waar de meeste uitgaande zijden zijn. Daar begin ik de belangrijkste zijde te volgen en zo spring ik van node naar node tot dit niet meer mogelijk is. Deze series zijn te scheiden met een scheidings-teken ('_'). Naast een normaal scheidings-teken heb ik nog twee andere tekens gedefinieerd. Het inclusie-teken geeft aan dat iedere reeks achter het betreffende karakter hoort. Deze heb ik aangegeven met een '{' of '}' (openen of sluiten is in theorie hetzelfde karakter). Zo kan

ABCC_AEAC_ADE_AEB

worden omgevormd tot

A{BCC_EAC_DE_EB}

Dit is een verbetering voor iedere node waaruit meer dan 3 uitgaande zijde zijn. Verder heb ik een exclusie-teken gedefinieerd (ook alleen effectief bij nodes waar meer dan 3 uitgaande zijde zijn). Dit teken ('[' of ']') bevat weer reeksen maar deze horen niet bij de inclusies waarin het zich bevindt hoewel ze wel het voorgaande karakter bevatten. Dus wordt

ABCD_AC_AD_AED_BD_BE_BA

zonder exclusie-tekens

A{BCD_C_D_ED}B{D_E_A}

maar met kan het nog kleiner, nl.

A{B[D_E_A]CD_C_D_ED}

Wanneer er veel nodes zijn met veel uitgaande zijde, zijn de inclusies en exclusies handig en comprimeren ze volgens mij redelijk.

Het voorbeeld wat ik eerder gebruikte kan zo worden herschreven en is korter.

### oude stijl ###
A BECD B CDB C C D EBA E AB

### nieuwe stijl ###
A{BCC_EAC_DEBDB}D

Hoewel ik het bovenstaande verhaal nog zeer wazig vind, laat ik het hier even bij. Hopelijk maakt het duidelijk wat ik bedoel. Zo niet, dan hoor ik het graag en verklaar ik het een en ander morgen nog wel.

[joepP]

Waarom moeilijk doen? Pak een standaard compressie-algoritme, gooi die over je data, en klaar.

[Ivo]

joepP schreef op donderdag 21 december 2006 @ 10:41:
Waarom moeilijk doen? Pak een standaard compressie-algoritme, gooi die over je data, en klaar.

Hij zit nu echter nog in de fase dat hij de data aan het definieren is. Een compressie-algoritme kan niet elke dataset efficient comprimeren. Bovendien kan hij nu een zeer specifieke vorm van compressie (namelijk specifiek voor zijn probleem) ontwikkelen die waarschijnlijk beter is dan een compressie-algoritme over de intuitive manier van de data representeren heen gooien.

[joepP]

Dat betwijfel ik ten sterkste.

De hoeveelheid informatie in de meest eenvoudige manier van opslaan (stringetje bouwen zoals in de TS) is al zeer hoog. Of andersom bekeken: er is geen redundante informatie aanwezig. Het beste wat je in dat geval zou kunnen doen is een goede bitstring codering te vinden voor de afzonderlijke knopen. En dat is precies wat Huffman encoding doet, waar je vast een standaard implementatietje voor uit de kast kan trekken. Snel, simpel en efficient.

De -enige- manier die ik kan bedenken om betere resultaten te halen is specifieke kennis van de graaf te gebruiken. Een graaf zonder kruisende lijnen (planair) zal wel wat efficienter opgeslagen kunnen worden.

[EfBe]

Tenzij dit voor handhelds is, is het investeren in compressie van specialistische data zoals DAG's echt weggegooide tijd, want het levert alleen maar een voordeel op voor de goedkoopste resource in het systeem, de harddisk, terwijl je juist resources extra gebruikt die vele malen duurder zijn.

En MSalters' methodiek kun je gebruiken om een matrix opslag te bouwen waarbij bits de connectie weergeven.