function[Wedg,Theta_sw,Theta_tw] = scfprledg(e_s,e_ls,e_t,e_lt)
% Comments updated on 17.09.2022
% Code updated on 14.02.2021 (Version-1)
% This code produces the spanning cycle families (SCFs) of a given digraph,
% having parallel edges (even more than two). The inputs to this function
% are vectors: 1) e_s (starting vertices of each edge in the digraph
% which are not selp-loops), 2) e_ls (starting vertices of each
% self-loops in the digraph), 3) e_t (terminating/final vertices of each
% edge in the digraph, which are not self-loops) and 4) e_lt
% (terminating/final vertices of self-loops in the digraph). A unique
% number (the highest number vertex + 2+i) is attached to each edge, with
% increasing order to identyfy the different edges.
% The outputs of this function are two matrices Theta_ws and Theta_wt,
% where k^{th} rows of Theta_ws and Theta_wt corresponds to the initial
% and final vertices, respectively, of the edges involved in the
% k^{th} spanning cycle family, with unique numbers are attached so as to
% identify the edges involved in the SCF. Further, Wedg matrix is
% obtained, whose 1st row and second row provides the starting and ending
% vertex indices of all the edges in the digraph G. The third row
% provides the UINs assigned to those edges.
% =========================================================================
sb = [e_s e_ls]; % Initial/Starting vertices
tb = [e_t e_lt]; % Final/Terminating vertices
m = length(sb); % Total number of edges in G including selfloops
n = max(sb); % Total number of vertices in G
l = length(e_ls); % Number of self-loops in G
wt=[]; % Assignment of UINs to each edges with vector wt
for i=1:1:m
mxo = n + (i+2);
wt = [wt mxo];
end
Wedg = [sb;tb;wt];
%% Plotting of graph
% G = digraph(sb,tb);
% plot(G,'Layout','layered')
% e = G.Edges;
%% Computation of incidence matrix (Self-loop parts are set to zero)
les=length(e_s);
Inci=zeros(n,les);
for j=1:1:les
Inci(e_s(1,j),j)=-1;
Inci(e_t(1,j),j)=1;
end
Ig = Inci; % Incidence matrix of the removed self-loop digraph
Inci_wt = [Inci;wt(1,1:les)]; % Incidence matrix with UINs attached at the
% end column.
SLz = zeros(n,l);
Iga = [Ig SLz];
I_gw = [Iga;wt];
%% Computation of spanning cycle families
v = 1:1:m;
C_mb = nchoosek(v,n); % all possible combinations of the elements of v,
% taken n at a time.
Csz = size(C_mb);
p = Csz(1);
c_s = [];
c_t = [];
T_s = [];
T_t = [];
Tewt_s = [];
Tewt_t = [];
c_sl = [];
c_tl = [];
T_ls = [];
T_lt = [];
Twt_lt = [];
Twt_ls = [];
for i = 1:1:p
M = Iga(:,C_mb(i,:)); % Construction of a matrix from Iga, taken n
% columns at a time
M_w = I_gw(:,C_mb(i,:));
sm = sum(M,2); % column sums
nzs = nnz(sm); % Number of non-zero entries in sm
zrc_p = find(sum(abs(M)) == 0); % zero column positions
zrr_p = find(sum(abs(M),2) == 0)'; % zero row positions
nzp_c = nnz(zrc_p);
nzp_r = nnz(zrr_p);
% The condition 2 (there are no zero rows in M) and condition 3
% (the addition of all columns of M is equal to a zero vector) of
% Proposition 11 are verified next.
if (nzs == 0) && (nzp_r == 0)
% column sum of M is equal to a zero vector, and there is no zero rows
S = M;
S_w = M_w;
for q = 1:1:n
svtx = find(S(:,q) == -1); % Find the position of -1 in the qth
% column
tvtx = find(S(:,q) == 1); % Find the position of 1 in the qth
% column
c_s = [c_s svtx];
c_t = [c_t tvtx];
end
Edg_wt = S_w(n+1,:);
Cews = [c_s Edg_wt];
Cewt = [c_t Edg_wt];
T_s = [T_s;c_s];
Tewt_s = [Tewt_s;Cews]; % T_sw
T_t = [T_t;c_t];
Tewt_t = [Tewt_t;Cewt]; % T_tw
c_s = [];
c_t = [];
else
% column sum of M is equal to zero and there is atleast one zero
% column and the number of zero rows equal to number of zero
% columns (Conditions of Proposition 12 are verified next).
if (nzs == 0) && (nzp_c ~= 0) && (nzp_c == nzp_r)
H_l = M;
H_lw = M_w;
% Next, we will verify if there are self-loops in digraph G,
% corresponding to the zero rows of H_l. For this, following
% steps are performed.
s_pl = intersect(zrr_p,e_ls); % This gives the list of zero
% rows in H_l, in increasing
% order, if self-loops appear in
% the digraph in those vertices.
% Since all the columns of I_gw, corresponding to the self-loops
% in digraph G, are zero columns, it is important to identify
% the correct UINs for self-loops. For this following steps are
% performed.
n_r = n-nzp_r; % Number of non-zero rows/columns
cl=n_r+1;
[~,wt_pos]=ismember(H_lw(end,cl:end),wt(end,:)); % This gives the
% position of the UINs, corresponding to the zero columns in
% H_lw, in the UINs vector wt.
Lup = sb(1,wt_pos); % This gives the elements of sb vector,
% determined by the vector wt_pos. These are
% essentially the indices of vertices of the digraph where
% self loops present.
Lup_inc = sort(Lup); % Writing elements in increasing order
Isq = isequal(s_pl,Lup_inc);
if Isq == 1 % Test if the vertices obtained in s_pl
% (zero rows of H_l) are same as the vertices
% obtained in Lup, which are obtained through
% the UINs.
S_l = H_l;
S_lw = H_lw;
for j = 1:1:n_r
stvtx = find(S_l(:,j) == -1);
trvtx = find(S_l(:,j) == 1);
c_sl = [c_sl stvtx];
c_tl = [c_tl trvtx];
end
l_s = [c_sl s_pl];
l_t = [c_tl s_pl];
Ledg_wt = S_lw(end,:);
Lews = [l_s Ledg_wt];
Lewt = [l_t Ledg_wt];
T_ls = [T_ls; l_s];
Twt_ls = [Twt_ls; Lews];
T_lt = [T_lt; l_t];
Twt_lt = [Twt_lt; Lewt];
c_sl = []; c_tl = [];
end
end
end
end
Theta_sw = [Tewt_s;Twt_ls];
Theta_tw = [Tewt_t;Twt_lt];