Datenstruktur für Netze gesucht

[Neo.P5]

Hallo,

ich suche eine Datenstruktur um ein Netz von gleichrangigen Objekten darzustellen.
Als Beispiel das Netz der Webseiten des Internets.

Jedes Objekt kann Referenzen auf andere (gleiche) Objekte haben. Diese haben wiederum Referenzen auf andere (gleiche) Objekte und/oder auf das vorherige Element zurück.

Zum Beispiel: Eine Webseite hat eine Referenz auf eine andere Seite. Diese wiederum kann wieder auf mehrere weitere Seiten zeigen. (natürlich auch wieder zurück). Andere Webseiten verweisen auchauf die erste Webseite, usw...


Mein Problem besteht nun darin, dass ich nicht einfach eine Baumstruktur verwenden kann, da es ja keinen Wurzelknoten gibt und somit auch keine Hirarchie der Knoten untereinander (eben ein Netz 🙂.

Zudem habe ich noch die Anforderung, dass diese Struktur u.U. sehr sehr viele Elemente erfassen muss, schnell durchsucht werden sollte und auf eine Datenbank abgebildet werden soll (vorzugsweise mit Hibernate).

Ich hoffe ihr habt eine Idee oder Ansatz für mich...

viele Grüße...

Neo

 

[stev.glasow]

was spricht gegen eine stinknormale relation ?

 

[Neo.P5]

Du meinst sowas wie..

public class IndexNode {

    private Domain domain;

    private ArrayList<IndexNode> externalReferenzes = new ArrayList< IndexNode >();

    /**
     * Konstruktor
     */
    public QSearchIndexNode(Domain domain) {
        this.domain = domain;
    }

}

Da hab ich irgendwie ein Problem mit dem Einfügen. Jedes Objekt darf nur einmal vorkommen, obwohl mehrere verschiedene Knoten darauf zeigen können und es selbst wiederum auf mehrere Objekte zeigt.
Ich bekomme das mit der Datenkonsitenz nicht hin. Außerdem weis ich nicht wie ich die Suche gestalten soll (ja: rekursiv).
Allerdings komme ich bei rekursiver Suche niemals zum Ende; es sein denn ich merke mir wo ich schon war.
Dann bekomme ich aber das Problem, dass die Datenstruktur mehrere Millionen Einträge enthalten kann und mehrere Suchen in der Sekunde durchgeführt werden müssen.

Ich dachte also an etwas optimierteres...

Trotzdem vielen Dank schonmal...

Ein Guter Anfang ist der erste Schritt des Weges...


Neo

 

[SebiB90]

Vllt. hilft dir das: http://de.wikipedia.org/wiki/Repräsentation_von_Graphen_im_Computer

 

[Neo.P5]

Danke auch dir.

Der Tipp mit den gerichteten Graphen ist super. Da hab ich natürlich mal wieder nicht dran gedacht.
Leider hab ich sowas bis jetzt noch nicht implementiert. Hat da evtl. jemand Praxiserfahrung mit, oder ein Beispiel?

Weiß evtl. jemand wie sich eine Suche auf so einem Graphen in der Praxis verhällt bzw. wie schnell so was ist?

vielen vielen Dank für den nützlichen Hinweis...

Gruß Neo

 

[0x7F800000]

1) Was heißt "problem mit dem Einfügen"? Wenn du alle Knoten erstmal in irgendeiner HashTable abspeicherst, und dann mit irgendsoeiner methode wie "addConnections(Node[] nodes)" die gerichteten Kanten einfügst, dann hast du doch stets nur eine einzige lange Collection, in der alle Knoten genau einmal vorkommen, und die untereinander verbunden sind.

2) Was heißt "Suche auf einem Graphen"? Was willst du da "suchen"? Knoten? Wege zwischen den Knoten?

 

[Guest]

@Andrey: ich glaube du beziehst dich noch auf mein Beispiel mit der "stinknormale relation" (oder Irre ich mich?). Diese Idee wurde mittlerweile verworfen und durch den gerichteten Grafen ersetzt.

Suchen bedeutet in diesem Falle eine bestimmte Menge an Knoten zu ermitteln auf die ein bestimmtes Suchkriterium (z.B. Name des Knotens enthällt ein "A") zutrifft und diese Menge sortiert nach deren Trefferwahrscheinlichkeit zurück zu geben.

Die Kanten unter den Knoten sind für die Suche vorerst nur zweitrangig; die Beziehung der Knoten untereinander wird später in einem anderen Programmschritt ausgewertet und wird für das Ranking der Knoten/Suchergebnisse verwendet (Wie viele ausgehende/Eingehende verbindungen,...).

Viele Grüße Neo...

 

[0x7F800000]

@Andrey: ich glaube du beziehst dich noch auf mein Beispiel mit der "stinknormale relation" (oder Irre ich mich?). Diese Idee wurde mittlerweile verworfen und durch den gerichteten Grafen ersetzt.

Aaaaha^^ klingt einleuchtend. Würdest du aber vielleicht doch nochmal erläutern, was deiner meinung nach der Unterschied zwischen einem "gerichteten Graph" und einer "stinknormalen Relation" sein soll? ???:L

Suchen bedeutet in diesem Falle eine bestimmte Menge an Knoten zu ermitteln auf die ein bestimmtes Suchkriterium (z.B. Name des Knotens enthällt ein "A") zutrifft und diese Menge sortiert nach deren Trefferwahrscheinlichkeit zurück zu geben.

Nja, für solche Kriterien ist es erstmal egal, ob das jetzt ein Teil eines Netzes ist oder sonstwas. Im schlimmsten Fall musst du einfach alle abgespeicherten Knoten durchgehen, schauen ob die das Kriterium erfüllen.
Etwas schöner wäre es, wenn die Kriterien nicht zu allgemein wären, sodass du die Knoten schon vorher einmal ordnen könntest, um später nicht alle Knoten durchgehen zu müssen. Irgendeine Sortierung wäre ganz toll.

 

[Neo.P5]

ja eine sortierung wäre sinnvoll. da hst du recht.

ich habe mich jetzt dazu entschluss lucene von apache zu verwenden um einen entsprechenden suchindex aufzubauen. die reladion wollte ich versuchen mit der hinterlegungn von id´s zu berücksichtigen...

ich meld mich nochmal wenn ich soweit bin.

p.s.: bitte entschlusdigt, dass ich so lange nicht geantwortet habe. ich war leider verhindert...