[java]Deleten in netwerk, inclusief referenties

[Flapmo]

Ik zit met een probleempje.

Ik heb in java een netwerk opgebouwd bestaande uit nodes, in deze nodes staan referenties naar andere nodes. Die weer referenties bevatten naar weer andere nodes. Een voorbeeldje:




Waar de xi steeds de nodes zijn. Verder valt het misschien op dat er een soort 'lagen' zijn. Dit is enigzins waar. Er zijn 2 'soorten' nodes. De een is een film de ander een acteur. Een film bevat dus in zijn node een list (linked) met daarin de hashkeys naar bijbehorende acteurnode in de hashmap (waar het netwerk opgeslagen is). En een acteurnode bevat weer links naar de movies waarin hij gespeeld heeft.

Nu wil ik gaan kijken of er binnen dit netwerk subnetwerken zijn. Dus dat er niet via stappen van movie naar acteur, en acteur naar movie te komen is. (hoppend).

Mijn idee was om een clone te maken van het originele netwerk en deze als een soort virus af te breken. Je pakt er random een en delete deze, hiernaa pak je alle referenties op 1 diep (breadth-first techniek, dus eerst alle referenties van die node verwijderen en dan van de nodes die daar weer in staan). Alleen hier stuit je op een probleem. Het netwerk is groot en bevat zo'n 700.000 nodes. En bij deleten gebeurd er dit:

X1----X2-----X3-----X4

Als ik nu X1 heb gepakt (random) en dus X1 wil deleten en ook zijn refs in X1, dus X2 dan moet ik wel zorgen dat de refs die in X2 staan bewaard blijven. Ik zou nu bijvoorbeeld alleen de referenties die in de node staan kunnen deleten, zo blijft de node nog wel toegankelijk. Je delete dan zeg maar alleen het verbindingslijntje X1-X2. hierna ga je naar X2 en doet hetzelfde.

Voor een klein netwerk zou dit nog wel werken omdat je altijd maar naar 1 andere hoeft. Maar omdat het netwerk zo groot is zijn er vaak per node wel meer dan 20 referenties naar andere nodes. Als ik deze 20 referenties zou deleten moet ik dus na 1 stap al 20 nodes onthouden waar ik hetzelfde moet doen, en na 2 stappen worden dit er al 20x20. Dit loopt snel uit de hand. Daarnaast zou ik daarna nog alle nodes moeten gaan kijken of er nog nodes zijn met referenties. Zo ja dan is dit een subnetwerk want dan kon ik er niet bij komen via mijn delete proces. Met dit netwerk moet ik hetzelfde gaan doen etc. Dit kost enorm veel CPU power, zoniet is het onuitvoerbaar.

Wat ik dus eigenlijk zoek is een methode die het omgekeerde doet van 'serialisen' wat het opslaan is van een object in een bytestream, inclusief alle referenties die er gebruikt worden in dit object. (vb: site met alle hyperlinks, en ook alle hyperlinks die in die site van de hyperlink staan, zodat je zonder internet nooit een 404 krijgt).

Iemand ideeen?

N.B. Bedankt voor de check -NMe-. Toch maar een repost gedaan.

[ Voor 3% gewijzigd door Flapmo op 03-05-2005 14:16 ]

[joepP]

Waarom deleten?

Je kan gewoon met BFS/DFS alle nodes aflopen en labelen. Als er daarna nog ongelabelde knopen zijn herhaal je dit proces. Maak je BFS/DFS implementatie recursief, dan ben je direct klaar. Pseudotje:

code:

//init
groupcount = 0;
for i = 1 to n do x(i).group= 0;

//loop
while there are x(j) met x(j).label = 0 do begin
  groupcount++;
  dfscolor(j, groupcount)
end

//dfs
proc dfscolor(i, label) begin
  //color node
  x(i).group = label

  //color children
  for all j: x(j) = neighbour van x(i) do
  if x(j).group = 0 then
    dfscolor(j, label);
end

Looptijd is lineair in aantal nodes als je een beetje slim zoekt naar de volgende niet-gekleurde node. Lijkt me eerlijk gezegd toch behoorlijk basaal...

[NaliXL]

Het is me in dit geval niet helemaal duidelijk wat je met het woord "netwerk" bedoelt, maar als ik zo eens kijk naar wat je hier vertelt, kun je dan niet veel gemakkelijker een database gebruiken voor jouw doel?

[Flapmo]

Cherub schreef op dinsdag 03 mei 2005 @ 15:02:
Het is me in dit geval niet helemaal duidelijk wat je met het woord "netwerk" bedoelt, maar als ik zo eens kijk naar wat je hier vertelt, kun je dan niet veel gemakkelijker een database gebruiken voor jouw doel?

dat is niet de bedoeling, ik denk dat ik inderdaad toch maar ga kijken naar markeren van de nodes die je al gehad hebt. wilde dat eerst express niet gaan doen omdat ik dacht dat het meer werk zou zijn dan simpelweg deleten. Maar deleten neemt een hoop probleempjes met zich mee .