Network Structure Constraints

A graph is said to be feasible if it satisfies all network structure constraints (NSCs). This page lists all available predefined NSCs and how to specify custom NSC checking functions. Many of the predefined NSCs are used during graph generation to improve the efficiency of the generation process (so should be used instead of a custom NSC checking function if applicable).

A specific problem's NSCs are parsed, data type and error checked, and assigned required default values in PMA_DefaultNSC.m.

Below, the number of component types Nt is defined by Nt = numel(L).

Predefined NSCs

NSC.connected - Connected Graph

Boolean defining if the graphs must be a connected graph (true) or disconnected graphs allowed (false).

NSC.connected = false; % [default] connected graph not required
NSC.connected = true; % connected graph required

---

NSC.loops - Loops

Scalar or appropriately-sized vector (Nt x 1) defining the maximum number of loops for each component type

NSC.loops = inf; % [default] no constraints on the number of loops
NSC.loops = 1; % allow a maximum of one loop per component
NSC.loops = 0; % no loops
NSC.loops = inf(Nt,1); % no constraints on the number of loops
NSC.loops = ones(Nt,1); % allow a maximum of one loop per component
NSC.loops = zeros(Nt,1); % no loops
NSC.loops = [0;1;2]; % no loops for L1, maximum 1 loop for L2, maximum 2 loops for L3

---

NSC.simple - Simple Components

Scalar or appropriately-sized vector (Nt x 1) defining if multiedges are allowed for each component type.

NSC.simple = 0; % [default] multiedges allowed
NSC.simple = 1; % no multiedges
NSC.simple = zeros(Nt,1); % multiedges allowed
NSC.simple = ones(Nt,1); % no multiedges (but maybe loops)
NSC.simple = [1;0;1]; % multiedges allowed on L1 and L3 but not L2

NOTE: this will be changed to NSC.multiedge in the future.

---

NSC.directA - Reduced Potential Adjacency Matrix

Appropriately-sized boolean matrix (Nt x Nt) where 1 indicates a connection is allowed between the component types indexed by the row and column index and 0 indicates this connection type is not allowed.

NSC.directA = ones(Nt); % [default] all connections are allowed
NSC.directA = zero(Nt); % no connections are allowed
NSC.directA = ~diag(ones(Nt,1)); % no similar components types connected (coloring-like problems)
NSC.directA = [0,1;1,0]; % L1-L2 connections allowed but not L1-L1 or L2-L2

---

NSC.lineTriple - Line-Connectivity Constraints

Matrix of size n x 3 where n is the number of line-connectivity constraints. Each row is a triple of integers [#1,#2,#3] corresponding to component types in L and is interpreted as: if L(1) and L(2) are connected, don't ever connect L(2) to L(3).

NSC.lineTriple = []; % [default] no line-connectivity constraints
NSC.lineTriple = [1,2,3]; % if L1 and L2 are connected, don't ever connect L2 to L3.
NSC.lineTriple(2,:) = [3,2,3]; % 2nd constraint; if L3 and L2 are connected, don't ever connect L2 to another L3.

---

NSC.Nr - Replicate Bounds

Two element vector defining upper and lower bounds on the total number of replicates (vertices) in each catalog.

NSC.Nr = [0 inf]; % [default] no replicate bound constraints
NSC.Nr = [2 4]; % between 2 and 4 replicates (vertices)

---

NSC.Np - Port Bounds

Two element vector defining upper and lower bounds on the total number of ports in each catalog. Similar to twice the number of edges were loops count twice. Each bound must be even, as is the case for all catalogs.

NSC.Np = [0 inf]; % [default] no port bound constraints
NSC.Np = [6 14]; % between 6 and 14 ports

---

NSC.S - Structured Components

NOTE: currently broken.

NSC.S = []; % [default] currently broken

Custom NSCs

Two different types of user-defined NSC checking functions can be specified.

---

NSC.userCatalogNSC - User-Defined Catalog NSC Checker

A user-defined catalog-only NSC checking function can be specified. It will be applied after all subcatalogs are generated and predefined catalog-only NSCs checked. The inputs are:

• L is the original label sequence
• Ls is the list of all subcatalog indexed label sequences
• Rs is the list of all subcatalog replicate sequences
• Ps is the list of all subcatalog port sequences
• NSC is the NSC structure
• opts is the options structure

The outputs are the [Ls,Rs,Ps] representing all subcatalogs that satisfy the user-defined NSCs.

NSC.userCatalogNSC = []; % empty by default
NSC.userCatalogNSC = @(L,Ls,Rs,Ps,NSC,opts) myCatalogNSCfunc(L,Ls,Rs,Ps,NSC,opts);

---

NSC.userGraphNSC - User-Defined Graph NSC Checker

A user-defined NSC checking function can be specified. It will be applied after all graphs are generated and predefined NSCs checked. The inputs are:

• pp is the information structure for the current graph (such as labels)
• A is the adjacency matrix
• feasibleFlag denotes if the current graph is still feasible

The outputs are the same [pp,A,feasibleFlag] where all outputs may be modified as needed in the user function.

NSC.userGraphNSC = []; % empty by default
NSC.userGraphNSC = @(pp,A,feasibleFlag) myGraphNSCfunc(pp,A,feasibleFlag);

List of Default Values

NSC.connected = false; % [default] connected graph not required
NSC.loops = inf; % [default] no constraints on the number of loops
NSC.simple = 0; % [default] multiedges allowed
NSC.directA = ones(Nt); % [default] all connections are allowed
NSC.lineTriple = []; % [default] no line-connectivity constraints
NSC.Nr = [0 inf]; % [default] no replicate bound constraints
NSC.Np = [0 inf]; % [default] no port bound constraints
NSC.S = []; % [default] currently broken
% NSC.userCatalogNSC = @(L,Ls,Rs,Ps,NSC,opts) myCatalogNSCfunc(L,Ls,Rs,Ps,NSC,opts); % none by default
% NSC.userGraphNSC = @(pp,A,feasibleFlag) myGraphNSCfunc(pp,A,feasibleFlag); % none by default