reverse cuthill mckee < Python < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 19:13 Fr 03.08.2012 | | Autor: | jumape |
| Aufgabe | Hallo,
ich möchte als Vorkonditionierer zur Lösung eines großen linearen GLS mit einer sparse-Matrix den reverse cuthill mc Kee algorithmus anwenden.
(networkx.utils.rcm) |
Jetzt muss man da aber als Input einen Graphen angeben. Jetzt ist meine Frage, wie ich aus meiner Matrix den Graphen? Gibt es dafür eine Routine bei networkx?
Vielen Dank im Voraus
jumape
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:48 So 05.08.2012 | | Autor: | felixf |
Moin jumape!
> ich möchte als Vorkonditionierer zur Lösung eines großen
> linearen GLS mit einer sparse-Matrix den reverse cuthill mc
> Kee algorithmus anwenden.
> (networkx.utils.rcm)
> Jetzt muss man da aber als Input einen Graphen angeben.
> Jetzt ist meine Frage, wie ich aus meiner Matrix den
> Graphen? Gibt es dafür eine Routine bei networkx?
Zu networkx kann ich dir nichts sagen, aber:
Deine Matrix (nennen wir sie $A$) hat ja Eintraege = 0 und Eintraege [mm] $\neq [/mm] 0$. Daraus machst du jetzt eine Matrix $A'$ mit nur den Eintraegen 0 und 1: alle Eintraege [mm] $\neq [/mm] 0$ werden zu 1, und die $= 0$ bleiben 0. Die so entstandene Matrix ist die ![[]](/images/popup.gif) Adjazenzmatrix eines Graphens: ist $A' = [mm] (a_{ij})_{ij}$, [/mm] so ist [mm] $a_{ij} [/mm] = 1$ genau dann, wenn zwischen den Ecken $i$ und $j$ des Graphens eine Kante ist.
Du kannst also den (ungerichteten!) Graph aus den Eintraegen [mm] $\neq [/mm] 0$ von $A$ zusammensetzen: jeder Eintrag $(i, j)$ der ungleich 0 ist liefert eine Kante des Graphen. (Da die Matrix $A'$ symmetrisch ist liefert dies einen ungerichteten Graph, sprich $(i, j)$ ist genau dann eine Kante, wenn $(j, i)$ ebenfalls eine ist. Falls $A'$ nicht symmetrisch ist, musst du sie bzw. den Graph symmetrisch machen: der Cuthill-McKee-Algorithmus moechte einen symmetrischen Graph.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Mo 03.09.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
