maxFlow - WeAreCAS

Descripción

La acción maxFlow calcula el flujo máximo desde un nodo fuente a un nodo sumidero en un grafo dirigido. El flujo máximo es la cantidad máxima de flujo que puede ser enviada a través de una red. Este problema se puede modelar definiendo un grafo donde los nodos son ubicaciones y los arcos son las rutas entre esas ubicaciones. Cada arco tiene una capacidad que limita la cantidad de flujo que puede pasar a través de él. El objetivo es encontrar la cantidad máxima de flujo que puede ser enviada desde el nodo fuente al nodo sumidero respetando las capacidades de los arcos.

optNetwork.maxFlow { deterministic=TRUE | FALSE, direction="DIRECTED" | "UNDIRECTED", display={...}, distributed=TRUE | FALSE, graph=integer, indexOffset=integer, links={...}, linksVar={...}, logFreqTime=integer, logLevel="AGGRESSIVE" | "BASIC" | "MODERATE" | "NONE", multiLinks=TRUE | FALSE, nodes={...}, nodesVar={...}, nThreads=integer, outGraphList={...}, outLinks={...}, outNodes={...}, outputTables={...}, selfLinks=TRUE | FALSE, sink="string" | double | 64-bit-integer, source="string" | double | 64-bit-integer, standardizedLabels=TRUE | FALSE, standardizedLabelsOut=TRUE | FALSE }

Parámetros

Parámetro	Descripción
deterministic	Cuando se establece en True, asegura que cada invocación (con la misma configuración de máquina y parámetros) produzca el mismo resultado final.
direction	Especifica si se debe considerar el grafo de entrada como dirigido o no dirigido.
display	Especifica una lista de tablas de resultados para enviar al cliente para su visualización.
distributed	Cuando se establece en True, utiliza un grafo distribuido.
graph	Especifica el grafo en memoria a utilizar.
indexOffset	Especifica el desplazamiento del índice para los identificadores en las tablas de datos de salida de registro y resultados.
links	Especifica la tabla de datos de entrada que contiene la información de los arcos del grafo.
linksVar	Especifica los nombres de las variables de datos para la tabla de arcos.
logFreqTime	Controla la frecuencia n (en segundos) para mostrar los registros de iteración para algunos algoritmos.
logLevel	Controla la cantidad de información que se muestra en el registro de SAS.
multiLinks	Cuando se establece en True, incluye multi-arcos cuando se lee un grafo de entrada.
nodes	Especifica la tabla de datos de entrada que contiene la información de los nodos del grafo.
nodesVar	Especifica los nombres de las variables de datos para la tabla de nodos.
nThreads	Especifica el número máximo de hilos a utilizar para el procesamiento multihilo.
outGraphList	Especifica la tabla de datos de salida para contener información resumida sobre los grafos en memoria.
outLinks	Especifica la tabla de datos de salida para contener la información de los arcos del grafo junto con cualquier resultado de los algoritmos que calculan métricas en los arcos.
outNodes	Especifica la tabla de datos de salida para contener la información de los nodos del grafo junto con cualquier resultado de los algoritmos que calculan métricas en los nodos.
outputTables	Lista los nombres de las tablas de resultados para guardar como tablas CAS en el servidor.
selfLinks	Cuando se establece en True, incluye auto-enlaces cuando se lee un grafo de entrada.
sink	Especifica el nodo sumidero para los cálculos de flujo máximo de red.
source	Especifica el nodo fuente para los cálculos de flujo máximo de red.
standardizedLabels	Cuando se establece en True, especifica que los datos del grafo de entrada están en un formato estandarizado.
standardizedLabelsOut	Cuando se establece en True, solicita que los datos del grafo de salida incluyan un formato estandarizado.

Preparación de datos Ver hoja de preparación de datos

Creación de Datos de Ejemplo

Este ejemplo crea una tabla de arcos que representa un grafo dirigido con capacidades. Los nodos 'S' y 'T' se utilizarán como fuente y sumidero respectivamente para el cálculo del flujo máximo.

¡Copiado!

1	PROC CAS;
2	DATA mycas.Links;
3	INFILE DATALINES delimiter=',';
4	INPUT from $ to $ capacity;
5	DATALINES;
6	S,A,3
7	S,B,2
8	A,C,3
9	A,D,4
10	B,C,1
11	B,D,2
12	C,T,2
13	D,T,3
14	;
15	RUN;

Ejemplos

Este ejemplo calcula el flujo máximo desde el nodo 'S' hasta el nodo 'T' en el grafo definido en la tabla 'Links'.

Código SAS® / CAS Código en espera de validación por la comunidad

¡Copiado!

1	PROC CAS;
2	LOADACTIONSET "optNetwork";
3	ACTION optNetwork.maxFlow /
4	links={name="Links"},
5	SOURCE="S",
6	sink="T";
7	RUN;
8	QUIT;

Resultado :
El resultado mostrará el valor del flujo máximo, que es 4, junto con resúmenes del problema y la solución.

Este ejemplo calcula el flujo máximo y guarda el flujo en cada arco en la tabla 'OutLinks' y la partición del corte mínimo en la tabla 'OutNodes'. El corte mínimo separa los nodos en dos conjuntos, {S, A, B, D} y {C, T}, lo que corresponde a un valor de flujo máximo de 4.

Código SAS® / CAS Código en espera de validación por la comunidad

¡Copiado!

1	PROC CAS;
2	LOADACTIONSET "optNetwork";
3	ACTION optNetwork.maxFlow /
4	links={name="Links"},
5	SOURCE="S",
6	sink="T",
7	outLinks={name="OutLinks", replace=true},
8	outNodes={name="OutNodes", replace=true};
9	RUN;
10	ACTION TABLE.fetch / TABLE="OutLinks";
11	RUN;
12	ACTION TABLE.fetch / TABLE="OutNodes";
13	RUN;
14	QUIT;

Resultado :
Se mostrarán tres tablas: la primera con el resumen de la solución y el flujo máximo (4). La segunda (OutLinks) detallará el flujo en cada arco. La tercera (OutNodes) mostrará la partición del corte mínimo (partition), que identifica los nodos alcanzables desde la fuente en el grafo residual.

FAQ

¿Qué es la acción `maxFlow`?

¿Para qué sirve el parámetro `source`?

¿Cuál es la función del parámetro `sink`?

¿Qué especifica el parámetro `direction`?

¿Qué tablas de entrada se pueden utilizar con la acción `maxFlow`?

Descripción

Creación de Datos de Ejemplo

Ejemplos

Ejemplo Simple de Flujo Máximo

Ejemplo Detallado con Tablas de Salida

FAQ