Autor Zpráva
Witiko
Profil
Zdravím PHP subfórum.

Mám databázi se dvěmi tabulkami, z nichž jedna obsahuje jednotky a druhá definuje vztahy a převoditelnost mezi jednotkami. Vypadá to nějak takto:

UNITS (ID, NAME)
>> 0, centimetry
>> 1, milimetry

CONVERSIONS (FROM, TO, RATIO)
>> 0, 1, 10
>> 1, 0, 0.1

Snažím se dospět ke scriptu, který by dokázal projít i přes několik vrstev a doplnit veškeré chybějící vztahy mezi jednotkami. Vezměme si, že mám následující obsah tabulek:

UNITS (ID, NAME)
>> 0, gramy
>> 1, kilogramy
>> 2, mililitry
>> 3, decilitry

CONVERSIONS (FROM, TO, RATIO)
>> 0, 1, 0.001
>> 1, 0, 1000
>> 2, 3, 0.01
>> 3, 2, 100

Nyní do tabulky UNITS vložíme řádek o hodnotách (4, litry) a do tabulky CONVERSIONS řádky (4, 1, 1) - kilogramy jsou rovny litrům (berme, že jde o vodu) - a (4, 3, 10) - litr se rovná 10 decilitrům. Tímto došlo k propojení jednotek váhy a objemu a vzniká zde spousta vztahů mezi jednotkami, které je třeba doplnit, aby ve výsledku vypadaly tabulky takto:

UNITS (ID, NAME)
>> 0, gramy
>> 1, kilogramy
>> 2, mililitry
>> 3, decilitry
>> 4, litry

CONVERSIONS (FROM, TO, RATIO)
>> 0, 1, 0.001
>> 0, 2, 1
>> 0, 3, 0.01
>> 0, 4, 0.001
>> 1, 0, 1000
>> 1, 2, 1000
>> 1, 3, 10
>> 1, 4, 1
>> 2, 0, 1
>> 2, 1, 0.001
>> 2, 3, 0.01
>> 2, 4, 0.001
>> 3, 0, 10
>> 3, 1, 0.1
>> 3, 2, 100
>> 3, 4, 0.1
>> 4, 0, 0.001
>> 4, 1, 1
>> 4, 2, 0.001
>> 4, 3, 10

Nejspíš bude potřeba volat rekurzivně funkci / použít cyklus, případně nadefinovat cyklus již přímo v MySQL žádosti (tzn. cyklus by se neprováděl na straně php, ale MySQL), nicméně ačkoliv jsem si nad problémem lámal hlavu, nenapadlo mě vhodné řešení. Proto poprosím o postrčení vhodným směrem, případně k lepšímu návrhu vztahové tabulky tak, aby její správa byla jednodušší (při n spolu souvisejících jednotkách bude mít tabulka CONVERSIONS n * (n - 1) řádků).
Alphard_
Profil *
Nebylo by jednodušší vždy při přidání nového záznamu vygenerovat vše, co je potřeba, než potom hledat, co chybí (a potenciálně přebývá)?
Witiko
Profil
Alphard
Dobrá tedy, po dodání dat vypadá tabulka takto:
UNITS (ID, NAME)
>> 0, gramy
>> 1, kilogramy
>> 2, mililitry
>> 3, decilitry
>> 4, litry

CONVERSIONS (FROM, TO, RATIO)
>> 0, 1, 0.001
>> 1, 0, 1000
>> 1, 4, 1
>> 2, 3, 0.01
>> 3, 2, 100
>> 3, 4, 10
>> 4, 1, 1
>> 4, 3, 10


Jak by tedy (alespoň schématicky) vypadal cyklus, který vztahy doplní na
CONVERSIONS (FROM, TO, RATIO)
>> 0, 1, 0.001
>> 0, 2, 1
>> 0, 3, 0.01
>> 0, 4, 0.001
>> 1, 0, 1000
>> 1, 2, 1000
>> 1, 3, 10
>> 1, 4, 1
>> 2, 0, 1
>> 2, 1, 0.001
>> 2, 3, 0.01
>> 2, 4, 0.001
>> 3, 0, 10
>> 3, 1, 0.1
>> 3, 2, 100
>> 3, 4, 0.1
>> 4, 0, 0.001
>> 4, 1, 1
>> 4, 2, 0.001
>> 4, 3, 10


Script musí doplnit všechny nově vzniklé vztahy mezi gramy, kilogramy, mililitry a decilitry. Ty nelze doplnit "postupně při přidání nového záznamu", tyto vazby vznikají až s přidáním jednotky litru.
TomášK
Profil
Následující pseudokód jsem neověřoval, ale zdá mi, že by mohl fungovat. Idea je založena na Floyd-Warshallově algoritmu z oblasti teorie grafů.

Vytvoř matici M o velikosti n x n, kde n je počet jednotek (záznamů v UNITS). Inicializuj
M[i][j] := (poměr převodu i -> j) nebo 0, pokud je neznámý // poměr převodu je ratio z CONVERSIONS
. Algoritmus si nedokáže domyslet inverzní převody, tj. je potřeba zadat oba (0->1 i 1->0). Pro diagonálu M[i][i] := 1, neboť poměr převodu jednotky sama na sebe je 1.

Prožeň matici následující procedurou:

procedure DoplneniJednotek ()
   for k := 1 to n
      for i := 1 to n
         for j := 1 to n
                M[i][j] := M[i][k] * M[k][j];


Ve výsledku bude na pozici M[i][j] poměr převodu i->j, pokud takový převod lze odvodit ze zadání, jinak 0. Výpočet nekontroluje, zda vstup neobsahuje spor - dva různé způsoby převodu i->j, které by daly jiný výsledek, které , ale šlo by to doplnit. Nejrychlejší možný způsob to není, ale na implementaci jednoduchý. Předpokládám, že jednotek nebude tolik, aby se vyplatilo hledat něco rychlejšího, i když to taky určitě někdy někdo vymyslel.
Witiko
Profil
TomášK:
Super, to vypadá, že by to mohlo být, co potřebuji. Jen je to až podezřele implementačně snadné, z pohledu na algorytmus mám pochybnosti, že počítá s hlubšími vztahy (tzn. kupříkladu vztahy jsou definované pouze mezi jednotkami 1 - 4 - 12 - 8 - 2 - 9, otázka je, jestli algoritmus nalezne vztah mezi 1 a 9). Vykouším to. :)
Alphard
Profil
Witiko:
Jak by tedy (alespoň schématicky) vypadal cyklus
Je už problém (ať už s pomocí [#4] nebo bez) vyřešen, nebo ještě ne? Dřív jsem neměl čas, a teď se tím nechci zabývat čistě akademicky, jestli to už funguje :-)
Witiko
Profil
Alphard:
Ještě jsem nestihl script nasadit, ale podle logiky algoritmu by měl, tedy ano. :-)
Segi_L
Profil
Witiko
Tie tabulky platia a budú platit len pre vodu?
Witiko
Profil
Segi_L:
Ne, to bylo jen pro ukázku.
Witiko
Profil
Řeším nyní problém s odstraněním jednotek z databáze. Pojďme vyjít z předchozího příkladu. Před přidáním litrů vypadají vztahy definované v databázi graficky nějak takto:



Po přidání litrů a prohnání matice algoritmem skončíme nějak takto:



Pokud bychom nyní chtěli jednotku odebrat i s veškerými na ní závisícími vztahy z databáze, byl by postup poměrně triviální. Stačilo by nám odstranit veškeré "oranžové" vztahy - tedy vztahy vytvořené algoritmem bezprostředně po přidání jednotky litrů do databáze.
Pojďme však do databáze přidat další jednotku, např. centilitry, které si definujeme ve vztahu k dalším jednotkám objemu:



V tuto chvíli pokud bychom chtěli odstranit veškeré vztahy závisící na jednotce litrů, jsme nahraní. I při odstranění veškerých vztahů vytvořených algoritmem bezprostředně po přidání jednotky litrů do databáze a veškerých přímích vztahů s jednotkou litrů, stále nám zůstanou vztahy mezi centilitry a gramy / kilogramy.

Je tedy nějaký způsob / cyklus, kterým by spolu s jednotkou bylo možné odstranit veškeré vztahy vzniklé díky ní? Z hlediska příkladu algoritmus, který by navrátil vztahy do takovéhoto stavu:

TomášK
Profil
Witiko:
Pěkné grafy :-) Tentokrát nic algoritmicky přímočarého nevidím. Ale předpokládám, že jednotek by nemusel být tolik, aby to šlo udělat "hloupě" - hrany, které mi vygeneruje matice, si označím jako vygenerované, ostatní jako definované. Když budu chtít odebrat nějakou jednotku, tak ji odeberu, smažu všechny vygenerované hrany v celém grafu a nechám matici, ať mi je spočítá znovu.

Edit1: Stačí se omezit na vrcholy, které jsou z odstraňovaného dosažitelné.
Witiko
Profil
TomášK:
Ano, to zní rozumně, měl jsem se na to podívat z tohohle úhlu, možná by mě to trklo. :-)

Dík, pustím se do implementace.

Vaše odpověď

Mohlo by se hodit


Prosím používejte diakritiku a interpunkci.

Ochrana proti spamu. Napište prosím číslo dvě-sta čtyřicet-sedm: