In Lessons 1–2 of this chapter, we used block diagrams and block-diagram algebra to simplify interconnections. Signal flow graphs provide an alternative representation that is often algebraically cleaner for multi-loop structures: instead of repeatedly reducing blocks, we can compute the overall transfer directly from a graph using Mason’s formula.

Throughout this lesson, we assume linear time-invariant (LTI) relations in the Laplace domain, so each branch gain is a transfer function in \( s \), and node signals are Laplace transforms of time-domain signals.

A key benefit is that Mason’s formula expresses the input–output transfer function as a rational expression built from: \( \{\text{forward paths}\} \), \( \{\text{loops}\} \), and \( \{\text{non-touching loop sets}\} \).

A signal flow graph is a directed graph whose nodes represent variables (signals) and whose directed branches represent linear relationships (gains) between signals. If there is a branch from node \( x_j \) to node \( x_i \) with gain \( a_{ij}(s) \), then the contribution from \( x_j \) into \( x_i \) is \( a_{ij}(s)\,x_j \).

Node equation (summation rule). Each node variable equals the sum of all incoming contributions:

\[ x_i(s) \;=\; \sum_{j \in \mathcal{N}_i^-} a_{ij}(s)\,x_j(s) \;+\; b_i(s)\,r(s), \]

where \( \mathcal{N}_i^- \) denotes the set of nodes with branches entering node \( i \), \( r(s) \) is the input node (or an external input), and \( b_i(s) \) is the input gain into node \( i \).

Forward path. A forward path from input node \( r \) to output node \( y \) is a directed path that does not repeat a node. Its path gain is the product of branch gains along that path.

\[ P_k(s) \;=\; \prod_{(j \rightarrow i)\in \text{path }k} a_{ij}(s). \]

Loop. A loop is a closed directed path that starts and ends at the same node without repeating other nodes. Its loop gain is the product of gains along the loop.

\[ L_\ell(s) \;=\; \prod_{(j \rightarrow i)\in \text{loop }\ell} a_{ij}(s). \]

Touching / non-touching loops. Two loops are touching if they share at least one node. They are non-touching if they share no nodes. A set of loops is non-touching if every pair within the set is non-touching.

flowchart LR
  R["r(s)"] -->|"G1"| A["x1"]
  A -->|"G2"| B["x2"]
  B -->|"G3"| C["x3"]
  C -->|"1"| Y["y(s)"]

  A -->|"G4"| C

  B -->|"H1"| D["x4"]
  D -->|"H2"| B

  C -->|"K1"| E["x5"]
  E -->|"K2"| C
        

In the graph above, there are two distinct forward paths from \( r \) to \( y \): \( r \rightarrow x1 \rightarrow x2 \rightarrow x3 \rightarrow y \) and \( r \rightarrow x1 \rightarrow x3 \rightarrow y \). There are at least two loops: \( x2 \rightarrow x4 \rightarrow x2 \) with gain \( H1\,H2 \), and \( x3 \rightarrow x5 \rightarrow x3 \) with gain \( K1\,K2 \). These two loops are non-touching because they share no nodes.

Conceptually, a block diagram represents operators (blocks) and summing junctions explicitly. A signal flow graph represents only variables as nodes and uses directed weighted branches for the linear relations between variables. The conversion is systematic:

• Each distinct signal becomes a node variable \( x_i \).
• Each block relation \( x_{\text{out}} = G(s)\,x_{\text{in}} \) becomes a branch \( x_{\text{in}} \rightarrow x_{\text{out}} \) with gain \( G(s) \).
• Each summing junction \( x = \sum_k \pm x_k \) is captured by multiple incoming branches into node \( x \), where signs are absorbed into branch gains (e.g., gain \( -1 \)).

The essential modeling constraint is that node equations must remain linear in the Laplace domain. Therefore, SFGs in this chapter apply to LTI interconnections already expressible by transfer functions.

Let the input be \( r(s) \) and the output be \( y(s) \). Suppose there are \( N_p \) distinct forward paths from input to output with gains \( P_1,\dots,P_{N_p} \).

Definition (Graph determinant). Define \( \Delta \) as:

\[ \Delta(s) \;=\; 1 \;-\; \sum_{\ell} L_\ell(s) \;+\; \sum_{\ell_1<\ell_2} L_{\ell_1}(s)\,L_{\ell_2}(s) \;-\; \sum_{\ell_1<\ell_2<\ell_3} L_{\ell_1}(s)\,L_{\ell_2}(s)\,L_{\ell_3}(s) \;+\;\cdots, \]

where each sum is taken only over sets of pairwise non-touching loops. (So the second sum is over all non-touching loop pairs, the third over all non-touching loop triples, etc.)

For each forward path \( P_k \), define \( \Delta_k \) as the same expression as \( \Delta \), but with all loops that touch the forward path removed.

Mason’s Gain Formula. The overall transfer function is:

\[ T(s) \;=\; \frac{y(s)}{r(s)} \;=\; \frac{\sum_{k=1}^{N_p} P_k(s)\,\Delta_k(s)}{\Delta(s)}. \]

This formula is exact for linear graphs where node equations obey the summation rule. It can be interpreted as: numerator aggregates contributions of each forward path corrected by the loop structure that does not interact with that path; denominator encodes the total “feedback amplification/attenuation” induced by all loop combinations.

We give a derivation based on linear algebra (assumed background) and a determinant expansion that corresponds to loop combinatorics. This stays within the course prerequisites: linear algebra and Laplace-domain LTI modeling.

5.1 Node equations in matrix form

Collect the internal node signals into a vector \( \mathbf{x}(s)\in\mathbb{R}^n \). Let \( \mathbf{A}(s)\in\mathbb{R}^{n\times n} \) encode branch gains between internal nodes: \( a_{ij}(s) \) is the gain on the branch \( x_j \rightarrow x_i \), and \( 0 \) if absent. Let \( \mathbf{b}(s)\in\mathbb{R}^n \) encode input branches \( r \rightarrow x_i \). Then node equations compactly become:

\[ \mathbf{x}(s) \;=\; \mathbf{A}(s)\,\mathbf{x}(s) \;+\; \mathbf{b}(s)\,r(s). \]

Assuming \( \det(\mathbf{I}-\mathbf{A}(s)) \neq 0 \), we solve:

\[ \mathbf{x}(s) \;=\; (\mathbf{I}-\mathbf{A}(s))^{-1}\,\mathbf{b}(s)\,r(s). \]

If the output is a linear combination of node variables, \( y(s)=\mathbf{c}(s)^\top \mathbf{x}(s) \), then the transfer is:

\[ T(s) \;=\; \frac{y(s)}{r(s)} \;=\; \mathbf{c}(s)^\top (\mathbf{I}-\mathbf{A}(s))^{-1}\mathbf{b}(s). \]

5.2 Adjugate identity and the appearance of a determinant ratio

Using the identity \( \mathbf{M}^{-1} = \operatorname{adj}(\mathbf{M})/\det(\mathbf{M}) \) for invertible \( \mathbf{M} \), we obtain:

\[ T(s) \;=\; \frac{\mathbf{c}(s)^\top \operatorname{adj}(\mathbf{I}-\mathbf{A}(s))\,\mathbf{b}(s)} {\det(\mathbf{I}-\mathbf{A}(s))}. \]

Thus Mason’s formula will follow if we can show: (i) \( \det(\mathbf{I}-\mathbf{A}) \) equals the loop-based \( \Delta \), and (ii) the numerator expands into the sum over forward paths \( P_k \) multiplied by the corresponding “cofactor determinants” that equal \( \Delta_k \).

5.3 Key lemma: determinant equals the loop combination polynomial

Consider the Leibniz formula:

\[ \det(\mathbf{I}-\mathbf{A}) \;=\; \sum_{\pi\in S_n} \operatorname{sgn}(\pi)\,\prod_{i=1}^n (\mathbf{I}-\mathbf{A})_{i,\pi(i)}. \]

Each permutation \( \pi \) decomposes uniquely into disjoint cycles. Selecting an off-diagonal entry \( -a_{i,\pi(i)} \) corresponds to choosing a directed edge \( x_{\pi(i)} \rightarrow x_i \). A product of such selections forms a set of directed cycles with no shared nodes (because the cycles are disjoint). Therefore, each non-identity cycle contributes a loop gain (with a sign) and disjoint cycles correspond to non-touching loops.

When a cycle is not chosen at a node, we choose the diagonal entry \( 1 \). Hence the determinant expansion enumerates all collections of disjoint directed cycles (non-touching loops), with alternating signs by cycle count, yielding:

\[ \det(\mathbf{I}-\mathbf{A}) \;=\; 1 \;-\; \sum_{\ell} L_\ell \;+\; \sum_{\ell_1<\ell_2} L_{\ell_1}L_{\ell_2} \;-\; \sum_{\ell_1<\ell_2<\ell_3} L_{\ell_1}L_{\ell_2}L_{\ell_3} \;+\;\cdots \;\equiv\; \Delta. \]

This is the algebraic reason the loop-combination polynomial is sometimes called the graph “determinant.”

5.4 Numerator: cofactors enforce “remove loops touching the path”

The adjugate element \( \operatorname{adj}(\mathbf{I}-\mathbf{A})_{ij} \) equals the cofactor \( C_{ji} \), i.e., a signed determinant of a minor matrix that removes row \( j \) and column \( i \). Combinatorially, this enforces that any cycle selection cannot use nodes on a chosen route that connects the input injection point to the output extraction point (otherwise the minor determinant vanishes due to node reuse constraints).

One can show that each term in \( \mathbf{c}^\top \operatorname{adj}(\mathbf{I}-\mathbf{A})\mathbf{b} \) corresponds to a unique forward path \( P_k \), and the remaining determinant factor equals the loop polynomial formed by loops not touching that path, i.e. \( \Delta_k \). Summing over all possible forward paths yields the numerator \( \sum_k P_k \Delta_k \), completing the derivation of Mason’s formula.

For hand calculations, Mason’s formula is most effective when applied systematically:

1. List all forward paths \( P_k \) from input to output.
2. List all individual loops \( L_\ell \).
3. Find all non-touching loop pairs, triples, etc., and form \( \Delta \).
4. For each forward path, remove touching loops and form \( \Delta_k \).
5. Compute \( T(s)=\left(\sum_k P_k\Delta_k\right)/\Delta \).

flowchart TD
  S["Start: given signal flow graph"] --> P1["Enumerate forward paths (input to output)"]
  P1 --> P2["Compute each path gain Pk = product of branch gains"]
  P2 --> L1["Enumerate simple loops (directed cycles)"]
  L1 --> L2["Compute each loop gain Li = product of branch gains"]
  L2 --> NT["Find all non-touching loop sets (pairs, triples, ...)"]
  NT --> D["Build Delta = 1 - sum(Li) + sum(Li*Lj) - sum(Li*Lj*Lk) + ..."]
  D --> DK["For each path k: remove loops touching the path, build Delta_k"]
  DK --> T["Compute T = (sum_k Pk*Delta_k) / Delta"]
  T --> E["End"]
        

Computationally, loop/path enumeration can be exponential in the worst case. In control engineering practice, SFGs produced from block diagrams are usually small enough that enumeration is feasible, and symbolic libraries can simplify the final rational expression.

Using the graph shown in Section 2, identify forward paths and loops.

Forward paths.

• Path 1: \( r \rightarrow x1 \rightarrow x2 \rightarrow x3 \rightarrow y \), so \( P_1 = G1\,G2\,G3 \).
• Path 2: \( r \rightarrow x1 \rightarrow x3 \rightarrow y \), so \( P_2 = G1\,G4 \).

Loops.

• Loop A: \( x2 \rightarrow x4 \rightarrow x2 \), \( L_A = H1\,H2 \).
• Loop B: \( x3 \rightarrow x5 \rightarrow x3 \), \( L_B = K1\,K2 \).

Non-touching loop sets. Loops A and B are non-touching, so the only non-touching pair product is \( L_A L_B \).

Compute \( \Delta \).

\[ \Delta \;=\; 1 \;-\; (L_A + L_B) \;+\; (L_A L_B) \;=\; 1 \;-\; (H1H2 + K1K2) \;+\; (H1H2)(K1K2). \]

Compute \( \Delta_1 \) and \( \Delta_2 \).

Path 1 passes through nodes \( x1,x2,x3 \), so it touches both loops A (touches \( x2 \)) and B (touches \( x3 \)). Therefore, all loops are removed: \( \Delta_1 = 1 \).

Path 2 passes through nodes \( x1,x3 \), so it touches loop B but does not touch loop A. Hence: \( \Delta_2 = 1 - L_A = 1 - H1H2 \).

Overall transfer.

\[ T(s) \;=\; \frac{P_1\Delta_1 + P_2\Delta_2}{\Delta} \;=\; \frac{(G1G2G3)\cdot 1 + (G1G4)\cdot(1 - H1H2)} {1 - (H1H2 + K1K2) + (H1H2)(K1K2)}. \]

This expression can be algebraically simplified, or evaluated numerically after substituting specific transfer functions for \( G1,G2,G3,G4,H1,H2,K1,K2 \).

Below are reference implementations for computing Mason’s formula from an SFG. Two practical strategies exist:

• Graph-enumeration approach (Mason directly): enumerate forward paths and simple loops, then build \( \Delta \) and \( \Delta_k \).
• Matrix approach (verification / alternative): build \( \mathbf{A} \), compute \( T=\mathbf{c}^\top(\mathbf{I}-\mathbf{A})^{-1}\mathbf{b} \).

8.1 Python (SymPy + NetworkX optional) — Mason Enumeration

Useful libraries: sympy (symbolic algebra), networkx (graph utilities), and optionally control for transfer-function objects (numerical validation).

# Mason's Gain Formula (symbolic) for small-to-medium graphs
# Nodes are strings; edges are (u, v) with gain as a SymPy expression.

import sympy as sp
from itertools import combinations

def all_simple_paths(adj, src, dst, visited=None):
    if visited is None:
        visited = set()
    if src == dst:
        return [[dst]]
    visited.add(src)
    paths = []
    for (nxt, gain) in adj.get(src, []):
        if nxt not in visited:
            for p in all_simple_paths(adj, nxt, dst, visited.copy()):
                paths.append([src] + p)
    return paths

def path_gain(path, gain_map):
    g = sp.Integer(1)
    for u, v in zip(path[:-1], path[1:]):
        g *= gain_map[(u, v)]
    return sp.simplify(g)

def all_simple_cycles(adj):
    # Simple DFS cycle enumeration (works well for small graphs)
    cycles = set()
    nodes = list(adj.keys())

    def dfs(start, current, visited, stack):
        for (nxt, _) in adj.get(current, []):
            if nxt == start and len(stack) > 1:
                cyc = tuple(stack + [start])
                # normalize rotation to avoid duplicates
                core = cyc[:-1]
                mins = min(range(len(core)), key=lambda i: core[i])
                norm = core[mins:] + core[:mins]
                cycles.add(tuple(norm))
            elif nxt not in visited and nxt in adj:
                dfs(start, nxt, visited | {nxt}, stack + [nxt])

    for s in nodes:
        dfs(s, s, {s}, [s])

    # Convert each cycle to edge list representation
    out = []
    for cyc in cycles:
        out.append(list(cyc) + [cyc[0]])
    return out

def loop_gain(cycle, gain_map):
    g = sp.Integer(1)
    for u, v in zip(cycle[:-1], cycle[1:]):
        g *= gain_map[(u, v)]
    return sp.simplify(g)

def nodes_in_cycle(cycle):
    return set(cycle[:-1])

def delta_from_loops(loop_list, loop_gains):
    # Build Delta = 1 - sum(L) + sum(products of 2 non-touching) - ...
    Delta = sp.Integer(1)
    m = len(loop_list)
    loop_nodes = [nodes_in_cycle(c) for c in loop_list]

    for k in range(1, m + 1):
        term_sum = sp.Integer(0)
        for idxs in combinations(range(m), k):
            # non-touching check
            ok = True
            used = set()
            prod = sp.Integer(1)
            for i in idxs:
                if loop_nodes[i] & used:
                    ok = False
                    break
                used |= loop_nodes[i]
                prod *= loop_gains[i]
            if ok:
                term_sum += prod
        if k % 2 == 1:
            Delta -= term_sum
        else:
            Delta += term_sum

    return sp.simplify(Delta)

def mason_gain(adj, gain_map, src, dst):
    # forward paths
    paths = all_simple_paths(adj, src, dst)
    P = [path_gain(p, gain_map) for p in paths]

    # loops
    cycles = all_simple_cycles(adj)
    L = [loop_gain(c, gain_map) for c in cycles]

    Delta = delta_from_loops(cycles, L)

    # Delta_k for each path: remove loops that touch path nodes
    numerator = sp.Integer(0)
    for pk, path in zip(P, paths):
        path_nodes = set(path)
        # filter loops not touching the path
        filt_cycles = []
        filt_L = []
        for cyc, lg in zip(cycles, L):
            if nodes_in_cycle(cyc) & path_nodes:
                continue
            filt_cycles.append(cyc)
            filt_L.append(lg)
        Delta_k = delta_from_loops(filt_cycles, filt_L)
        numerator += pk * Delta_k

    T = sp.simplify(numerator / Delta)
    return T, paths, cycles, Delta

# Example: graph from Section 2 (symbolic gains)
G1,G2,G3,G4,H1,H2,K1,K2 = sp.symbols('G1 G2 G3 G4 H1 H2 K1 K2')

adj = {
    "r":  [("x1", G1)],
    "x1": [("x2", G2), ("x3", G4)],
    "x2": [("x3", G3), ("x4", H1)],
    "x4": [("x2", H2)],
    "x3": [("y", sp.Integer(1)), ("x5", K1)],
    "x5": [("x3", K2)],
    "y":  []
}

gain_map = {}
for u, outs in adj.items():
    for v, g in outs:
        gain_map[(u, v)] = g

T, paths, cycles, Delta = mason_gain(adj, gain_map, "r", "y")
print("Forward paths:", paths)
print("Loops:", cycles)
print("Delta:", sp.factor(Delta))
print("T(s):", sp.factor(T))
      

8.2 C++ (from scratch numeric Mason) — Suitable for Embedded/Performance Settings

Useful libraries: Eigen (linear algebra verification), Boost Graph Library (optional). Below is a compact from-scratch numeric version (double precision) for small graphs.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <functional>

struct Edge {
  int to;
  double gain;
};

static inline long long key(int u, int v) {
  return (static_cast<long long>(u) << 32) ^ static_cast<unsigned long long>(v);
}

void dfs_paths(int u, int dst,
               const std::vector<std::vector<Edge>>& adj,
               std::vector<int>& cur,
               std::vector<std::vector<int>>& out,
               std::vector<bool>& vis) {
  if (u == dst) { out.push_back(cur); return; }
  vis[u] = true;
  for (const auto& e : adj[u]) {
    if (!vis[e.to]) {
      cur.push_back(e.to);
      dfs_paths(e.to, dst, adj, cur, out, vis);
      cur.pop_back();
    }
  }
  vis[u] = false;
}

double path_gain(const std::vector<int>& p,
                 const std::unordered_map<long long,double>& gmap) {
  double g = 1.0;
  for (size_t i=0;i+1<p.size();++i) g *= gmap.at(key(p[i], p[i+1]));
  return g;
}

void dfs_cycles(int start, int u,
                const std::vector<std::vector<Edge>>& adj,
                std::vector<int>& stack,
                std::vector<bool>& in_stack,
                std::vector<std::vector<int>>& cycles) {
  in_stack[u] = true;
  for (const auto& e : adj[u]) {
    if (e.to == start && stack.size() >= 2) {
      std::vector<int> cyc = stack;
      cyc.push_back(start);
      cycles.push_back(cyc);
    } else if (!in_stack[e.to] && e.to >= start) {
      stack.push_back(e.to);
      dfs_cycles(start, e.to, adj, stack, in_stack, cycles);
      stack.pop_back();
    }
  }
  in_stack[u] = false;
}

double loop_gain(const std::vector<int>& cyc,
                 const std::unordered_map<long long,double>& gmap) {
  double g = 1.0;
  for (size_t i=0;i+1<cyc.size();++i) g *= gmap.at(key(cyc[i], cyc[i+1]));
  return g;
}

std::unordered_set<int> nodes_in_cycle(const std::vector<int>& cyc) {
  return std::unordered_set<int>(cyc.begin(), cyc.end()-1);
}

double delta_from_loops(const std::vector<std::vector<int>>& loops,
                        const std::vector<double>& L) {
  const int m = static_cast<int>(loops.size());
  std::vector<std::unordered_set<int>> ln(m);
  for (int i=0;i<m;++i) ln[i] = nodes_in_cycle(loops[i]);

  double Delta = 1.0;

  // enumerate subsets via recursion (ok for small m)
  std::function<void(int,int,double,std::unordered_set<int>&)> rec;
  rec = [&](int idx, int chosen, double prod, std::unordered_set<int>& used) {
    if (idx == m) {
      if (chosen > 0) {
        if (chosen % 2 == 1) Delta -= prod;
        else Delta += prod;
      }
      return;
    }
    // skip
    rec(idx+1, chosen, prod, used);

    // take if non-touching
    bool ok = true;
    for (int node : ln[idx]) { if (used.count(node)) { ok = false; break; } }
    if (ok) {
      for (int node : ln[idx]) used.insert(node);
      rec(idx+1, chosen+1, prod * L[idx], used);
      for (int node : ln[idx]) used.erase(node);
    }
  };

  std::unordered_set<int> used;
  rec(0, 0, 1.0, used);
  return Delta;
}

int main() {
  // Nodes: 0=r, 1=x1, 2=x2, 3=x3, 4=x4, 5=x5, 6=y
  const int n = 7;
  std::vector<std::vector<Edge>> adj(n);
  std::unordered_map<long long,double> gmap;

  auto add_edge = [&](int u, int v, double g) {
    adj[u].push_back({v,g});
    gmap[key(u,v)] = g;
  };

  // Example numeric gains (replace with evaluated transfer-function magnitudes if desired)
  add_edge(0,1,2.0);  // G1
  add_edge(1,2,3.0);  // G2
  add_edge(2,3,4.0);  // G3
  add_edge(3,6,1.0);  // to y
  add_edge(1,3,0.5);  // G4
  add_edge(2,4,0.2);  // H1
  add_edge(4,2,0.1);  // H2
  add_edge(3,5,0.3);  // K1
  add_edge(5,3,0.4);  // K2

  // forward paths
  std::vector<std::vector<int>> paths;
  std::vector<int> cur = {0};
  std::vector<bool> vis(n,false);
  dfs_paths(0, 6, adj, cur, paths, vis);

  // loops (simple cycle enumeration)
  std::vector<std::vector<int>> loops;
  for (int s=0;s<n;++s) {
    std::vector<bool> in_stack(n,false);
    std::vector<int> st = {s};
    dfs_cycles(s, s, adj, st, in_stack, loops);
  }

  std::vector<double> L;
  for (const auto& cyc : loops) L.push_back(loop_gain(cyc, gmap));

  double Delta = delta_from_loops(loops, L);

  double num = 0.0;
  for (const auto& p : paths) {
    double Pk = path_gain(p, gmap);
    std::unordered_set<int> pnodes(p.begin(), p.end());

    // filter loops not touching this path
    std::vector<std::vector<int>> fl;
    std::vector<double> fL;
    for (size_t i=0;i<loops.size();++i) {
      auto ln = nodes_in_cycle(loops[i]);
      bool touch = false;
      for (int node : ln) if (pnodes.count(node)) { touch = true; break; }
      if (!touch) { fl.push_back(loops[i]); fL.push_back(L[i]); }
    }
    double Delta_k = delta_from_loops(fl, fL);
    num += Pk * Delta_k;
  }

  double T = num / Delta;
  std::cout << "Delta = " << Delta << "\n";
  std::cout << "T = " << T << "\n";
  return 0;
}
      

8.3 Java (JGraphT optional) — Clean Graph Representation + Mason Evaluation

Useful library: JGraphT for graph traversal; Symja (symbolic) or plain doubles (numeric). Below is a minimal numeric implementation pattern (from scratch style).

import java.util.*;

public class MasonGain {
  static class Edge {
    int to;
    double gain;
    Edge(int to, double gain) { this.to = to; this.gain = gain; }
  }

  static long key(int u, int v) {
    return (((long)u) << 32) ^ (v & 0xffffffffL);
  }

  static void dfsPaths(int u, int dst, List<List<Edge>> adj,
                       boolean[] vis, List<Integer> cur,
                       List<List<Integer>> out) {
    if (u == dst) { out.add(new ArrayList<>(cur)); return; }
    vis[u] = true;
    for (Edge e : adj.get(u)) {
      if (!vis[e.to]) {
        cur.add(e.to);
        dfsPaths(e.to, dst, adj, vis, cur, out);
        cur.remove(cur.size()-1);
      }
    }
    vis[u] = false;
  }

  static double pathGain(List<Integer> p, Map<Long,Double> gmap) {
    double g = 1.0;
    for (int i=0;i+1<p.size();++i) g *= gmap.get(key(p.get(i), p.get(i+1)));
    return g;
  }

  static Set<Integer> nodesInCycle(List<Integer> cyc) {
    return new HashSet<>(cyc.subList(0, cyc.size()-1));
  }

  static double loopGain(List<Integer> cyc, Map<Long,Double> gmap) {
    double g = 1.0;
    for (int i=0;i+1<cyc.size();++i) g *= gmap.get(key(cyc.get(i), cyc.get(i+1)));
    return g;
  }

  static double deltaFromLoops(List<List<Integer>> loops, List<Double> L) {
    int m = loops.size();
    List<Set<Integer>> ln = new ArrayList<>();
    for (List<Integer> cyc : loops) ln.add(nodesInCycle(cyc));

    final double[] Delta = new double[]{1.0};

    class Rec {
      void go(int idx, int chosen, double prod, Set<Integer> used) {
        if (idx == m) {
          if (chosen > 0) {
            if (chosen % 2 == 1) Delta[0] -= prod;
            else Delta[0] += prod;
          }
          return;
        }
        // skip
        go(idx+1, chosen, prod, used);

        // take if non-touching
        boolean ok = true;
        for (int node : ln.get(idx)) if (used.contains(node)) { ok = false; break; }
        if (ok) {
          Set<Integer> used2 = new HashSet<>(used);
          used2.addAll(ln.get(idx));
          go(idx+1, chosen+1, prod * L.get(idx), used2);
        }
      }
    }
    new Rec().go(0,0,1.0,new HashSet<>());
    return Delta[0];
  }

  public static void main(String[] args) {
    int n = 7; // 0=r, 6=y
    List<List<Edge>> adj = new ArrayList<>();
    for (int i=0;i<n;i++) adj.add(new ArrayList<>());
    Map<Long,Double> gmap = new HashMap<>();

    java.util.function.BiConsumer<Integer,Integer> noop = (a,b) -> {};

    class Add {
      void edge(int u, int v, double g) {
        adj.get(u).add(new Edge(v,g));
        gmap.put(key(u,v), g);
      }
    }
    Add add = new Add();

    // Example numeric gains
    add.edge(0,1,2.0);
    add.edge(1,2,3.0);
    add.edge(2,3,4.0);
    add.edge(3,6,1.0);
    add.edge(1,3,0.5);
    add.edge(2,4,0.2);
    add.edge(4,2,0.1);
    add.edge(3,5,0.3);
    add.edge(5,3,0.4);

    // Forward paths
    List<List<Integer>> paths = new ArrayList<>();
    boolean[] vis = new boolean[n];
    List<Integer> cur = new ArrayList<>();
    cur.add(0);
    dfsPaths(0,6,adj,vis,cur,paths);

    // Loop enumeration omitted for brevity in this minimal snippet:
    // In production, use Johnson's algorithm or a library method to list simple cycles.
    // Then compute Delta and Delta_k exactly as shown in the Python/C++ versions.
    System.out.println("Forward paths found: " + paths.size());
    for (List<Integer> p : paths) System.out.println(p);
  }
}
      

For complete Java loop enumeration, consider Johnson’s algorithm (standard for simple cycles) or use JGraphT’s cycle enumeration utilities.

8.4 MATLAB and Simulink (Control System Toolbox + Verification)

MATLAB is convenient for symbolic or numeric verification. If you represent branch gains as transfer functions (tf objects), you can evaluate Mason’s formula numerically over frequency, or simplify symbolically using the Symbolic Math Toolbox.

% MATLAB: numeric verification using symbolic Mason expression (Symbolic Math Toolbox)
syms G1 G2 G3 G4 H1 H2 K1 K2 s

Delta = 1 - (H1*H2 + K1*K2) + (H1*H2)*(K1*K2);
T = (G1*G2*G3*1 + (G1*G4)*(1 - H1*H2)) / Delta;
T_simplified = simplify(T);
disp(T_simplified);

% Substitute transfer functions (example)
G1_tf = tf(2, [1 1]);    % 2/(s+1)
G2_tf = tf(3, [1 2]);    % 3/(s+2)
G3_tf = tf(4, [1 3]);    % 4/(s+3)
G4_tf = tf(1, [1 4]);    % 1/(s+4)
H1_tf = tf(0.2, 1);
H2_tf = tf(0.1, 1);
K1_tf = tf(0.3, 1);
K2_tf = tf(0.4, 1);

% Evaluate T by substituting into the symbolic structure (manual, numeric)
T_tf = (G1_tf*G2_tf*G3_tf + (G1_tf*G4_tf)*(1 - H1_tf*H2_tf)) / ...
       (1 - (H1_tf*H2_tf + K1_tf*K2_tf) + (H1_tf*H2_tf)*(K1_tf*K2_tf));

step(T_tf); grid on; title('Step response from Mason formula');
      

Simulink verification idea. Build the corresponding interconnection using Gain and Sum blocks and compare the simulated input–output response to T_tf above (step responses should match). This uses only concepts already covered: transfer functions, interconnections, and algebraic signal summation.

8.5 Wolfram Mathematica (Symbolic Determinant/Adjugate and Mason Structure)

(* Mathematica: symbolic Mason expression and simplification *)
ClearAll[G1, G2, G3, G4, H1, H2, K1, K2];

Delta = 1 - (H1 H2 + K1 K2) + (H1 H2) (K1 K2);
T = (G1 G2 G3 + (G1 G4) (1 - H1 H2)) / Delta;

FullSimplify[T]

(* Optional: verify using matrix form T = c^T (I - A)^(-1) b.
   Choose internal nodes x1..x5; define A according to edges among internal nodes.
*)
A = {
  {0, 0, G4, 0, 0},   (* x1 depends on internal nodes: none here, example placeholder *)
  {G2, 0, 0, 0, 0},   (* x2 depends on x1 via G2: adjust indexing to your chosen ordering *)
  {0, G3, 0, 0, K2},  (* x3 depends on x2 via G3 and x5 via K2 *)
  {0, H1, 0, 0, 0},   (* x4 depends on x2 via H1 *)
  {0, 0, K1, 0, 0}    (* x5 depends on x3 via K1 *)
};

(* NOTE: The above A is illustrative; you must ensure it matches your node ordering and edges. *)
      

Mathematica can also enumerate cycles using built-in graph functions, but the symbolic determinant approach is often the simplest for theoretical verification of small graphs.

Problem 1 (Single Loop Check): Consider a graph with a single forward path gain \( P \) and a single loop gain \( L \) that touches the forward path. Compute \( T \) using Mason’s formula.

Solution: There is one path, so \( \sum_k P_k\Delta_k = P\Delta_1 \). Since the loop touches the path, it is excluded from \( \Delta_1 \), hence \( \Delta_1=1 \). The determinant is \( \Delta = 1 - L \). Therefore:

\[ T \;=\; \frac{P}{1 - L}. \]

Problem 2 (Two Non-Touching Loops): Suppose there is a single forward path \( P \) and two non-touching loops with gains \( L_1 \) and \( L_2 \), and neither loop touches the forward path. Find \( T \).

Solution: Since neither loop touches the path, \( \Delta_1 = \Delta \). Also:

\[ \Delta \;=\; 1 - (L_1 + L_2) + (L_1L_2). \]

Hence \( T = \dfrac{P\Delta}{\Delta} = P \). This matches the intuition: loops in a disconnected non-interacting substructure cannot affect the input–output relation, and Mason’s formula cancels them automatically.

Problem 3 (Compute \( \Delta \) from loop inventory): A graph has three loops with gains \( L_1,L_2,L_3 \). Loops 1 and 2 are non-touching; loops 2 and 3 are non-touching; loops 1 and 3 touch. Write \( \Delta \).

Solution: Single-loop sum is \( L_1+L_2+L_3 \). Non-touching pairs are \( (1,2) \) and \( (2,3) \), so the pair sum is \( L_1L_2 + L_2L_3 \). There is no non-touching triple because loop 1 touches loop 3. Therefore:

\[ \Delta \;=\; 1 - (L_1 + L_2 + L_3) + (L_1L_2 + L_2L_3). \]

Problem 4 (Two Forward Paths with Touching Rules): A graph has two forward paths with gains \( P_1,P_2 \). There are two loops with gains \( L_a,L_b \), where \( L_a \) touches path 1 but not path 2, and \( L_b \) touches both paths. Compute \( \Delta_1,\Delta_2 \) and the resulting transfer \( T \) in terms of \( P_1,P_2,L_a,L_b \).

Solution: The global determinant includes both loops and (if non-touching) their product:

\[ \Delta \;=\; 1 - (L_a + L_b) + \Big(\text{include } L_aL_b \text{ only if non-touching}\Big). \]

For \( \Delta_1 \), remove loops that touch path 1: remove \( L_a \) and \( L_b \), so \( \Delta_1=1 \). For \( \Delta_2 \), remove loops that touch path 2: remove \( L_b \) but keep \( L_a \), so \( \Delta_2 = 1 - L_a \). Therefore:

\[ T \;=\; \frac{P_1\cdot 1 + P_2(1 - L_a)}{\Delta}. \]

Problem 5 (Determinant Interpretation): Let \( \mathbf{x}=\mathbf{A}\mathbf{x}+\mathbf{b}r \). Show that the condition for a unique solution is \( \det(\mathbf{I}-\mathbf{A}) \neq 0 \), and interpret this condition in the language of Mason’s formula.

Solution: Rearranging gives \( (\mathbf{I}-\mathbf{A})\mathbf{x}=\mathbf{b}r \). A unique solution exists iff \( \mathbf{I}-\mathbf{A} \) is invertible, i.e., iff \( \det(\mathbf{I}-\mathbf{A}) \neq 0 \). By the loop expansion lemma in Section 5, \( \det(\mathbf{I}-\mathbf{A}) \equiv \Delta \), so uniqueness is equivalently \( \Delta \neq 0 \). When \( \Delta = 0 \), the interconnection is algebraically singular (infinite or undefined gain in the Laplace domain), consistent with an ill-posed feedback interconnection.

We defined signal flow graphs as a variable-centric representation of linear interconnections, introduced forward paths and loop structures, and stated Mason’s Gain Formula: \( T = \left(\sum_k P_k\Delta_k\right)/\Delta \). We then connected the formula to linear algebra by expressing node equations as \( \mathbf{x}=\mathbf{A}\mathbf{x}+\mathbf{b}r \) and interpreting \( \Delta=\det(\mathbf{I}-\mathbf{A}) \) via cycle-based determinant expansions. Finally, we provided systematic hand-calculation steps and multi-language implementations for computing Mason’s formula in practice.