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.

Circuit is drawn in Qucs simulator which I think will be of great value in near future.

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.

Figure representing a digital circuit.
  • 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.

Start from a and enumerate all the paths ending at the nodes starting with u. We have total of 6 paths. As we hit an dead end, we increase the number of path by one. The numerics displayed at the end of node represent this only. Edges with label 0 shows that this is the first path we have taken. For examplem a->w->p00->u1 is one path. We push these nodes on a stack. We increase the path number as we hit u1 since it belongs to the end point. From here we trace back to hunt down the rest of the paths which are shown by blue edges. This trace-backing is most naturally implemented using stack. Any node name prefixed with p_ represents pop operation on the stack. Here, from u1 we got to p_u1 which mean that pop u1. We reach p00 and we know that there is one edge we have not traversed since it was not in the stack. Now p00->u2 is one more path and we increase the path by one (path = 2 now). We traceback through p_u2->p_p01->p-w (pop u2, p01, and w) and reach a to find a new edge p11 to be traversed. So on and so forth, we enumerate all the paths. We should label every edge with label path_value so that we can keep track of the paths.

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

 

Path from node b to output. The procedure is explained in the previous figure. Here also we get 6 paths.

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

 

<p style="text-align: left;">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 -> w [label = 0];
 w -> p00 [label = 0];
 p00 -> u1[label = 0, headlabel="1"];
 p00 -> u2 [headlabel="2"];
 w -> p01;
 p01 -> u3[headlabel = 3];
 a -> p11;
 p11 -> u2 [headlabel =4];
 p11 -> u4 [headlabel = 5];
 a -> p10;
 p10 -> u3 [headlabel = 6];
}
subgraph cluster002{
style=filled;
color=pink;
edge [color = blue]
u1 -> p_u1;
//p_u1 -> 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 -> 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_ -> 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
 p00 -> u2 [headlabel="2"];// 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;
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s