Autor | Zpráva | ||
---|---|---|---|
Gogo_v Profil |
#1 · Zasláno: 1. 12. 2011, 14:56:57 · Upravil/a: Gogo_v
Dobrý den. Přemýšlím už relativně dlouho nad řešením jednoho problému a pořád mne nic kloudného nenapadlo. Potřeboval bych setřídit posloupnost podle ip adresy. Konkrétně mám sloupce source_ip a destination_ip ve kterých je uloženo co s čím sousedí. Výsledek by měl být řetězec např. A->B->C->D a kdyz se zeptám co nefunguje když nejde C vrátí mi to C a D. Problém trošku je že jakákoliv IP může sousedit s více než jedním sousedem takže třeba A->B->C->D a A->E->F a E->G->H (tu když se zeptám co nejde když nejde E odpovědí bude E,F,G,H ) a podobně . Ty pismena reprezentují IP adresu ale k pochopení o co jde stačí asi i takový popis :) alspoň doufám. Děkuji moc za jakýkoliv nápad
něco z wiki /* Tarjanuv algoritmus pseudo code @param node zpracovavany uzel @param SCC seznam komponent (seznamu uzlu v komponentach) @param s zasobnik @param index index slouzici k cislovani uzlu @return seznam komponent */ List tarjanAlgorithm(Node node, List scc, Stack s, int index) v.index = index v.lowlink = index index++ s.push(node) //pridej na zasobnik for each Node n in Adj(node) do //pro vsechny sousedy if n.index == -1 //pokud jeste nebyl uzel objeven tarjanAlgorithm(n, scc, s, index) //prohledej node.lowlink = min(node.lowlink, n.lowlink) //uprav lowlink otce else if stack.contains(n) node.lowlink = min(node.lowlink, n.index) if node.lowlink == node.index //pokud jsme v koreni komponenty Node n = null List component //seznam uzlu dane komponenty do n = stack.pop() //vyber uzel ze zasobniku component.add(n) //pridej ho do komponenty while(n != v) //dokud nejsme v koreni scc.add(component) //komponentu pridej do seznamu komponent return scc //vrat seznam komponent |
||
okolojdouci Profil * |
#2 · Zasláno: 2. 12. 2011, 05:56:34
Možná mi něco uniká, ale nestačila by jedna tabulka pro IP adresy a druhá pro vazbu IDpredchudce - IDnaslednik?
Data pak asi budeš muset vytahovat rekurzivním voláním z php, takže to nebude jedním dotazem, ale třeba pěti, ale tím bych se netrápil, pokud to nebudou nějaké gigantické výpisy každoých pár sekund. |
||
Joker Profil |
#3 · Zasláno: 2. 12. 2011, 07:59:12
Gogo_v:
„jakákoliv IP může sousedit s více než jedním sousedem“ Takže to není řetěz, ale strom. Pak by se dal použít třeba algoritmus traverzování kolem stromu, ale nejspíš bude potřeba upravit tu databázovou tabulku. |
||
Gogo_v Profil |
#4 · Zasláno: 2. 12. 2011, 13:43:01
Joker:
Děkuji za reakci. Samozřejmě jde o strom jak už jsem dával odkaz na wiki. Na traverzovaní jsem se díval bohužel ne příliž pochopil, teda alspoň jak to aplikovat na můj problém :) Možná nebude od věci vysvětlit k čemu to má být :) Stávající tabulka se generuje automaticky několikrát denně a vytvářím ji dotazy na zařízení cisco (počítačová síť)- cdp neighbours z odpovědí vysekám které zařízení s čím sousedí a to uložím do databáze. Problém je že každé zařízení mi řekne jen svého přímého souseda . Zeptám se zařízení A co má za sousedy a to mi odpoví na portu x sousedi B na portu Y sousedi C ja si do databaze uložím (src A dst B) (src A dst C) když se zeptám zařízení B tak to mi samozřejmě taky odpoví že sousedí s A a třeba F uložím tedy i (src B dst A ) ... atd. Z toho vyplývá že nějaké drastické změny v MySQL nevymyslím protože víc informací než které tam aktualně jsou nikde nezjistím. Nebráním se ovšem udělat ze stávajících dat tabulku jinou pokud bz to něčemu pomohlo :). okolojdouci: nepochopil jsem docela co máte na mysli. vazba predchudce - naslednik je ve stávající tabulce dána identifikátor je právě ta IP adresa. Mi šlo o to vytvořit strom sítě z těchto informaci které jsou v databázi. a následně nějaký způsob jak zjistit čeho všeho se dotkne když strom na některém místě přeruším tedy dotčené body. |
||
okolojdouci Profil * |
#5 · Zasláno: 2. 12. 2011, 13:52:15
Gogo_v:
Vypadá to, že jsem špatně pobral zadání. Ignorovat možno. |
||
Časová prodleva: 12 let
|
0