A premye fwa mwen tout tan chita, yo ekri kèk reyèl RDF postal, mwen te kòmanse, kòm youn nan yo ta dwe toujou, ak kèk tès yo. Pifò ladan yo ki al bon, men Lè sa a, mwen te ekri yon tès ki konpare egalite a nan de grafik; mwen panse ke sa a te pou yon analizeur nan Scala, nenpòt moman ane pase a, men m pèdi tras nan ki sa egzakteman m 'te kap nan. Nan nenpòt ka, ki sa ki yon ka nan vè, mwen louvri.
Li sanble ke egalite graf nan RDF se difisil. Konbinezon nan gangliyon vid ak non-vid fè li yon pwoblèm izomorfism graf ke mwen pa jwenn yon ekivalans egzak pou nan tou dwat-up teyori grafik. Graf ak yo te rele somè ak bor gen solisyon fasil yo, graf ki genyen somè enkoni ak bor gen lòt, solisyon difisil.Diferans lan, ki depann sou kalite a nan graf, kapab gen ant O (n) ak O (n!) sou ki kantite nœuds, Se konsa, lè chwazi yon solisyon posib, nou ta renmen pou fè pou evite solisyon ki pa pran nonmen nan kont.
Pwoblèm nan izomorfism se difisil ase ke anpil popilè RDF en pa menm gen ladan yon solisyon pou li. RDFLib pou Python a gen yon apwoksimasyon ak yon a-fè nòt, mwen pa wè yon fonksyon ki apwopriye a nan API modèl Redland a, ak Sesame gen yon aplikasyon ki gen kòmantè ki anba la a:
/ / FIXME: sa a aplikasyon repetitif gen yon gwo risk pou yo / / lakòz yon larivyè k'ap desann chemine
Java mwen se rouye ak Mwen pa gen okenn entansyon pou polisaj li moute pou sa a post blog, men mwen kwè aplikasyon sezam an gen konpleksite faktoryèl.
Koulye a, m 'pa jwenn sa ki mal. Sa yo se tout pwojè gratis, epi li nan yon pwoblèm difisil fè sa ki dwat. Nou plis pase nan Datagraph jis te fè fè san yo pa yon fonksyon izomorfism swa nan Scala oswa Ruby pandan plizyè mwa olye ke rezoud li. Se konsa, sa a pa gen entansyon yo dwe yon piki bon mache nan sa yo ki pwojè - an reyalite, nou sèvi ak toude Redland ak Sesame, ak afè san pwoblèm mwen tap. Men, si mwen mal sou nati a flò sa a jaden flè, yon moun tanpri korije m '.
Sepandan, nou ap devlope yon nouvo RDF nan bibliyotèk pou Ruby, se konsa lè li te vini tan reyèlman rezoud pwoblèm nan, nou te vle rezoud li dwat. Tankou pifò pwoblèm nan syans konpitè, li la aktyèlman nouvèl fin vye granmoun.Jeremy Carroll rezoud li epi li aplike li pou Jena swa anvan oubyen apre ekri yonpapye gwo sou sijè a. Sa mwen ap sou yo dekri se pi plis oswa mwens algorithm l ', li pandan m ap yon ti kras ajiste sa ki annapre yo-style mwen an, mwen pa sou di anpil ke papye l' pa fè sa. Se konsa, jis ale li papye a si sa a, se preferans ou.
Ka algorithm a ap dekri tankou yon revizyon nan yon nayif O (n!) algorithm izomorfism graf, nan ki se chak node vid mappé sou chak node lòt vid, swiv pa yon chèk konsistans. Majik la tij soti nan RDF gen sa yo debouya Out bann kod mondyal pou pifò somè ak tout bor. Si nou ap entelijan osijè de sa, nou ka elimine anpil nan tout mapin yo posib anvan nou eseye menm premye nou an spéculatif gewografik.
Mwen pa fè matematik la, men li ta sanble ke yon moun ta ka resisite yon graf ka pathologie ki ta dwe O (n!). Nan lòt men an, depi RDF pa pèmèt atribu node vid, ak algoritm paske nan fen sou matche ak premye fwa a, mwen pa gen ankò kalkile ki jan yo kreye tankou yon graf pathologie pou sa a algoritm. Graf gen tandans yo dwe swa louvri ase gen yon gwo kantite solisyon, youn nan yo ap kite ou jwenn byen vit, oswa sere ase gen youn sèlman.
Algorithm a ap travay jan sa a:
- Konpare gwosè graf ak tout deklarasyon san yo pa nœuds vid. Si yo pa matche ak, febli.
- Repete, pou chak graf:
- Repete, pou chak node vid:
- Mak node la kòm chita ou pa. Yon node chita la gen sèlman nœuds ki pa Peye-vid oswa nœuds chita sou deklarasyon an ki li parèt.
- Kreye yon siyati pou node la. Yon siyati konsiste de yon reprezantasyon kanonyal nan tout deklarasyon sa yo yon node parèt pous
- Revoke sof si nou make yon node kòm chita sou sa kouri.
- Repete, pou chak node vid:
- Map chita nœuds vid nan graf la lòt chita nœuds vid kote siyati matche.
- Si tout nœuds yo trase, nou genyen yon bijèksyon, ki nou kapab retounen.
- Chwazi fondman nœuds ki soti nan chak graf ak siyati ki idantik. Mak yo tankou chita, lè sa a recurse nan etap 2.
- Si pa gen okenn fondman nœuds gen siyati nan menm, oswa yo nou te eseye tout pè matche, yon bijèksyon pa egziste. Febli.
Nan yon bagay k ap apwoche angle jou-a-jou, sa kap pase isit la se ke apre elimine posiblite yo senp, nou ap génération yon hash nan tout nan eleman yo ki parèt ak yon node bay yo nan yon graf. Nou Lè sa a, kreye yon kat node-a-hash.Kòm achaj yo pral menm bagay la pou nœuds vid yo nan toulede graf opinyon, nou itilize ki hash elimine matchings posib anvan nou eseye yo. Olye pou yo eseye chak kat, nou eseye mapin sèlman sou nœuds ki gen siyati a menm.Rezilta a fen a se yon algorithm ki egzije pou yon ka san patipri pathologie recurse nan tout, ki ale sèlman nan recurse anpil lapenn. Bèl.
A nenpòt ki vitès, ou ka wè detay yo, ansanm ak kèk ka tès yo jwe avèk, nanRDF:: izomorf pou RDF.rb. Sa a post blog konyenside avèk, 0.1.0 lage ki karakteristik yon algorithm siyati yon ti kras amelyore, kantite moun ki nesesè jij nan kèk ka. Dokiman an tou se anpil amelyore - mwen te pase plis tan sou pwoblèm sa a pase m 'tout tan gen entansyon, se konsa mwen espere sa a ka yon rezime ki lizib algorithm a pou nenpòt moun ki vini nan tout sa a nan lavni.Natirèlman, RDF.rb 's estrikti vle di prèske anyen lè l sèvi avèk RDF.rb ka fè tès pou izomorfism kounye a, se konsa èspere ke li pa pral janm rive ak ou pou li postal la.
Natirèlman, RDF:: izomorf a se nan domèn nan piblik, se konsa ou ta dwe jwenn aplikasyon mwen an vle resevwa nou, santi yo lib a kapab bay kopi postal lan kòm dirèkteman tankou fondasyon ou a oswa pwogram lang pèmèt. Lè tanpri santi yo lib fè sa san okenn obligasyon bay Attribution oswa nenpòt ki stupidity sa yo.