## Examples from the Details section (netsld01)

```/***************************************************************/
/*                                                             */
/*          S A S   S A M P L E   L I B R A R Y                */
/*                                                             */
/*    NAME: netsld01                                           */
/*   TITLE: Examples from the Details section (netsld01)       */
/* PRODUCT: OR                                                 */
/*  SYSTEM: ALL                                                */
/*    KEYS: OR                                                 */
/*   PROCS: OPTMODEL, PRINT, SORT, TRANSPOSE                   */
/*    DATA:                                                    */
/*                                                             */
/* SUPPORT:                          UPDATE:                   */
/*     REF: Examples from the Details section of the           */
/*          network solver documentation.                      */
/*    MISC:                                                    */
/*                                                             */
/***************************************************************/

/* GRAPH INPUT DATA                                            */

input from \$ to \$ weight @@;
datalines;
A B 1   A C 2   A D 4   B C 1   B E 2
B F 5   C E 1   D E 1   E D 1   E F 2
F G 6   G H 1   G I 1   H G 2   H I 3
;

proc optmodel;
set NODES = union{<ni,nj> in LINKS} {ni,nj};

print weight;
put NODES=; /* computed automatically by OPTMODEL */
quit;

proc optmodel;
set NODES = 1..5;
set LINKS = {vi in NODES, vj in NODES: vi < vj};
num distance {<vi,vj> in LINKS} = 10*vi + vj;

set <num,num> TOUR;

/* Build a link set using only nodes 1..4 nodes */
set <num,num> LINKS_BETWEEN_1234 = {vi in 1..3, vj in (vi+1)..4};
/* Build a node subset consisting of nodes 3..5 */
set NODES_345 = 3..5;

/* Implicit network 1: solve over nodes 1..5 -- The original network*/
solve with NETWORK /
out=( tour=TOUR )
tsp
;
put TOUR=;

put _OROPTMODEL_NUM_['OBJECTIVE'];

/* Filter on LINKS: solve over nodes 1..4 */
solve with NETWORK /
out=( tour=TOUR )
tsp
;
put TOUR=;

/* Filter on NODES: solve over nodes 3..5 */
solve with NETWORK /
subgraph=( nodes=NODES_345 )
out=( tour=TOUR )
tsp
;
put TOUR=;

/* Explicit nodes and links: semantic error over nodes 1..5
* Links <u,5> are undefined and no documented default exists. */
solve with NETWORK /
out=( tour=TOUR )
tsp
;

/* make room for tail, head, and weight */
solve with NETWORK /
tsp
;
quit;

/* BICONNECTED COMPONENTS AND ARTICULATION POINTS              */

input from \$ to \$ @@;
datalines;
A B  A F  A G  B C  B D
B E  C D  E F  G I  G H
H I
;

proc optmodel;
set NODES = union{<i,j> in LINKS} {i,j};
set<str> ARTPOINTS;

solve with NETWORK /
loglevel  = moderate
biconcomp
out       = (biconcomp=bicomponent artpoints=ARTPOINTS)
;

print bicomponent;
put ARTPOINTS;
create data LinkSetOut from [from to] biconcomp=bicomponent;
create data NodeSetOut from [node]=ARTPOINTS artpoint=1;
quit;

run;

proc print data=NodeSetOut noobs label;
run;

/* CLIQUE                                                      */

input from to @@;
datalines;
0 1  0 2  0 3  0 4  0 5
0 6  1 2  1 3  1 4  2 3
2 4  2 5  2 6  2 7  2 8
3 4  5 6  7 8  8 9
;

proc optmodel;
set<num,num> CLIQUES;

solve with NETWORK /
clique = (maxcliques=all)
out    = (cliques=CLIQUES)
;

put CLIQUES;
create data Cliques from [clique node]=CLIQUES;
num num_cliques = card(setof {<cid,node> in CLIQUES} cid);
set CLIQUE_IDS = 1..num_cliques;
num size {cid in CLIQUE_IDS} = card(slice(<cid,*>, CLIQUES));
create data CliqueSizes from [clique] size;
quit;

proc print data=Cliques noobs label;
run;

proc print data=CliqueSizes noobs label;
run;

/* CONNECTED COMPONENTS                                        */

/* Connected Components of a Simple Undirected Graph           */

input from \$ to \$ @@;
datalines;
A B  A C  B C  C H  D E  D F  D G  F E  G I  K L
;

proc optmodel;
set NODES = union {<i,j> in LINKS} {i,j};
num component{NODES};

solve with NETWORK /
concomp
out     = (concomp=component)
;

print component;
create data NodeSetOut from [node] concomp=component;
quit;

proc print data=NodeSetOut noobs label;
run;

data NodeSetIn;
input node \$ @@;
datalines;
A  B  C  D  E  F  G  H  I  J  K  L
;

proc optmodel;
set<str> NODES;
num component{NODES};

solve with NETWORK /
nodes   = (include=NODES)
concomp
out     = (concomp=component)
;

print component;
create data NodeSetOut from [node] concomp=component;
quit;

proc print data=NodeSetOut noobs label;
run;

/* Connected Components of a Simple Directed Graph             */

input from \$ to \$ @@;
datalines;
A B  B C  B E  B F  C G
C D  D C  D H  E A  E F
F G  G F  H G  H D
;

proc optmodel;
set NODES = union {<i,j> in LINKS} {i,j};
num component{NODES};

solve with NETWORK /
graph_direction = directed
concomp
out             = (concomp=component)
;

print component;
create data NodeSetOut from [node] concomp=component;
quit;

proc print data=NodeSetOut noobs label;
run;

/* CYCLE                                                       */

input from \$ to \$ @@;
datalines;
A B  A E  B C  C A  C D
D E  D F  E B  E C  F E
;

proc optmodel;
set<num,num,str> CYCLES;

solve with NETWORK /
graph_direction = directed
cycle           = (maxcycles=1)
;
quit;

proc optmodel;
set<num,num,str> CYCLES;

solve with NETWORK /
graph_direction = directed
cycle           = (maxcycles=all)
;
quit;

proc optmodel;
set<num,num,str> CYCLES;

solve with NETWORK /
graph_direction = directed
cycle           = (maxcycles=1)
out             = (cycles=CYCLES)
;

put CYCLES;
create data Cycles from [cycle order node]=CYCLES;
quit;

proc print data=Cycles noobs label;
run;

proc optmodel;
set<num,num,str> CYCLES;

solve with NETWORK /
graph_direction = directed
cycle           = (maxcycles=all)
out             = (cycles=CYCLES)
;

put CYCLES;
create data Cycles from [cycle order node]=CYCLES;
quit;

proc print data=Cycles noobs label;
run;

/* MINIMUM-COST NETWORK FLOW                                   */

input from to weight upper;
datalines;
1 4 2 15
2 1 1 10
2 3 0 10
2 6 6 10
3 4 1  5
3 5 4 10
4 7 5 10
5 6 2 20
5 7 7 15
6 8 8 10
7 8 9 15
;

data NodeSetIn;
input node supply;
datalines;
1  10
2  20
4  -5
7 -15
8 -10
;

proc optmodel;
set NODES = union {<i,j> in LINKS} {i,j};
num supply{NODES} init 0;
read data NodeSetIn into [node] supply;

solve with network /
loglevel        = moderate
logfreq         = 1
graph_direction = directed
nodes           = (lower=supply)
mcf
out             = (flow=flow)
;

print flow;
create data LinkSetOut from [from to] upper cost flow;
quit;

run;

data NodeSetIn;
input node lower upper;
datalines;
1  10  .I
2  20  20
4  .M  -5
7 -15 -15
8 -10  -6
;

proc optmodel;
set <num> NODES;
num supply{NODES};
num supplyUB{NODES}; /* also demand lower bound, if negative */
read data NodeSetIn into NODES=[node] supply=lower supplyUB=upper;

solve with NETWORK /
direction = directed
links     = ( upper = upper weight = cost )
nodes     = ( lower = supply upper = supplyUB )
mcf
out       = ( flow = flow )
;
print flow;
create data LinkSetOut from [from to] upper cost flow;
quit;

run;

/* MINIMUM CUT                                       */

input from to weight @@;
datalines;
1 2 2  1 5 3  2 3 3  2 5 2  2 6 2
3 4 4  3 7 2  4 7 2  4 8 2  5 6 3
6 7 1  7 8 3
;

proc optmodel;
set<num> NODES = union {<i,j> in LINKS} {i,j};
set<num,num> PARTITIONS;
set<num,num,num> CUTSETS;

solve with NETWORK /
loglevel = moderate
mincut   = (maxcuts=3)
out      = (partitions=PARTITIONS cutsets=CUTSETS)
;
set CUTS = setof {<cut,i,j> in CUTSETS} cut;
num minCutWeight {cut in CUTS} = sum {<(cut),i,j> in CUTSETS} weight[i,j];
print minCutWeight;

for { cut in CUTS }
put "Cut ID: "    cut
"Partition: " ( slice( <cut,*>, PARTITIONS ) )
"and "        ( NODES diff slice( <cut,*>, PARTITIONS ) )
"Cut: "       ( slice( <cut,*,*>, CUTSETS ) )
"Weight: "    minCutWeight[cut];

create data MinCut from [mincut from to]=CUTSETS weight[from,to];
num partition {cut in CUTS, node in NODES} =
if <cut,node> in PARTITIONS then 0 else 1;
create data NodeSetOut from [cut node]={CUTS, NODES} partition;
quit;

proc print data=NodeSetOut noobs label;
run;

proc print data=MinCut noobs label;
run;

proc print data=MinCut noobs label;
sum weight;
by mincut;
run;

/* MINIMUM SPANNING TREE                                       */

input from \$ to \$ weight @@;
datalines;
A B  7  A D  5  B C 8  B D 9  B E 7
C E  5  D E 15  D F 6  E F 8  E G 9
F G 11  H I  1  I J 3  H J 2
;

proc optmodel;
set<str,str> FOREST;

solve with NETWORK /
minspantree
out         = (forest=FOREST)
;

put FOREST;
create data MinSpanForest from [from to]=FOREST weight;
quit;

proc print data=MinSpanForest noobs label;
sum weight;
run;

/* SHORTEST PATH                                               */

/* Shortest Paths for All Pairs                                */

input from \$ to \$ weight @@;
datalines;
A B 3  A C 2  A D 6  A E 4  B D 5
B F 5  C E 1  D E 2  D F 1  E F 4
;

proc optmodel;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set NODES = union{<i,j> in LINKS} {i,j};
num path_length{NODES, NODES};

solve with NETWORK /
shortpath
out       = (sppaths=PATHS spweights=path_length)
;

put PATHS;
print path_length;
create data ShortPathP from [source sink order from to]=PATHS
weight[from,to];
create data ShortPathW from [source sink]
path_weight=path_length;
quit;

title 'ShortPathP';
proc print data=ShortPathP noobs label;
run;

title 'ShortPathW';
proc print data=ShortPathW noobs label;
run;

/* Shortest Paths for a Subset of Source-Sink Pairs            */

proc optmodel;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SOURCES = / A C /;
set SINKS   = / B F /;

solve with NETWORK /
shortpath = (source=SOURCES sink=SINKS)
out       = (sppaths=PATHS)
;

put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;

title 'ShortPath';
proc print data=ShortPath noobs label;
run;

/* Shortest Paths for a Subset of Source or Sink Pairs         */

proc optmodel;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SOURCES = / B E /;

solve with NETWORK /
shortpath = (source=SOURCES)
out       = (sppaths=PATHS)
;

put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;

title 'ShortPath';
proc print data=ShortPath noobs label;
run;

proc optmodel;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SINKS = / B E /;

solve with NETWORK /
shortpath = (sink=SINKS)
out       = (sppaths=PATHS)
;

put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;

title 'ShortPath';
proc print data=ShortPath noobs label;
run;

/* Shortest Paths for One Source-Sink Pair                     */

proc optmodel;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set SOURCES = / C /;
set SINKS   = / F /;

solve with NETWORK /
shortpath = (source=SOURCES sink=SINKS)
out       = (sppaths=PATHS)
;

put PATHS;
create data ShortPath from [source sink order from to]=PATHS weight[from,to];
quit;

title 'ShortPath';
proc print data=ShortPath noobs label;
run;

input from \$ to \$ weight count @@;
datalines;
A B 3 1  A C 2 1  A D 6 1  A E 4 1  B D 5 1
B F 5 1  C E 1 1  D E 2 1  D F 1 1  E F 4 1
;

proc optmodel;
set <str,str,num,str,str> PATHS; /* source, sink, order, from, to */
set NODES = union{<i,j> in LINKS} {i,j};
num path_length{i in NODES, j in NODES: i ~= j};

solve with NETWORK /
shortpath
out       = (sppaths=PATHS spweights=path_length)
;

put PATHS;
num path_weight2{source in NODES, sink in NODES: source ~= sink} =
sum {<(source),(sink),order,from,to> in PATHS} count[from,to];
print path_length path_weight2;
create data ShortPathW from [source sink]
path_weight=path_length path_weight2;
quit;

title 'ShortPathW';
proc print data=ShortPathW noobs label;
run;

proc optmodel;
set LINKS            = / <A B> <A C> <B C> <B D> <B E> <D B> <D C> <E D> /;
num weight{LINKS} init [   -1     4     3     2     2     1     5    -3  ];

set NODES = union{<i,j> in LINKS} {i,j};
/* Use the type (in this case, STRING) of NODES but leave PATHS empty */
set PATHS init {NODES,NODES,/0/,NODES,NODES:0};
set SOURCE = /E/, SINK = /B/;
solve with NETWORK /
links     = ( weight = weight )
direction = directed
shortpath = ( source = SOURCE sink = SINK )
out       = ( sppaths = PATHS )
;
put "Path and Weight: " (setof{<s,t,i,u,v> in PATHS} <u,v,weight[u,v]> );

quit;

/* TRANSITIVE CLOSURE                                            */

input from \$ to \$ @@;
datalines;
B C  B D  C B  D A  D C
;

proc optmodel;
set<str,str> CAN_REACH;

solve with NETWORK /
graph_direction = directed
transcl
out = ( closure = CAN_REACH )
;

put CAN_REACH;
create data TransClosure from [from to]=CAN_REACH;
quit;

title 'Transitive Closure';
proc print data=TransClosure noobs label;
run;

/* TRAVELING SALESMAN PROBLEM                                   */

input from \$ to \$ weight @@;
datalines;
A B 1.0   A C 1.0   A D 1.5   B C 2.0   B D 4.0
B E 3.0   C D 3.0   C F 3.0   C H 4.0   D E 1.5
D F 3.0   D G 4.0   E F 1.0   E G 1.0   F G 2.0
F H 4.0   H I 3.0   I J 1.0   C J 5.0   F J 3.0
F I 1.0   H J 1.0
;

proc optmodel;
set<str,str> EDGES;
set<str> NODES = union{<i,j> in EDGES} {i,j};
num weight{EDGES};
num tsp_order{NODES};
set<str,str> TOUR;

solve with NETWORK /
loglevel = moderate
tsp
out      = (order=tsp_order tour=TOUR)
;

put TOUR;
print {<i,j> in TOUR} weight;
print tsp_order;
create data NodeSetOut from [node]         tsp_order;
create data TSPTour    from [from to]=TOUR weight;
quit;

title 'Traveling Salesman Problem';
proc sort data=NodeSetOut;
by tsp_order;
run;

proc print data=NodeSetOut noobs label;
run;

proc print data=TSPTour noobs label;
sum weight;
run;

/* TRAVELING SALESMAN PROBLEM                                   */

input from \$ to \$ weight @@;
datalines;
A B 2.0   A C 1.0   A E 4.0
B A 1.0   B C 2.0   B D 1.0   B E 1.0
C B 2.0   C D 3.0
D A 1.0   D C 1.0   D E 2.0
E A 2.0   E D 1.0
;

proc optmodel;
set<str,str> EDGES;
set<str> NODES = union{<i,j> in EDGES} {i,j};
num weight{EDGES};
num tsp_order{NODES};
set<str,str> TOUR;

solve with NETWORK /
loglevel  = moderate
direction = directed
tsp
out       = (order=tsp_order tour=TOUR)
;

put TOUR;
print {<i,j> in TOUR} weight;
print tsp_order;
create data NodeSetOut from [node]         tsp_order;
create data TSPTour    from [from to]=TOUR weight;
quit;

proc sort data=NodeSetOut;
by tsp_order;
run;

proc print data=NodeSetOut noobs label;
run;

proc print data=TSPTour noobs label;
sum weight;
run;

```