Code covered by the BSD License  

Highlights from
Count Loops in a Graph

image thumbnail

Count Loops in a Graph

by

 

12 Apr 2006 (Updated )

Calculates the number of loops in a graph consisting of nodes and edges

loops_gui(cmd)
function loops_gui(cmd)
%LOOPS_GUI  Creates a GUI that counts the number of loops in a network
% This code counts the number of loops (cycles) in a network (graph) that
% is composed of nodes and edges. It employs an iterative algorithm that
% transforms the network into a tree (the ILCA - Iterative Loop Counting
% Algorithm). This is a "brute force" technique as there are no known (to
% my knowledge anyway) algorithms for providing a good estimation.
% 
% AUTHOR:   Joseph Kirk,2/2007
% EMAIL:    <jdkirk630@gmail.com>
% USAGE:    >> loops_gui;
% NOTES:    Refer to the README and the DETAILS files for more info

global HFIG NET LOOPLIST AXN AXH NUMLOOPS LOOPDIST ...
    NETPROPS REDUCENET COUNTLOOPS SAVENET SAVELOOPS CLEAR;

if nargin  ~=  1
    HFIG = figure('Name','Count Loops in a Network of Nodes and Edges','Numbertitle','off', ...
        'Menubar','none','Color',[0.8 0.8 0.8],'Position',[25,50,750,450],'Resize','off');
    AXN = axes('Units','pixels','Position',[30 95 300 300],'Visible','off');
    AXH = axes('Units','pixels','Position',[420 95 300 300],'Visible','off');
    FILEMENU = uimenu('Label','File');
    uimenu(FILEMENU,'Label','Load Net','Callback',[mfilename,'(''GETNET'')'],'Accelerator','N');
    uimenu(FILEMENU,'Label','Clear','Callback',[mfilename,'(''CLEAR'')']);
    uimenu(FILEMENU,'Label','Exit','Callback',[mfilename,'(''CLOSE'')'],'Separator','on');
    HELPMENU = uimenu('Label','Help');
    uimenu(HELPMENU,'Label','Help','Callback','msgbox(''Click the buttons! :)'',''Help'')');
    uimenu(HELPMENU,'Label','Readme','Callback','README');
    uimenu(HELPMENU,'Label','Algorithm Description','Callback','DETAILS');
    uimenu(HELPMENU,'Label','About Loops','Separator','on','Callback',['msgbox({'''',' ...
        ''' Iterative Loop Counting Algorithm Gui '','' Release 4 - February 2007 '','''',' ...
        ''' by Joseph Kirk '','' jdkirk630@gmail.com''},''About Loops'')']);
    uicontrol('Parent',HFIG,'Position',[30 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[1.0 0.65 0.65],'Tag','getnet','String','Get Net', ...
        'FontWeight','bold','Callback',[mfilename,'(''GETNET'')']);
    REDUCENET = uicontrol('Parent',gcf,'Position',[130 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[0.9 0.9 0.9],'Tag','reducenet','String','Reduce Net', ...
        'Enable','off','FontWeight','bold','Callback',[mfilename,'(''REDUCENET'')']);
    COUNTLOOPS = uicontrol('Parent',gcf,'Position',[230 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[0.9 0.9 0.9],'Tag','countloops','String','Count Loops', ...
        'Enable','off','FontWeight','bold','Callback',[mfilename,'(''COUNTLOOPS'')']);
    SAVENET = uicontrol('Parent',gcf,'Position',[330 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[0.9 0.9 0.9],'Tag','savenet','String','Save Net', ...
        'Enable','off','FontWeight','bold','Callback',[mfilename,'(''SAVENET'')']);
    SAVELOOPS = uicontrol('Parent',gcf,'Position',[430 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[0.9 0.9 0.9],'Tag','saveloops','String','Save Loops', ...
        'Enable','off','FontWeight','bold','Callback',[mfilename,'(''SAVELOOPS'')']);
    CLEAR = uicontrol('Parent',HFIG,'Position',[530 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[0.9 0.9 0.9],'Tag','clear','String','Clear', ...
        'Enable','off','FontWeight','bold','Callback',[mfilename,'(''CLEAR'')']);
    uicontrol('Parent',HFIG,'Position',[630 25 90 30],'Style','pushbutton', ...
        'BackgroundColor',[0.75 0.6 1],'Tag','done','String','Close', ...
        'FontWeight','bold','Callback',[mfilename,'(''CLOSE'')']);
    NETPROPS = uicontrol('Parent',gcf,'Position',[30 65 300 25],'Style','text', ...
        'BackgroundColor',[0.8 0.8 0.8],'Tag','netprops','String',' ','FontSize',12);
    NUMLOOPS = uicontrol('Parent',gcf,'Position',[25 415 700 30],'Style','text', ...
        'BackgroundColor',[0.8 0.8 0.8],'Tag','numloops','String',' ','FontSize',14);

else   %%% GUI callback routines %%%
    switch cmd
        case 'GETNET'
            Button = questdlg('Pick a network type:','Network Type', ...
            'Edge List File','Random Network','Edge List File');
            if ~isempty(Button)
                switch Button
                     case 'Edge List File'
                        % READ NET FROM FILE (PROMPT WILL APPEAR)
                        edge_list = read_edge_list(); % prompt user to select an edge list file
                        if ~isempty(edge_list)
                            USNET = edge_list2net(edge_list); % format the edgelist for loop counting
                            NET = sort_net(USNET);
                        else
                            return
                        end
                   case 'Random Network'
                        % GENERATE RANDOM NET (PROMPT WILL APPEAR)
                        prompt = {' Enter number of NODES for the random network: ', ...
                            ' Enter number of EDGES for the random network: '};
                        name = 'Random Network Setup';
                        answer = inputdlg(prompt,name,1,{'15','25'});
                        if ~isempty(answer)
                            num_nodes = str2double(answer{1});
                            num_edges = str2double(answer{2});
                            USNET = gen_rand_net(num_nodes,num_edges);
                            NET = sort_net(USNET);
                        else
                            return
                        end
                end
            else
                return
            end
            num_nodes = length(NET); num_edges = calc_num_edges(NET);
            disp(['  Net:  nodes = ' num2str(num_nodes) ' edges = ' num2str(num_edges)]);
            axes(AXN); plot_net(NET); title('Network');
            set(NETPROPS,'String',['Net has ' num2str(num_nodes) ' nodes and ' ...
                num2str(num_edges) ' edges']);
            set(REDUCENET,'BackgroundColor',[1.0 0.75 0.6],'Enable','on');
            set(COUNTLOOPS,'BackgroundColor',[1 1 0.75],'Enable','on');
            set(SAVENET,'BackgroundColor',[0.75 1 0.75],'Enable','on');
            set(CLEAR,'BackgroundColor',[0.6 0.75 1],'Enable','on');
            set(SAVELOOPS,'BackgroundColor',[0.9 0.9 0.9],'Enable','off');
            set(NUMLOOPS,'String',' ');
            axes(AXH); plot(NaN,NaN); set(AXH,'Visible','off');
        case 'REDUCENET'
            NET = reduce_net(NET);
            num_nodes = length(NET); num_edges = calc_num_edges(NET);
            disp(['   Reduced net:  nodes = ' num2str(num_nodes) ' edges = ' num2str(num_edges)]);
            axes(AXN); plot_net(NET); title('Reduced Network');
            set(NETPROPS,'String',['Net has ' num2str(num_nodes) ' nodes and ' ...
                num2str(num_edges) ' edges']);
        case 'COUNTLOOPS'
            prompt = {' Approximately how many loops do you expect? (Needed for waitbar progress) '};
            name = 'Loop Count (Estimate)';
            answer = inputdlg(prompt,name,1,{'1000'});
            if isempty(answer)
                return
            else
                num_est_loops = cell2mat(answer);
            end
            n = get_starting_node(NET); % give the path a nearly optimal starting node
            path = NET(n).node; % initialize the path
            current_edge = NET(n).edges(1); % initialize the first edge
            LOOPLIST = []; % initialize the loop list
            iterations = 0; % initialize the number of algorithm steps
            wbh = waitbar(0,['Searching Tree for Loops ... ' num2str(0) ' found']);
            while (length(path)>1 || ~isempty(current_edge))
                [NET,path,current_edge,LOOPLIST] = iterate_tree(NET,path,current_edge,LOOPLIST);
                iterations = iterations+1;
                waitbar(length(LOOPLIST)/str2double(num_est_loops),wbh, ...
                    ['Searching Tree for Loops ... ' num2str(length(LOOPLIST)) ' found']);
            end
            close(wbh);
            num_loops = length(LOOPLIST);
            disp(['    It took ' num2str(iterations) ' steps to complete the ILCA']);
            disp(['     There are ' num2str(num_loops) ' loops in the net']);
            axes(AXH);
            LOOPDIST = plot_loop_dist(NET,LOOPLIST);
            set(NUMLOOPS,'String',[num2str(num_loops) ' Loops Found ... in ' ...
                num2str(iterations) ' ILCA Iterations']);
            set(SAVELOOPS,'BackgroundColor',[0.75 1 0.75],'Enable','on');
        case 'SAVENET'
            prompt = {'Enter the name of the file (no file extension):'};
            name = 'Save Net to TXT File';
            answer = inputdlg(prompt,name,[1 50],{'net'});
            filename = cell2mat(answer);
            if ~isempty(filename)
                net2file(NET,[filename '.txt']);
            end
        case 'SAVELOOPS'
            prompt = {'Enter the name of the file (no file extension):'};
            name = 'Save Loops to TXT or MAT File';
            answer = inputdlg(prompt,name,[1 50],{'looplist'});
            filename = cell2mat(answer);
            if ~isempty(filename)
                Button = questdlg('Choose File Type:','File Type', ...
                'TXT File','MAT File','TXT File');
                if ~isempty(Button)
                    switch Button
                        case 'TXT File'
                            loops2file(LOOPLIST,[filename '.txt']);
                        case 'MAT File'
                            eval(sprintf([filename ' = LOOPLIST;']));
                            eval(sprintf('save %s %s',filename,filename));
                    end
                end
            end
        case 'CLEAR'
            NET = []; LOOPLIST = [];
            set(NUMLOOPS,'String',' ');
            set(NETPROPS,'String',' ');
            set(REDUCENET,'BackgroundColor',[0.9 0.9 0.9],'Enable','off');
            set(COUNTLOOPS,'BackgroundColor',[0.9 0.9 0.9],'Enable','off');
            set(SAVENET,'BackgroundColor',[0.9 0.9 0.9],'Enable','off');
            set(SAVELOOPS,'BackgroundColor',[0.9 0.9 0.9],'Enable','off');
            set(CLEAR,'BackgroundColor',[0.9 0.9 0.9],'Enable','off');
            axes(AXN);plot(NaN,NaN);set(AXN,'Visible','off');
            axes(AXH);plot(NaN,NaN);set(AXH,'Visible','off');
        case 'CLOSE'
            close;
        otherwise
            error('LOOPS_GUI: Invalid command!');
    end
end
return

%--------------------------------------------------------------------------
%------- SUBFUNCTIONS -----------------------------------------------------
%--------------------------------------------------------------------------
function net = gen_rand_net(num_nodes,num_edges)
% PURPOSE:  Generate an *undirected* random network of a given number of nodes/edges
% USAGE:    >> net = gen_rand_net(num_nodes,num_edges);
% INPUTS:   num_nodes  - number of nodes in the random network
%           num_edges  - number of edges in the random network
% OUTPUTS:  net  - network structure containing two fields: 'node' and 'edges'
%                     'node' is the ID of the current node
%                     'edges' is a vector that lists all the nodes connected to 'node'
% NOTES:    Does not guarantee a *connected* network (especially if 'num_edges' is small)
%           Allows nodes that are only 1-connected

num_nodes = abs(round(real(num_nodes)));
num_edges = abs(round(real(num_edges)));

if (num_nodes < 3)
    num_nodes = 3;
end
if (num_edges > num_nodes*(num_nodes-1)/2)
    num_edges = num_nodes*(num_nodes-1)/2;
elseif (num_edges < num_nodes)
    num_edges = num_nodes;
end
x = rand(1,num_nodes); y = rand(1,num_nodes);
tri = delaunay(x,y);
[nr,nc] = size(tri);
edge_list = zeros(3*nr,nc-1);
for e = 1:nr
    edge_list(3*e-2,:) = tri(e,[1 2]);
    edge_list(3*e-1,:) = tri(e,[1 3]);
    edge_list(3*e,:) = tri(e,[2 3]);
end
net = edge_list2net(edge_list);
n = length(net);
m = calc_num_edges(net);
iterations = 1;
while or(m ~= num_edges,n ~= num_nodes)
    if n == num_nodes
        if m < num_edges % add an edge
            edge_list = [edge_list; ceil(num_nodes*rand(1,2))];
        else % subtract an edge
            e = length(edge_list); r = ceil(e*rand);
            edge_list = edge_list([(1:r-1) (r+1:e)],:);
        end
    else
        if n < num_nodes % add a node
            for k = 1:n+1
                if isempty(find(edge_list == k,1))
                    edge_list = [edge_list; k ceil(n*rand)];
                    break
                end
            end
        else % subtract a node
            v = edge_list(ceil(length(edge_list)*rand),ceil(2*rand));
            edge_list = edge_list(edge_list(:,1)~=v,:);
            edge_list = edge_list(edge_list(:,2)~=v,:);
        end
    end
    net = edge_list2net(edge_list);
    n = length(net);
    m = calc_num_edges(net);
    iterations = iterations + 1;
end
disp([' The random net was generated after ' num2str(iterations) ' modifications']);

%--------------------------------------------------------------------------
function edge_list = read_edge_list()
% PURPOSE:  Read an edge list from file
% USAGE:    >> edge_list = read_edge_list();
% INPUTS:   filename  - (optional) string specifying name of the input file
% OUTPUTS:  edge_list  - Nx2 matrix of nodes where each row represents an edge connection

edge_list = [];
[fname,path] = uigetfile('*.txt','Load Edge List File ...');
if fname
    filename = [path fname];
else
    return
end
fid = fopen(filename,'rt');
edge_list = fscanf(fid,'%10i',[2,inf]);
fclose(fid);
edge_list = edge_list';

%--------------------------------------------------------------------------
function net = edge_list2net(edge_list)
% PURPOSE:  Transform an edge list into a network structure
% USAGE:    >> net = edge_list2net(edge_list);
% INPUTS:   edge_list  - Nx2 matrix of nodes where each row represents an edge connection
% OUTPUTS:  net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'

net = [];
if isempty(edge_list)
    return
end
edge_list = abs(round(real(edge_list)));
ne = size(edge_list);
net(1).node = edge_list(1,1); net(1).edges = edge_list(1,2);
net(2).node = edge_list(1,2); net(2).edges = edge_list(1,1);
for idx = 2:ne(1)
    node_exists = 0;
    % if the node is already part of the net, update the list of edges
    for k = 1:length(net)
        if (edge_list(idx,1) == net(k).node)
            % do not update the edge list if the edge already exists
            if isempty(find([net(k).edges net(k).node] == edge_list(idx,2),1))
                net(k).edges = [net(k).edges edge_list(idx,2)];
            end
            node_exists = 1;
            break
        end
    end
    % if the node is new, add it to the end of the net along with the edge
    if ~node_exists
        net(k+1).node = edge_list(idx,1);
        net(k+1).edges = edge_list(idx,2);
    end
    node_exists = 0;
    % if the node is already part of the net, update the list of edges
    for k = 1:length(net)
        if (edge_list(idx,2) == net(k).node)
            % do not update the edge list if the edge already exists
            if isempty(find([net(k).edges net(k).node] == edge_list(idx,1),1))
                net(k).edges = [net(k).edges edge_list(idx,1)];
            end
            node_exists = 1;
            break
        end
    end
    % if the node is new, add it to the end of the net along with the edge
    if ~node_exists
        net(k+1).node = edge_list(idx,2);
        net(k+1).edges = edge_list(idx,1);
    end
end

%--------------------------------------------------------------------------
function net = sort_net(net)
% PURPOSE:  Puts all of the nodes in order from least to greatest
% USAGE:    >> net = sort_net(net);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
% OUTPUTS:  net  - sorted network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'

tmp = [];
nodes_list = zeros(1, length(net));
for k = 1:length(net)
    nodes_list(k) = net(k).node;
end
[sorted, order] = sort(nodes_list);
for k = 1:length(net)
    tmp(k).node = net(order(k)).node;
    tmp(k).edges = sort(net(order(k)).edges);
end
net = tmp;

%--------------------------------------------------------------------------
function num_edges = calc_num_edges(net)
% PURPOSE:  Calculates the number of edges in an undirected network
% USAGE:    >> num_edges = calc_num_edges(net);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
% OUTPUTS:  num_edges  - number of edges in the network

num_edges = 0;
for k = 1:length(net)
    num_edges = num_edges + length(net(k).edges);
end
num_edges = num_edges/2;

%--------------------------------------------------------------------------
function plot_net(net)
% PURPOSE:  Make a plot of the network structure
% USAGE:    >> plot_net(net);
% INPUTS:   net	- network structure containing two fields: 'node' and 'edges'
%                 'node' is the ID of the current node
%                 'edges' is a vector that lists all the nodes connected to 'node'

n = length(net);
nodeids = zeros(1,n);
for ii = 1:n
    nodeids(ii) = net(ii).node;
end
% place the nodes with equal spacing around a circle
wn = exp(j*2*pi/n); z = wn.^(0:n-1);
x = real(z); y = imag(z);
hold off
for ii = 1:n
    k = find(nodeids == net(ii).node);
    % plot a line for each edge connection
    for jj = 1:length(net(ii).edges)
        kk = find(nodeids == net(ii).edges(jj));
        plot([x(k) x(kk)],[y(k) y(kk)],'k-')
        hold on
    end
    % add the node ID for the current node to the graph
    if (x(k) >= 0 && y(k) >= 0)
        text(x(k),y(k),num2str(nodeids(k)),'VerticalAlignment','bottom','HorizontalAlignment','left');
    elseif (x(k) < 0 && y(k) >= 0)
        text(x(k),y(k),num2str(nodeids(k)),'VerticalAlignment','bottom','HorizontalAlignment','right');
    elseif (x(k) < 0 && y(k) < 0)
        text(x(k),y(k),num2str(nodeids(k)),'VerticalAlignment','top','HorizontalAlignment','right');
    else
        text(x(k),y(k),num2str(nodeids(ii)),'VerticalAlignment','top','HorizontalAlignment','left');
    end
end
plot(x,y,'r.')
hold off
set(gca,'XTick',NaN,'YTick',NaN)
axis([-1.2 1.2 -1.2 1.2])

%--------------------------------------------------------------------------
function net = reduce_net(net)
% PURPOSE:  Remove all 'singly connected' nodes and corresponding edges
% USAGE:    >> rnet = reduce_net(net);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
% OUTPUTS:  net  - reduced network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'

finished = 0;
while (~finished)
    finished = 1;
    for k = 1:length(net)
        % delete the node and edge connection
        if (length(net(k).edges) == 1)
            finished = 0;
            node = net(k).node;
            edge = net(k).edges;
            net(k) = [];
            % also delete the 'opposite direction edge'
            for kk = 1:length(net)
                if (net(kk).node == edge)
                    if (length(net(kk).edges) == 1)
                        net(kk) = [];
                    else
                        idx = find(net(kk).edges == node);
                        if ~isempty(idx)
                            net(kk).edges(idx) = [];
                        end
                    end
                    break
                end
            end
            break
        end
    end
end

%--------------------------------------------------------------------------
function n = get_starting_node(net)
% PURPOSE:  Pick the (nearly) optimal starting node
% USAGE:    >> n = get_starting_node(net);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
% OUTPUTS:  n  - index to the optimal network starting node

n = 1;
for k = 2:length(net)
    if (length(net(k).edges) > length(net(n).edges))
        n = k;
    end
end

%--------------------------------------------------------------------------
function [net,path,current_edge,loop_list] = iterate_tree(net,path,current_edge,loop_list)
% PURPOSE:  Execute the current iterative step in the loop counting algorithm
% USAGE:    >> [net,path,current_edge,loop_list] = iterate_tree(net,path,current_edge,loop_list);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
%           path  - an ordered vector of node values that are connected
%           current_edge  - the node ID of the current edge
%           loop_list  - a structure with one field named 'loop' containing a list of all loops found
% OUTPUTS:  net  - same as net input
%           path  - same as path input,potentially modified
%           current_edge  - the node ID of the next edge to be considered
%           loop_list  - same as loop_list input,potentially ammended

path_size = length(path);
% DONE - finished searching tree
if (path_size == 1 && isempty(current_edge))
    return
% CURRENT EDGE LIST FINISHED - go up tree
elseif (isempty(current_edge))
    current_edge = get_next_edge(net,path(path_size-1),path(path_size));
    path(path_size) = [];
% CURRENT EDGE IS THE SAME AS PREVIOUS VERTEX - move to next edge
elseif (length(path) > 1 && path(path_size-1) == current_edge)
    current_edge = get_next_edge(net,path(path_size),current_edge);
% LOOP FOUND!
elseif (check_path4loop(path,current_edge))
    loop = loop2std_form(path,current_edge);
    if ~compare_loop(loop,loop_list)
        loop_list = append_loop_list(loop_list,loop);
    end
    current_edge = get_next_edge(net,path(path_size),current_edge);
% NO LOOP FOUND - keep going down tree
else
    path = [path current_edge];
    current_edge = get_next_edge(net,path(path_size+1),[]);
end

%--------------------------------------------------------------------------
function loop_list = append_loop_list(loop_list,loop)
% PURPOSE:  Adds a loop to the end of a loop_list structure
% USAGE:    >> loop_list = append_loop_list(loop_list,loop);
% INPUTS:   loop_list  - a structure with one field named 'loop' containing
%                        a list of all previously found loops
%           loop  - 1xM vector containing a list of nodes that make a loop
% OUTPUTS:  loop_list  - the modified loop_list structure

if isempty(loop_list)
    loop_list.loop = loop;
else
    num_loops = length(loop_list);
    loop_list(num_loops+1).loop = loop;
end

%--------------------------------------------------------------------------
function status = check_path4loop(path,current_edge)
% PURPOSE:  Check to see if the current edge is in the path
% USAGE:    >> status = check_path4loop(path,current_edge);
% INPUTS:   path  - an ordered vector of node values that are connected
%           current_edge  - a node connected to the last node in path
% OUTPUTS:  status  - 1 if a loop has been found,0 otherwise

status = 0;
if find(path == current_edge,1)
    status = 1;
end

%--------------------------------------------------------------------------
function status = compare_loop(loop,loop_list)
% PURPOSE:  Check to see if the loop already exists in the loop_list
% USAGE:    >> status = compare_loop(loop,loop_list);
% INPUTS:   loop  - 1xM vector containing nodes that are connected in a loop
%           loop_list  - a structure with one field named 'loop' containing a list
%                        of all previously found loops
% OUTPUTS:  status  - equals 1 if 'loop' already exists,0 otherwise

status = 0;
if isempty(loop_list)
    return
end
for k = 1:length(loop_list)
    m = length(loop_list(k).loop);
    n = length(loop);
    % if the two loops have the same length,check if they are identical
    if (m == n)
        status = 1;
        for kk = 1:n
            if (loop_list(k).loop(kk) ~= loop(kk))
                status = 0;  % loops are different,move on to next
                break
            end
        end
        % loops are identical
        if status
            return
        end
    end
end

%--------------------------------------------------------------------------
function next_edge = get_next_edge(net,current_node,current_edge)
% PURPOSE:  Find the next edge of the current node in the network structure
% USAGE:    >> next_edge = get_next_edge(net,current_node,current_edge);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
%           current_node  - the ID of the current node in the path
%           current_edge  - the node ID of the current edge
% OUTPUTS:  next_edge  - the node ID of the next edge in the edges list for the current node

next_edge = [];
for k = 1:length(net)
    if (current_node == net(k).node)
        if isempty(current_edge)    % start with the first edge of the node
            next_edge = net(k).edges(1);
        else    % get the next edge in the list,if there is one
            kk = find(net(k).edges == current_edge);
            if kk < length(net(k).edges)
                next_edge = net(k).edges(kk+1);
            end
        end
        return
    end
end

%--------------------------------------------------------------------------
function loop = loop2std_form(path,current_edge)
% PURPOSE:  Take a loop found in the path and return the loop vector in *standard form*
% USAGE:    >> loop = loop2std_form(path,current_edge);
% INPUTS:   path  - an ordered vector of node values that are connected
%           current_edge  - the node ID of the current edge
% OUTPUTS:  loop  - 1xM vector of standard form loop,where M is the length of the loop
% NOTES:    Standard form is defined as having the smallest node ID at the front
%           of the list,and the smaller of the two neighbors listed second

ii = find(path == current_edge);
% get the loop from the path
loopy = path(ii:end);
n = length(loopy);
jj = find(loopy == min(loopy));
% order the loop with the smallest value first
loop = loopy([(jj:n) (1:jj-1)]);
% order the rest of the loop with the smaller of the two neighbors second
if loop(2) > loop(n)
    loop = [loop(1) fliplr(loop(2:n))];
end

%--------------------------------------------------------------------------
function nh = plot_loop_dist(net,loop_list)
% PURPOSE:  Plot the distribution of loops with length 'h'
% USAGE:    >> plot_loop_dist(net,loop_list);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
%           loop_list  - a structure with one field named 'loop' containing
%                        a list of all loops found

num_nodes = length(net);
num_loops = length(loop_list);
nh = zeros(1,num_nodes-2);
for k = 1:num_loops
    h = length(loop_list(k).loop);
    nh(1,h-2) = nh(1,h-2)+1;
end
% plot the number of loops of each length (h)
hold off
plot((3:num_nodes),nh(1,:),'b.-');
title(' Number of loops of length "h"');
xlabel(' h ');
ylabel(' N_h ');
set(gca,'XTick',(3:max(1,floor(num_nodes/10)):num_nodes))
set(gca,'YTick',(0:max(1,floor(max(nh)/10)):max(nh)))
axis([2 num_nodes+1 0 max(nh)*1.1]);
hold off

%--------------------------------------------------------------------------
function net2file(net,fname)
% PURPOSE:  Write the net to a file
% USAGE:    >> net2file(net,fname);
%               or
%           >> net2file(net);
% INPUTS:   net  - network structure containing two fields: 'node' and 'edges'
%                  'node' is the ID of the current node
%                  'edges' is a vector that lists all the nodes connected to 'node'
%           fname  - (optional) name of the file to write loops to
%                     must be a string with (recommended) .txt file extension

fid = fopen(fname,'w');
% print one edge per line with a tab separating each node
for k = 1:length(net)
    num_edges = length(net(k).edges);
    for kk = 1:num_edges
        if net(k).node < net(k).edges(kk)
            fprintf(fid,[num2str(net(k).node) '\t' num2str(net(k).edges(kk)) '\n']);
        end
    end
end
fclose(fid);

%--------------------------------------------------------------------------
function loops2file(loop_list,filename)
% PURPOSE:  Write the loop_list to a file
% USAGE:    >> loops2file(loop_list,filename);
%               or
%           >> loops2file(loop_list);
% INPUTS:   loop_list  - a structure with one field named 'loop' containing
%                        a list of all previously found loops
%           filename  - (optional) name of the file to write loops to
%                     must be a string with (recommended) .txt file extension

fid = fopen(filename,'w');
wb = waitbar(0,' Writing Loops to File ... ');
num_loops = length(loop_list);
% print one loop per line with a space separating each node
for k = 1:num_loops
    waitbar(k/num_loops,wb);
    loop_size = length(loop_list(k).loop);
    string = num2str(loop_list(k).loop(1));
    for kk = 2:loop_size
        string = [string ' ' num2str(loop_list(k).loop(kk))];
    end
    fprintf(fid,[string '\n']);
end
fclose(fid);
close(wb);

Contact us