Die Aktion `maxFlow` berechnet den maximalen Fluss in einem Graphen zwischen einem angegebenen Quellknoten und einem Senkenknoten. Der maximale Fluss ist die größte Menge an 'Material', die von der Quelle zur Senke durch das Netzwerk von Kanten mit begrenzten Kapazitäten transportiert werden kann. Dieses Problem ist fundamental in der Netzwerkoptimierung und findet Anwendung in Logistik, Telekommunikation und vielen anderen Bereichen.
| Parameter | Beschreibung |
|---|---|
| deterministic | Wenn auf True gesetzt, stellt sicher, dass jeder Aufruf (mit der gleichen Maschinenkonfiguration und Parametereinstellungen) das gleiche Endergebnis liefert. |
| direction | Gibt an, ob der Eingabegraph als gerichtet oder ungerichtet betrachtet werden soll. |
| display | Gibt eine Liste von Ergebnistabellen an, die zur Anzeige an den Client gesendet werden sollen. |
| distributed | Wenn auf True gesetzt, wird ein verteilter Graph verwendet. |
| graph | Gibt den zu verwendenden In-Memory-Graphen an. |
| indexOffset | Gibt den Index-Offset für Bezeichner in den Protokoll- und Ergebnisausgabetabellen an. |
| links | Gibt die Eingabedatentabelle an, die die Informationen zu den Graphkanten enthält. |
| linksVar | Gibt die Namen der Datenvariablen für die Kantentabelle an. |
| logFreqTime | Steuert die Frequenz n (in Sekunden) für die Anzeige von Iterationsprotokollen für einige Algorithmen. |
| logLevel | Steuert die Menge der im SAS-Protokoll angezeigten Informationen. |
| multiLinks | Wenn auf True gesetzt, werden Mehrfachkanten beim Einlesen eines Graphen berücksichtigt. |
| nodes | Gibt die Eingabedatentabelle an, die die Informationen zu den Graphknoten enthält. |
| nodesVar | Gibt die Namen der Datenvariablen für die Knotentabelle an. |
| nThreads | Gibt die maximale Anzahl von Threads an, die für die Multithread-Verarbeitung verwendet werden sollen. |
| outGraphList | Gibt die Ausgabedatentabelle an, die Zusammenfassungsinformationen über In-Memory-Graphen enthalten soll. |
| outLinks | Gibt die Ausgabedatentabelle an, die die Kanteninformationen des Graphen zusammen mit allen Ergebnissen der Algorithmen enthält, die Metriken für Kanten berechnen. |
| outNodes | Gibt die Ausgabedatentabelle an, die die Knoteninformationen des Graphen zusammen mit allen Ergebnissen der Algorithmen enthält, die Metriken für Knoten berechnen. |
| outputTables | Listet die Namen der Ergebnistabellen auf, die als CAS-Tabellen auf dem Server gespeichert werden sollen. |
| selfLinks | Wenn auf True gesetzt, werden Eigenschleifen beim Einlesen eines Graphen berücksichtigt. |
| sink | Gibt den Senkenknoten für die Berechnungen des maximalen Netzwerkflusses an. |
| source | Gibt den Quellenknoten für die Berechnungen des maximalen Netzwerkflusses an. |
| standardizedLabels | Wenn auf True gesetzt, wird angegeben, dass die Eingabegraphendaten in einem standardisierten Format vorliegen. |
| standardizedLabelsOut | Wenn auf True gesetzt, wird angefordert, dass die Ausgabegraphendaten ein standardisiertes Format enthalten. |
Dieser SAS-Code erstellt eine CAS-Tabelle namens `LinkData`, die einen gerichteten Graphen mit Kantenkapazitäten darstellt. Diese Daten werden verwendet, um den maximalen Fluss von einem Quell- zu einem Senkenknoten zu berechnen.
| 1 | DATA casuser.LinkData; |
| 2 | INFILE DATALINES delimiter=','; |
| 3 | INPUT from $ to $ capacity; |
| 4 | DATALINES; |
| 5 | A,B,3 |
| 6 | A,C,2 |
| 7 | B,D,2 |
| 8 | B,E,3 |
| 9 | C,D,3 |
| 10 | C,F,2 |
| 11 | E,G,1 |
| 12 | D,G,4 |
| 13 | F,G,3 |
| 14 | ; |
| 15 | RUN; |
Dieses Beispiel berechnet den maximalen Fluss von einem Quellknoten 'A' zu einem Senkenknoten 'G' unter Verwendung der zuvor erstellten `LinkData`-Tabelle. Die Ergebnisse, einschließlich des Flusses auf jeder Kante, werden in der Tabelle `MaxFlowLinks` gespeichert.
| 1 | PROC CAS; |
| 2 | ACTION optNetwork.maxFlow / |
| 3 | links={name='LinkData'}, |
| 4 | SOURCE='A', |
| 5 | sink='G', |
| 6 | outLinks={name='MaxFlowLinks', replace=true}; |
| 7 | RUN; |
| 8 | QUIT; |
Dieses Beispiel erweitert die einfache Berechnung, indem es auch die minimale Schnittpartition ausgibt. Die Partition trennt die Knoten in zwei Mengen: eine, die von der Quelle aus im Residualgraphen erreichbar ist, und eine, die es nicht ist. Dies ist nützlich, um Engpässe im Netzwerk zu identifizieren.
| 1 | PROC CAS; |
| 2 | ACTION optNetwork.maxFlow / |
| 3 | links={name='LinkData'}, |
| 4 | SOURCE='A', |
| 5 | sink='G', |
| 6 | outLinks={name='MaxFlowLinks', replace=true}, |
| 7 | outNodes={name='MinCutNodes', replace=true}; |
| 8 | RUN; |
| 9 | QUIT; |