# Enumerate path in a circuit

Consider the following circuit and its directed graph. Directed graphs can represent many things. In our case though, it represent a digital circuit as shown below. Consider each node of the graph as a logical gate of the circuit. The incoming edges are input to the logic gate and outgoing edges are the output of the logic gate.

Following figure shows its directed graph. Buffer Y9 and Y10 are ignored since they were inserted to distinguish u_1 from p_00 etc. Now if we need to test this circuit for path delays, we need to enumerate the path firsts. After converting the circuit into a graph, enumeration the path is a routine problem and can be solved by using Depth First Search algorithm. An edge from one node to other shows that a wire exists between them. By path we mean this wire only.

The path is shown below. dot Tool is used to generate this graph. Now the problem is reduced to enumerating the path between input and output.﻿ This can be done using the standard Depth First Search (DFS). The procedure is following.

• Partition the graph We partition nodes of the given graph $G(E,V)$ in to two sets namely $V_{input}$ and $V_{output}$.
• Clearly, $latex V_{input} \bigcup V_{output} \subset V$. We may have a trivial case in which $V_{input} \bigcup V_{output} \subseteq V$. Clearly, the number of path in this situation is equal to the number of edges in $G$. In our problem we are already been provided with $V_{input} = \{a , b\}$ and $V_{output} = \{u_1, u_2, u_3, u_4\}$.
• Step 1 Start from a node $V_i \in V_{input}$. Mark this node asused. Initialize counter to 0. Initialize stack to keep track of path.
• Step 2 Pick an edge and reach to the next connected node. Push this edge on the stack. Do it till you hit a node which belongs to $V_{output}$. Increase counter by 1.
• Step 3 Pop the stack and traceback your path. Do it till you meet a node which have an edge which has not been pushed on to the stack. When you get this node. Repeat step 2. Else go to step 4.
• Step 4 Counter will give you the number of path between input node $V-i$ and the output nodes. If there are nodes left in $V_{input}$, go to step 1. Else go to step 5.
• Step 5 Each input node have a counter value. Add them up. This gives the total number of path in the circuit.﻿ ﻿

Now these steps can be visualized easily. We start from node a and traverse this graph.

In the same way, we can enumerate all the paths from input node b to the output nodes.

Well, we used graphviz to generate these graphs. We give these scripts.

&lt;p style=&quot;text-align: left;&quot;&gt;digraph G {
node[fontzise = 10, width="0.4", height = "0.4", margin = 0];
edge[color=red]
subgraph cluster001{
style = filled;
color = lightgrey;
node [style= filled, color=white]
start [shape = box];
start -> a [penwidth = 4, headlabel = 0];
a -&gt; w [label = 0];
w -> p00 [label = 0];
p00 -> u1[label = 0, headlabel="1"];
w -> p01;
a -> p11;
p11 -> u4 [headlabel = 5];
a -> p10;
p10 -> u3 [headlabel = 6];
}
subgraph cluster002{
style=filled;
color=pink;
edge [color = blue]
u1 -> p_u1;
//p_u1 -&gt; p_p00;
p_u1 -> p00;
u2 -> p_u2;
p_u2 -> p_p00;
p_p00 -> w;
///
u3 -> p_u3;
p_u3 -> p_p01;
p_p01 -> p_w;
p_w -&gt; a;
//
//
u4 -> p_u4;
p_u4 -> p_p11;
p_p11 -> a;
//
}
subgraph cluster004{
style=filled;
color=pink;
edge [color = blue]
u3 -> p_u3_;
p_u3_ -&gt; p_p10_;
p_p10_ -> a [headlabel = "END"];
u2 -> p_u2_;
p_u2_ -> p11;

}

subgraph cluster004{
p00; p01; p11; p10;
}
subgraph cluster03{
style = filled;
color = lightgrey;
node [style= filled, color=white]
u1; u2; u3; u4;
}

}

digraph G {

node[fontzise = 10, width="0.4", height = "0.4", margin = 0];
edge[color=red]

subgraph cluster001{
style = filled;
color = lightgrey;
node [style= filled, color=white]
start [shape = box];
start -> b [penwidth = 4, headlabel = 0];
b -> x [label = 0];
x -> p00 [label = 0];
p00 -> u1[label = 0, headlabel="1"]; // pop
x -> p10;
p10 -> u3[headlabel = 3]; // pop
b -> p01;
p01 -> u3 [headlabel =4]; // pop
b -> p11;
p11 -> u2 [headlabel = 5]; // pop
p11 -> u4 [headlabel = 6]; // pop
}
subgraph clusterPOP1{
style=filled;
color=pink;
edge [color = blue]
u1 -> p_u1;
p_u1 -> p00;// Go forward.
u2 -> p_u2;
p_u2 -> p_p00;
p_p00 -> x; // go forward.
u3 -> p_p10;
p_p10 -> p_x;
p_x -> b; // go forward.
u3 -> p_u3;
p_u3 -> p_p01;
p_p01 -> b; // go forward.
u4 -> p_u4;
p_u4 -> p_p11;
p_p11 -> b [headlabel = "EXIT"];
}

subgraph clusterPOP2{
style=filled;
color=pink;
edge [color = blue]
u2 -> p_u2_;
p_u2_ -> p11; // go forward.

}

subgraph cluster03{
style = filled;
color = lightgrey;
node [style= filled, color=blue]
u1; u2; u3; u4;
}
}