Subgraph ermitteln < Matlab < Mathe-Software < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 10:58 Di 27.10.2009 | | Autor: | Alpha23 |
Hallo!
Ich habe für meine Diplomarbeit einen Algorithmus im Bereich Transportwesen entwickelt und mit MATLAB programmiert. Hänge jetzt an der Laufzeitverbesserung - hochgerechnet einige Wochen Laufzeit ist nicht so schön. ;)
Was ich brauche, ist der Subgraph aller Kanten und Knoten, die von einem Knoten aus erreichbar sind. Der Graph ist kreisfrei, hat ca. 100.000 Knoten und 200.000 Kanten und ist als logische sparse-Matrix gespeichert. Ein Knoten hat maximal zwei Nachfolger, also gibt es pro Zeile maximal zwei Einträge.
Ich lasse mir also per BFS über das kostenlose MatlabBGL-Paket alle Abstände ausgeben, dann sind alle Knoten, die Abstand -1 haben nicht erreichbar. Daher müsste ich in der neuen Adjazenzmatrix eigentlich nur die Zeilen genau dieser Knoten übernehmen.
Der Befehl
Adj_out(reachable~=-1,:)=Adj_in(reachable~=-1,:);
dauert aber teilweise bis zu 10 Minuten!! Wie kann ich diesen Aufruf beschleunigen? Ich habe es bereits mit verschiedenen Schleifen versucht, die brauchen aber noch länger.
Danke für eure Antworten!
Ich habe diese Frage in keinem anderen Forum gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:20 Do 29.10.2009 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
