Darstellung einer dynamischen Matrix

[SebiB90]

Hi,

habt ihr eine Idee, wie man eine dynamisch erweiterbare Matrix erstellen kann? Ich brauch eigentlich ein 2d int array bei dem man Spalten und Zeilen hinzufügen kann.

Meine einzige Idee sind verschaltelte ArrayListen

ArrayList<ArrayList<Integer>> matrix = new ArrayList<ArrayList<Integer>>(5);
matrix.add(new ArrayList<Integer>(6));
//das ganze noch 4 weitere male

In einer Dimension diese Matrix zu erweitern wäre ja ganz einfach:

matrix.add(new ArrayList<Integer>(6));

allerdings wie kann ich die andere Dimension erweitern? Müsste dann ja jede Liste einzeln erweitern und das wäre schon umständlich =/

Hättet ihr eine Idee, wie man das einfacher realisieren könnte?

Danke im vorraus
SebiB90

 

[Spacerat]

Vllt. ein eindimensionales Array mit Zeilen * Spalten als Elemente. Dazu die Anzahl der Zeilen un Spalten zusätzlich speichern. Der Zugriff könnte dann schonmal mit Zeile * Zeilen + Spalte erfolgen. Die Erweiterung um eine Zeile ist dann im Prinzip kein Thema. Nur für ein performantes Hinzufügen von Spalten habe ich leider keine konkrete Idee.

 

[0x7F800000]

könntest du bitte näher erläutern wozu du das brauchst bzw was du damit vorhast?
Bei dünnbesetzten matrizen könnte man je nach implementierung einfach neuen eintrag reinschmeißen und die zeilen/spalten ein wenig umbenennen, was sehr schnell gehen würde.
(Sowas hier: http://de.wikipedia.org/wiki/Compressed_Row_Storage könnte man leicht abwandeln, und schon würde es gehen)
Bei dicht besetzten matrizen ist ArrayList<ArrayList<X>> eine einigermaßen passable Lösung, allerdings musst du bei einfügen von Spalten ziemlich viel zeugs umkopieren, das dauert ewig.

Wenn du dichte matrix als eine Art "in zwei richtungen" verkettete Liste implementierst, dann hast du da zwar kein random access mehr, aber kannst die stets sehr schnell addieren und multiplizieren (bei einigen Algos könnte es aber ein ziemlicher krampf werden, hab's nie ausprobiert) und da könntest du sehr billig neue spalten und zeilen direkt an die richtige stelle einfügen.

Ist das wirklich nötig? Was willst du denn damit anstellen?

 

[SebiB90]

Danke schonmal.
CRS sieht interessant aus. Allerdings ist die Matrix nicht unbedingt dünn(ab wann kann man überhaupt dünn sagen, wäre eine 50% befüllte Matrix noch dünn?) besiedelt, wobei sie je größer sie wird immer dünner besiedelt sein müsste.

Was ich eigentlich vor habe ist folgendes: Ich möchte einen Graph mit Mehrfachkanten darstellen. Da ich an beiden Enden der Kante eine Information(ein Integer Wert) brauche, nutze ich eine Inzidenzmatrix/Knoten-Kanten-Matrix ( http://de.wikipedia.org/wiki/Repräsentation_von_Graphen_im_Computer#Inzidenzmatrix ). Da der Graph erst im Programm aufgebaut werden soll vom Nutzer, brauch ich eine erweiterbare Matrix.

 

[0x7F800000]

Üüüiii... 😱 ne, das kannst du glatt vergessen 😉
Zum einen sind Graphen bei allen möglichen Anwendungen eh tendentiell eher dünnbesetzt, zum anderen ist das mit "erweiterbarer matrix" unverhältnismäßig kompliziert, und imho auch unnötig. Verwalte das in einer Adjazenzliste, ist fast immer besser.

 

[SebiB90]

Das Problem ist nur, dass ich bei Adjazenzliste nicht weiß, wie ich die Informationen an den Kantenenden speichern soll.

 

[0x7F800000]

Was sind "Kantenenden"?
Ist doch vollkommen egal, wie das Objekt "Kante" aussieht. Du kannst da "Inhalt der kante" "Gewicht der Kante" "Ende der Kante" "Richtung der Kante" "7 kleine Füßchen der Kante" oder sonstwas dranhängen. Hauptsache die Kante wird aus dem Knoten verlinkt, statt einfach nur in eine Matrix eingetragen.

 

[SebiB90]

Was sind "Kantenenden"?

Hm...nehmen wir mal eine Assoziation in einem UML Diagramm. Da kann man auch bei beiden Enden eine Multiplizität angeben. Und sowas meine ich. Also ich will kein UML darstellen, aber an einer Kante 2 Integer Werte speichern 😉

Hab grad vllt. ne Denkblokade und seh nicht wie man das bei einer Adjazenzliste macht =/

 

[0x7F800000]

eine recht simple variante:
[HIGHLIGHT="Java"]
class Edge{
Node target; //wohin zeigt die Kante? (man kann auch beide Endknoten speichern)
EdgeData additionalInformation; //zum beispiel irgendein Tupel der unter anderem zwei int's enthält
}

class Node{
Collection<Edge> outcomingEdges;
NodeData additionalInformation;
}

/*
* "adjazenzliste" ist einfach nur eine collection von nodes, die wissen ja jeweils
* selbst wie sie untereinander verbunden sind
*/
Collection<Node> nodes=new LinkedList<Nodes>();
Node a=new Node(NodeData xyz);
Node b=new Node(NodeData zxy);
a.addEdge(/*wohin?*/b,/*zusatzinfos?*/123,789);
nodes.add(a);
nodes.add(b);
[/HIGHLIGHT]
du kannst dann natürlich noch die eingehenden kanten oder die Knoten von den die kante ausgeht mitspeichern, kommt drauf an ob man da in alle richtungen navigieren will, oder lauter nur "einbahnstraßen" braucht.

Und naja, wie gesagt... "Adjazenzliste" muss eigentlich keine Liste sein, und sie muss jetzt auch keine "Indizes" auf andere Knoten beinhalten, auch wenn Wikipedia das suggeriert. Es geht halt einfach darum, dass alles durch Referenzen verbunden wird, statt alle kanten in eine Matrix zu stopfen. Das ist so zu sagen die "natürlichere" Representation eines Graphen im Speicher.

 

[Marco13]

Ob die Knoten dann die Kanten "direkt" speichern sollten, ist eine andere Frage - man könnte auch ein interface machen, wo man sowas wie
Set<Edge> getOutgoingEdgesOf(Node node) { ... }
abfragt, und ob da dann eine Adjazenzliste oder eine Matrix dahintersteckt, ist egal.