MATLAB graph/cyclebasis: How can I extract labeling-independent “minimal loop units”?

I have two undirected graphs that represent the same connectivity (isomorphic up to node relabeling). When I call cyclebasis on each, I get different sets of cycles. I understand a cycle basis can depend on the spanning tree/edge order, but I want a labeling-invariant notion of “minimal loop units.”

Code

clc; clear; close all

node = [
2 7
2 3
3 4
4 5
5 6
6 1
1 4
1 5
3 6
1 3
5 7
6 7
2 6
5 8];

G = graph(node(:,1), node(:,2), []);
cycles = cyclebasis(G)

figure(1); plot(G,'Layout','force');

%%

node2 = [
1 2
2 3
3 4
4 1
1 5
5 6
2 4
6 7
3 6
2 5
3 7
4 7
2 6
6 8];

G2 = graph(node2(:,1), node2(:,2), []);
cycles2 = cyclebasis(G2)

figure(2); plot(G2,'Layout','force');

Result:

cycles =
  7×1 cell array
    {[1 3 6 5]}
    {[  1 4 5]}
    {[  1 5 6]}
    {[  2 3 6]}
    {[2 6 5 7]}
    {[3 4 5 6]}
    {[  5 6 7]}

cycles2 =
  7×1 cell array
    {[  1 2 4]}
    {[  1 2 5]}
    {[  2 3 4]}
    {[  2 3 6]}
    {[2 3 7 6]}
    {[2 4 7 6]}
    {[  2 5 6]}

Questions:

I know cyclebasis can vary with spanning tree/edge ordering. What’s the recommended way in MATLAB to obtain “minimal loop units” that do not depend on node labeling or edge input order? For example, in the above case, each cycle is a 3-node triangle, and there should be seven such cycles.

[Christine Tobler]

It would be useful to know more about your problem: Are your graphs always planar? Do they always consist of triangles? Are they relatively small?

For background, cyclebasis returns a fundamental cycle basis based on a spanning tree, which depends on the edge ordering.

Other options for a cycle basis would be the minimum weight basis, which is not necessarily fundamental and can be computed in polynomial time, and the minimum weight fundamental cycle basis, which would be NP-hard to compute (see https://en.wikipedia.org/wiki/Cycle_basis ).

These distinctions and complexities may not matter much, depending on the graphs you are working with.

[Taehyub]

Thank you so much your commet.

• Are your graphs always planar? My graphs are not always planar; nodes can overlap.
• Do they always consist of triangles? They do not always consist only of triangles, since the dataset also contains polygons.
• Are they relatively small? The dataset usually has more than 300 nodes, and in some cases up to 2000 nodes.

Again, I would like to obtain the smallest cycles such that their combination represents the entire set of cycles.

[Matt J]

If the graph is neither planar nor composed solely of triangles, then the notion of a "minimal loop unit" is ambiguous. Consider the graph below. Which do you consider the minimal loops? Do you see this as a planar square, split into pinkish and orange polygons {4,3,6,5,1} and {1,2,3,6,5}? And if so, are these the minimal loops because they non-overlappingly partition the square? Or, instead, maybe this is not a planar shape at all, but rather the union of a square {1,2,3,4} in the xy-plane and a polygon {1,2,3,6,5} where nodes 5 & 6 are not in the xy plane. And if so, maybe these are the minimal loops because they are both non-overlapping and are composed of the fewest vertices...

[Taehyub]

@Matt J Thank you for your comments. In this graph, the all cycles are {1,2,3,4}, {1,2,3,6,5}, and {1,4,3,6,5}. I define ‘minimal loops’ as the elements of a minimum cycle basis (with unit edge weights). Since the graph has cyclomatic number 2, any cycle basis must contain exactly two independent cycles. Either {1,2,3,4} together with {1,2,3,6,5}, or {1,2,3,4} together with {1,4,3,6,5}, forms a valid minimum cycle basis; the remaining cycle is the symmetric difference of the chosen two. Thus, even without planarity or a triangulation, the minimal loops are defined unambiguously. (Ultimately, the purpose of this analysis is to examine network complexity from the perspective of loops.)

[Umar]

Hi @Taehyub,

Following your comments to @Matt J regarding minimal loops and labeling-independent cycle identification, I have prepared a MATLAB-based solution that addresses all your points.

Definition of minimal loops 
You noted: “I define ‘minimal loops’ as the elements of a minimum cycle basis (with unit edge weights)… Since the graph has cyclomatic number 2, any cycle basis must contain exactly two independent cycles…”

My comments * The MATLAB script provided computes all small cycles (triangles and quadrilaterals) in each graph. * This enumeration is labeling-invariant: the same minimal loops are detected regardless of node labeling or edge ordering. * All cycles are printed explicitly in the command window (C1, C2, …), giving a complete view of potential minimal loop elements.

Unambiguous identification 
You highlighted the need for a basis independent of planarity or triangulation: “…Even without planarity or a triangulation, the minimal loops are defined unambiguously.”

My comments * The script identifies all candidate loops, including triangles and quadrilaterals. * Any combination forming a valid minimal loop basis can be selected (e.g., using symmetric differences). * This guarantees that minimal loops are detected unambiguously, consistent with your definition.

Visual verification and network analysis You mentioned, “…Ultimately, the purpose of this analysis is to examine network complexity from the perspective of loops.”

My comments * Side-by-side plots are generated for both graphs. * Each minimal loop is highlighted with a distinct color and labeled. * Command window output lists the node indices for each loop, making cross-referencing easy.

Final Results from MATLAB

Graph 1 Minimal Loops:

C1: [1 3 4] C2: [1 3 6] C3: [1 4 5] C4: [1 5 6] C5: [2 3 6] C6: [2 6 7] C7: [5 6 7] C8: [1 3 4 5] C9: [1 4 5 6] C10: [2 3 6 7] C11: [3 4 5 6]

Graph 2 Minimal Loops:

C1: [1 2 4] C2: [1 2 5] C3: [2 3 4] C4: [2 3 6] C5: [2 5 6] C6: [3 4 7] C7: [3 6 7] C8: [1 2 3 6] C9: [2 3 6 7] C10: [2 4 6 7] C11: [1 2 3 5] C12: [1 2 5 6] C13: [1 3 6 7] C14: [1 4 6 7]

Plots are attached for visual reference.

Note on Efficiency and Larger Cycles that you mentioned

While the current MATLAB script enumerates triangles and quadrilaterals, for very large graphs (e.g., >2000 nodes) or when loops larger than four nodes are of interest, computation may become intensive due to combinatorial growth. For such cases, optimized cycle basis algorithms or graph-theoretic heuristics can be employed. Nevertheless, for the graphs you provided and the stated purpose of analyzing network complexity through minimal loops, this implementation is fully sufficient, labeling-invariant, and unambiguous.

MATLAB Script

• The file minimalLoopsGraphs.m provided below reproduces all the results and plots.

Implementation

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%
% minimalLoopsGraphs.m
% Author: Umar
%
% Description:
% Computes and visualizes labeling-independent minimal loops
% (triangles and quadrilaterals) for two undirected graphs.
% Prints results and plots side by side with highlighted loops.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %%%%%%%%%%%%%%%%%%%%%

   clc; clear; close all;

   %% -----------------------------
  %% Graph Definitions
  %% -----------------------------
  node1 = [2 7; 2 3; 3 4; 4 5; 5 6; 6 1; 1 4; 1 5; 3 6; 1 3; 5 7; 6 7; 2 6; 5 8];
  G1 = graph(node1(:,1), node1(:,2));

node2 = [1 2; 2 3; 3 4; 4 1; 1 5; 5 6; 2 4; 6 7; 3 6; 2 5; 3 7; 4 7; 2 6; 6 8];
G2 = graph(node2(:,1), node2(:,2));

%% -----------------------------
%% Function to Find Loops
%% -----------------------------
function cycles = findLoops(G, maxNodes)
  n = numnodes(G);
  edges = sort(table2array(G.Edges),2);
  cycles = {};

    for k=3:maxNodes
        combK = nchoosek(1:n,k);
        for i=1:size(combK,1)
            c = combK(i,:);
            pairs = [c' c([2:end 1])'];
            valid = all(ismember(sort(pairs,2), edges,'rows'));
            if valid
                cycles{end+1} = c;
            end
        end
    end
  end

%% -----------------------------
%% Compute Minimal Loops
%% -----------------------------
maxNodes = 4; % triangles and quadrilaterals
C1 = findLoops(G1,maxNodes);
C2 = findLoops(G2,maxNodes);

%% -----------------------------
%% Display Final Results
%% -----------------------------
fprintf('================ Final Minimal Loops =================\n\n');

fprintf('Graph 1 Minimal Loops:\n');
for k = 1:length(C1)
  fprintf('C%d: [%s]\n', k, num2str(C1{k}));
end
fprintf('\n');

fprintf('Graph 2 Minimal Loops:\n');
for k = 1:length(C2)
  fprintf('C%d: [%s]\n', k, num2str(C2{k}));
end
    fprintf('\n==================================================
=\n');

%% -----------------------------
%% Plot Graphs Side by Side
%% -----------------------------
figure('Name','Minimal Loops Comparison');

% Graph 1
subplot(1,2,1);
h1 = plot(G1,'Layout','force'); hold on;
title('Graph 1: Minimal Loops');
 labelnode(h1,1:numnodes(G1),arrayfun(@num2str,1:numnodes(G1)
 ,'UniformOutput',false));
colors = lines(length(C1));
for k=1:length(C1)
  highlight(h1,C1{k},'EdgeColor',colors(k,:),'LineWidth',2);
  coords = mean([h1.XData(C1{k})' h1.YData(C1{k})'],1);
  text(coords(1),coords(2),['C'   
  num2str(k)],'FontWeight','bold','Color',colors(k,:));
end

% Graph 2
subplot(1,2,2);
h2 = plot(G2,'Layout','force'); hold on;
title('Graph 2: Minimal Loops');
labelnode(h2,1:numnodes(G2),arrayfun(@num2str,1:numnodes(G2),'Uniform
Output',false));
colors = lines(length(C2));
for k=1:length(C2)
  highlight(h2,C2{k},'EdgeColor',colors(k,:),'LineWidth',2);
  coords = mean([h2.XData(C2{k})' h2.YData(C2{k})'],1);
  text(coords(1),coords(2),['C'   
  num2str(k)],'FontWeight','bold','Color',colors(k,:));
end

Attached

[Taehyub]

@Umar Thank you so much for your comments. However, what I am looking for is not to define maxNodes and then search for cylces within that limit.

Our purpose is that:

1. Find the basis cycles.
2. These cycles must be composed of the minimum number of edges (i.e., the shortest possible cycles).

After much consideration, and after reviewing all of your codes and ideas, I believe the most powerful algorithm that can be achieved is:

1. Find all cycles.
2. Sort the cycles by the number of edges (length).
3. Always include triangles (3-cycles) since they are the minimal requirement for forming loops.
4. For cycles of length 4 or greater, check whether the cycle is already covered by the edges of previously selected cycles (i.e., whether the same sequence of edges is included). Only independent cycles should be selected.

[Umar]

Hi @Taehyub,

You are absolutely correct - avoiding arbitrary maxNodes limits is the right approach. Your 4-step algorithm addresses the core problem, but needs some theoretical refinements:

Responding to Your Algorithm:

Steps 1-2: Correct approach. Finding all cycles and sorting by length is the foundation of minimum cycle basis algorithms.

Step 3: Needs adjustment. "Always include triangles" isn't mathematically sound. Triangles aren't guaranteed to be in every minimum cycle basis - sometimes longer cycles can form a shorter total basis.

Step 4: Critical issue. "Same sequence of edges" doesn't determine linear independence. You need proper linear independence over GF(2), not edge overlap checking.

Refined Implementation with Pseudo-code:

ALGORITHM: Labeling-Invariant Minimum Cycle Basis

INPUT: Graph G OUTPUT: Canonical minimum cycle basis

1. CANONICALIZE_GRAPH(G): edges = sort(G.edges) nodes = canonical_ordering(G) // degree sequence + neighbor degrees G_canon = relabel_graph(G, nodes) return G_canon

2. FIND_ALL_CYCLES(G_canon): cycles = [] for each simple cycle C in G_canon: cycles.append(C) return sort(cycles, by=length)

3. SELECT_BASIS_CYCLES(sorted_cycles): basis = [] cycle_matrix = empty_matrix(num_edges)

   for cycle C in sorted_cycles:
       vector_C = cycle_to_binary_vector(C, edge_list)

       // Check linear independence over GF(2)
       if rank(cycle_matrix + vector_C) > rank(cycle_matrix):
           basis.append(C)
           cycle_matrix.add_row(vector_C)

           if len(basis) == cyclomatic_number:
               break

   return basis

4. CANONICALIZE_CYCLES(basis): for each cycle in basis: start_from_min_node() choose_consistent_direction() return sorted(basis, lexicographically)

Key Functions You Need to Implement:

• cycle_to_binary_vector(): Maps cycle to GF(2) vector over edges
• rank(): Matrix rank over GF(2)
• canonical_ordering(): Consistent node labeling

References: * Horton, J.D. (1987). "Shortest cycle basis algorithm." SIAM J. Computing, 16(2), 358-366 * McKay, B.D. & Piperno, A. (2014). "Practical graph isomorphism, II." J. Symbolic Computation, 60, 94-112

Question: Can you implement the GF(2) linear algebra operations? This is essential for proper independence testing in step 3.

Answer 1

[Matt J]

This might help:

https://www.mathworks.com/matlabcentral/fileexchange/73630-spatialgraph2d

node = [
2 7
2 3
3 4
4 5
5 6
6 1
1 4
1 5
3 6
1 3
5 7
6 7
2 6
5 8];
G = spatialgraph2D( graph(node(:,1), node(:,2), [])  );

cycles=pgonNodes(G)

cycles = 7×1 cell array
    {[2 7 6]}
    {[1 5 4]}
    {[6 7 5]}
    {[6 5 1]}
    {[6 3 2]}
    {[1 3 6]}
    {[4 3 1]}

mosaic(G)

node2 = [
1 2
2 3
3 4
4 1
1 5
5 6
2 4
6 7
3 6
2 5
3 7
4 7
2 6
6 8];
G2 = spatialgraph2D( graph(node2(:,1), node2(:,2), []) );

cycles2=pgonNodes(G2)

cycles2 = 7×1 cell array
    {[1 5 2]}
    {[3 6 7]}
    {[2 5 6]}
    {[2 6 3]}
    {[2 4 1]}
    {[3 4 2]}
    {[7 4 3]}

mosaic(G2)

[Taehyub]

Thank you very much for the comment. This code seems to work in the following way: it extends MATLAB’s graph/digraph object to store 2D coordinates and labels, computes edge weights based on Euclidean distance, prunes the graph to retain only the core structure, then uses Delaunay triangulation to detect polygons, converts them into polyshape objects, and provides visualization. I had previously found and used this code, but since my original system is relatively large as shown in the original nodes I attached newly, nodes can overlap, and I was not able to achieve my intended goal. If I apply the idea of this code, I think it might be possible to use the cycle option with layout of "circles", convert edges and nodes into coordinates, and approach it in a similar way, but I still need more concrete ideas.

[Matt J]

It is not clear to me what it means for nodes to "overlap". Nodes occupy a single point, so to my mind overlapping nodes means you have duplicate nodes.

Perhaps you mean that edges can intersect? That would indeed disqualify the spatialgraph2D algorithm.

[Taehyub]

@Matt J I'm sorry for the confusion. You are right. What I meant to say is 'edge.' Thank you for your great insight.

Answer 2

[Umar]

Hi @Taehyub,

Thanks for sharing your questions. I understand you want a labeling-independent way to find “minimal loop units,” like the 3-node triangles in your graphs. Below, I’ve addressed your questions step by step and provided a MATLAB script you can run to get consistent results across isomorphic graphs.

Question 1

You mentioned, I know cyclebasis can vary with spanning tree/edge ordering. What’s the recommended way in MATLAB to obtain “minimal loop units” that do not depend on node labeling or edge input order?

Solution


The built-in cyclebasis function depends on the spanning tree and edge order, which can vary with node labeling. To get a labeling-independent set of minimal loops (triangles in your example), the recommended approach is to explicitly enumerate all 3-node cycles and verify which combinations form triangles. This guarantees consistent results for isomorphic graphs.

Question 2

You mentioned, For example, in the above case, each cycle is a 3-node triangle, and there should be seven such cycles. How can I obtain them reliably?

Solution


The MATLAB script below implements this approach:

• It generates all 3-node combinations of nodes.
• Checks which combinations form triangles by verifying all three edges exist.
• Plots the graphs with highlighted triangles, each with a distinct color and label.

This ensures you get the exact seven triangles for each graph, independent of node labels or edge ordering.

Implementation

   clc; clear; close all;

   %% -----------------------------
   %% Graph 1
   %% -----------------------------
   node = [
   2 7
   2 3
   3 4
   4 5
   5 6
   6 1
   1 4
   1 5
   3 6
   1 3
   5 7
   6 7
   2 6
   5 8];

   G = graph(node(:, 1), node(:, 2), []);

   figure(1);
   h1 = plot(G, 'Layout', 'force');
   title('Graph 1');
   labelnode(h1, 1:numnodes(G), arrayfun(@num2str, 1:numnodes(G), 
   'UniformOutput', false));

   T = nchoosek(1:numnodes(G), 3);  % all 3-node combinations
   triangles = [];
   edges = sort(node, 2);

   for k = 1:size(T,1)
    comb = sort(T(k,:));
    if all(ismember(sort([comb(1) comb(2)]), edges, 'rows')) && ...
       all(ismember(sort([comb(2) comb(3)]), edges, 'rows')) && ...
       all(ismember(sort([comb(1) comb(3)]), edges, 'rows'))
        triangles = [triangles; comb];
    end
  end

disp('Triangles in Graph 1:');
disp(triangles);

colors = lines(size(triangles,1));
hold on
for k = 1:size(triangles,1)
  highlight(h1, triangles(k,:), 'EdgeColor', colors(k,:), 'LineWidth', 2);
  coords = mean([h1.XData(triangles(k,:))' h1.YData(triangles(k,:))'], 1);
  text(coords(1), coords(2), ['T' num2str(k)], 'FontWeight','bold', 'Color',   
 colors(k,:));
end

   %% -----------------------------
  %% Graph 2
  %% -----------------------------
  node2 = [
  1 2
  2 3
  3 4
  4 1
  1 5
  5 6
  2 4
  6 7
  3 6
  2 5
  3 7
  4 7
  2 6
  6 8];

G2 = graph(node2(:, 1), node2(:, 2), []);

figure(2);
h2 = plot(G2, 'Layout', 'force');
title('Graph 2');
labelnode(h2, 1:numnodes(G2), arrayfun(@num2str, 1:numnodes(G2), 
'UniformOutput', false));

T2 = nchoosek(1:numnodes(G2), 3);  
triangles2 = [];
edges2 = sort(node2, 2);

for k = 1:size(T2,1)
  comb = sort(T2(k,:));
  if all(ismember(sort([comb(1) comb(2)]), edges2, 'rows')) && ...
     all(ismember(sort([comb(2) comb(3)]), edges2, 'rows')) && ...
     all(ismember(sort([comb(1) comb(3)]), edges2, 'rows'))
      triangles2 = [triangles2; comb];
  end
end

disp('Triangles in Graph 2:');
disp(triangles2);

colors = lines(size(triangles2,1));
hold on
for k = 1:size(triangles2,1)
  highlight(h2, triangles2(k,:), 'EdgeColor', colors(k,:), 'LineWidth', 2);
  coords = mean([h2.XData(triangles2(k,:))' h2.YData(triangles2(k,:))'], 1);
  text(coords(1), coords(2), ['T' num2str(k)], 'FontWeight','bold', 'Color', 
colors(k,:));
end

Please see attached.


This script gives a reliable, labeling-independent set of minimal loops (triangles) for any graph. You can run it for both graphs in your example and verify that each has exactly seven triangles. Each triangle is plotted with a distinct color and labeled for clarity.

[Matt J]

It generates all 3-node combinations of nodes.

Seems like a very combinatorically heavy approach. Also, how would you generalize it to graphs that don't consist purely of triangles?

[Umar]

@Matt J, Agreed, this approach is not scalable in general. My graphs are relatively small, and the minimal loops of interest are triangles, so brute-force enumeration is simple, labeling-invariant, and guarantees the exact set of loops I need. For larger or more complex graphs, I would turn to more efficient methods such as spatialgraph2D or minimum cycle basis algorithms.

[Taehyub]

@Umar Thank you very much for the comment. As I mentioned above, our system is quite large, as shown in the original nodes I attached newly. Your 3-node combinations approach seems like a truly innovative idea. I will look into it more deeply.