1 Introduction

In recent years, microfluidics-based biochips have received considerable attention as the implementation platform for lab-on-a-chip [1, 15]. Such composite systems can greatly simplify cumbersome laboratory procedures by manipulating fluids at nanoliter or at picoliter volume scale [35]. These systems can be used as platforms for faster and cheaper clinical diagnosis, for massively parallel DNA analysis, and for real-time bio-molecular detection and recognition [28]. Real-time reactions using proteins and DNA samples can also be performed very efficiently on these systems [20, 24, 25]. Such systems are also useful as immediate point-of-care health services [22, 26], for the management of bio-terrorism threats, and for real-time environmental toxicity monitoring [12, 34].

The first generation microfluidic biochips designed for simple biochemical assays were based on the principle of continuous liquid flow through permanently-etched microchannels [31, 33]. The second generation paradigm, referred to as digital microfluidics, manipulates liquids as discrete nanoliter droplets of integral volume units [2, 19]. Digital microfluidics-based biochips consist of arrangement of identical basic cells, having individual control such that movement of each droplet (or groups of droplets) can be electronically controlled individually. Biochips typically deploy a two-dimensional array arrangement of cells as shown in Fig. 1. These biochips offer dynamic reconfigurability and architectural scalability and can be used for running several different types of applications e.g., mixture preparation [1, 32]. In fact, different applications may be distributed in both space (e.g., multiplexed assays) and time (e.g., sequence of different experiments). Various chemical and biological applications of digital microfluidics-based biochips have been demonstrated in the literature [8].

Fig. 1
figure 1

Dynamically reconfigurable digital microfluidics-based biochip

Full size image

With the advancement of technology, digital microfluidics-based biochips are becoming more and more sophisticated. Several types of manufacturing defects are likely to crop up in such a complex chip. Moreover, other physical defects may also arise during field operations [14, 31, 38]. As these biochips are often used for life-critical applications, devising effective testing methodologies to test these devices after manufacture and during bioassay operations is very much needed. Prior works [1] in this area can broadly be classified into structural testing and functional testing. Structural testing targets detection of physical defects, whereas functional testing aims at identifying the presence of malfunctioning microfluidic functional modules.

A short-circuit between two adjacent electrodes in a microfluidic array that may occur at the time of fabrication, has been shown to be the most common defect in the literature [27, 28]. The effect of electrode short defects on droplet motion depends on the orientation of liquid flow. The test procedure should therefore focus on pairs of cells and the traversal of test droplets from one cell to all its neighbors. Testing may be performed for checking droplet movement between every adjacent (under 4-neighborhood) pairs of electrodes in unidirectional (structural or unidirectional routing test), or in bidirectional (full routing, applicable in functional testing) fashion. Such problems of optimal navigation of test droplets can be formulated in terms of the Euler cycle or Euler path problems in an undirected or in a directed graph respectively, representing the electrode adjacency structure [31, 37].

Most of the prior works [1] in this area had considered the testing problem in a full microfluidic array (having a regular 2D-array like layout). However, in many cases, application-specific biochips are fabricated, or a significant percentage of total cells in an M ×N microfluidic array may be permanently disabled or removed resulting in an irregular chip layout [36]. For example, in the 7 ×7 microfluidic array shown in Fig. 1, which is configured for a particular bioassay, a small percentage of the total number of cells (shown in gray shade) is used for the assay. If unused electrodes are disabled, this can be treated as an Application Specific Integrated Circuit (ASIC) biochip. Sista et al. [23] reported the design of several ASIC chips for point of care testing. The collection of the primary electrodes in a defect-tolerant hexagonal microfluidic array with redundant spare electrodes [1], may be considered to have formed an incomplete array, akin to an ASIC. Hence, the Eulerization procedure designed for a regular-geometry complete M ×N microfluidic array is not directly applicable for an ASIC biochip. As a result, eulerizing it by adding extra dummy edges and optimal test planning may not be as straightforward as those in the graph model of a full M ×N microfluidic array. Recent works on irregular-geometry biochip layouts such as ASICs or special types such as pin-constrained biochips have focused on synthesis or implementation of design-for-testability solutions [13]. Devising an efficient Euler tour-based testing methodology is desirable to minimize test time and electrode degradation during structural testing.

Droplet routing test plays an important role in functional testing of a digital microfluidic biochip [37]. To perform (bidirectional) routing test, test droplet(s) should cross the cell boundaries between each pair of adjacent cells (under 4-neighborhood) in both directions. We show that the cycle decomposition based methodology proposed here can easily be adopted to provide more efficient solution to the bidirectional routing test problem as compared to an earlier work [37].

The main contributions of this paper can be summarized as follows:

  • We first propose a generalized technique for eulerizing the underlying undirected graph representing the electrode geometry, followed by a cycle based procedure to compute an Euler tour in the eulerized graph to obtain the optimal route plan for the test droplet for conducting structural test (i.e., unidirectional droplet routing test). The salient features of this procedure are as follows:

  • The technique has been shown to be applicable to various existing and emerging biochip architectures, such as fully reconfigurable microfluidic arrays, ASIC microfluidic biochips, defect-tolerant biochips, and to pin-constrained irregular-geometry biochips.

  • It is simple to implement, and does not need bridge checking or any probabilistic technique to speed it up as used earlier [1, 31].

  • The determination of Euler tour in a fully reconfigurable M ×N array can be treated as a special case and can be done in a straightforward manner.

  • The proposed cycle decomposition method allows us to run the structural test procedure in several phases.

  • Finally, we show how, instead of applying two iterations of Euler tour-based structural test as considered in an earlier work [37], the proposed cycle-decomposition technique can easily be adopted to provide more efficient solution to the bidirectional routing test problem.

The rest of this paper is organized as follows. Section 2 reviews prior work in the related area. Section 3 presents the techniques for structural testing. In Section 4, we discuss how the proposed technique can be adopted for bidirectional routing test. Finally, conclusions are drawn in Section 5.

2 Related Prior Work

An easy to implement testing methodology for digital microfluidic biochips was proposed first by Su et al. [27]. The faults in a biochip are classified as catastrophic or parametric [28]. Test droplets are driven through one end of each row and column of the array and are observed at the other end. In many cases, concurrent testing is necessary to ensure system’s availability, particularly for safety-critical applications [18, 29]. Moreover, some physical defects may occur during in-field operation. An effort was also made for test planning and test resource optimization [30]. In all off-line and concurrent testing procedures considered earlier, the goal was to visit all the cells in an microfluidic array using one or more test droplets. Accordingly, the testing problem was formulated as a Hamiltonian path problem on an undirected graph model of the microfluidic array.

Su et al. [31] demonstrated with the help of laboratory experiments, that the effect of electrode short defects on droplet motion depends on the orientation of liquid flow. The test procedure should therefore focus on pairs of cells and the traversal of droplets from one cell to all its neighbors also. Consequently, the structural test problem was formulated in terms of the Euler tour and Euler path problems in an undirected graph. A suitable technique was adopted first to eulerize the graph model of a microfluidic array, and then Fleury’s algorithm was invoked to find an Euler cycle on the eulerized graph. To avoid high computation cost involved in iterative connectivity checking during search for an Euler tour, Fleury’s algorithm was modified by replacing bridge-checking with a probabilistic search procedure based on some rules [1, 31]. Though rule-based search is scalable to large problems, it cannot guarantee the identification of an Euler tour in one run and, may need several simulation runs. A design-for-testability scheme was introduced to tackle the testability problem in ASIC type and pin-constrained digital microfluidic biochips [36]. However, to the best of our knowledge, no work targeting Euler tour-based testing of ASIC type of digital microfluidic biochips, has appeared in the literature.

Structural testing targets the detection of physical defects, but it does not guarantee robust execution of target bioassays or the integrity of assay outcomes. Functional testing of digital microfluidic biochip is needed to detect fluidic malfunctions and thereby ensures whether or not the elementary fluidic operations are reliably executed on the biochip [37]. Bidirectional routing test plays an important role in functional testing of a digital microfluidic biochip [16]. It not only captures physical defects such as electrode shorts, but also checks each electrode’s ability to transport droplets.The problem can be formulated as that of determining an Euler tour in a directed graph model of the microfluidic array (which can be derived by replacing every edge in the undirected graph model with two directed edges in opposite directions). In an earlier work [37], routing test was carried out by applying two iterations of Euler tour-based unidirectional structural test in opposite directions. The technique is unable to find an optimal solution as it starts from the undirected graph model of the microfluidic array, which is inherently non-eulerian in nature.

3 Generalized Method for Cycle-based Euler Tour Identification

As demonstrated in several earlier works [1, 31], to test a digital microfluidics-based biochip for any catastrophic fault, a test droplet should start from the dispensing port and after visiting all the cells and the cell boundaries in the microfluidic array, should reach the droplet sink. The pass/fail decision is made by detecting the presence/absence of test droplet through a capacitive sensing circuit [1]. In order to minimize the test cost the total tour length should therefore be minimum. A microfluidic array is modeled as an undirected graph G = (V, E), where the set of vertices V represents the set of microfluidic cells in the array, and an edge {u, v} ∈ E represents that the microfluidic cells representing u and v are directly adjacent (under 4-neighborhood assumption) in the array. Figure 2a and b show the graph model for a 5 ×5 microfluidic array and an ASIC biochip respectively.

Fig. 2
figure 2

Graph model for a a 5 × 5 microfluidic array and b an ASIC biochip

Full size image

On this graph model, test planning problem for digital microfluidics-based biochip can be formulated as follows: starting from any given node in the graph (representing test droplet dispensing port) the test droplet should reach another given node (representing test droplet sink) in the graph after visiting all the edges of the graph exactly once so as to minimize the total path length traversed by the droplet. Accordingly, the test planning problem to be formulated as Euler path and Euler tour problems. An Euler path in a graph G is defined as a path (directed path in case of a digraph) that traverses all the edges of G exactly once [5]. Similarly, a cycle that traverses all the edges of the graph exactly once is defined as an Euler tour. A graph in which an Euler tour is present, is called Eulerian. A connected undirected graph has an Euler tour if and only if all the vertices of the graph are of even degree [5]. A connected undirected graph has an Euler path if and only if it has exactly two vertices of odd degree. The Euler path must start at one of the odd-degree vertices and must end at the other odd-degree vertex [5]. Finding an Euler tour is more useful as it helps to reduce the test hardware area overhead and the cost of manual maintenance, by merging test droplet source and sink [31].

It is to be noted that the graph model of an M ×N microfluidic array has more than two vertices of odd degree for M ≥ 3, N ≥ 3. Moreover, the graph model of an ASIC biochip may not also be eulerian since one or more vertices in the graph might have odd degree. So before finding an Euler tour in the graph model of microfluidic array, the graph must be eulerized by adding additional edges as required. An additional edge must satisfy an adjacency constraint i.e., it can be introduced only between two nodes representing two neighboring cells, because a droplet can only be transported to only one of its 4-neighbors. Addition of extra edges implies that we have to retrace some of the cell-boundaries in order to traverse all the cell boundaries at least once.

3.1 Eulerization Technique

The undirected graph model of an M ×N microfluidic array can be eulerized by introducing additional edges between some pairs of adjacent boundary vertices as demonstrated in [31]. The graph model of an ASIC biochip, however, may not have a regular structure as that of an M ×N array. As a result, eulerizing it by adding extra dummy edges for optimizing test cost may not be as straightforward as eulerizing the graph model of the M ×N microfluidic array, because the geometric positions of the odd-degree nodes may be random in nature. Figure 3a shows a typical ASIC biochip with cells having odd number of neighbors labeled with O 1, O 2, ⋯ O 6. However, we know that the number of odd degree vertices in any graph is even [5]. Thus, the odd degree vertices can be paired (i.e., matched) to form extra edges such that all vertices will have even degree. Given a graph G = (V,E), a matching M in G is a set of pairwise non-adjacent edges; that is, no two edges share a common vertex [5]. A vertex is matched if it is incident to an edge in the matching. Otherwise the vertex is unmatched. It should be noted that the addition of extra edges between a non-adjacent vertex pair is not as simple as the addition of extra edges between an adjacent vertex pair. An extra edge connecting two non-adjacent vertex (i,j) in the underlying graph represents a sequence of edges, each between two adjacent vertices, forming a path with end points at i and j. The method is illustrated in Fig. 3b on the non adjacent odd degree vertices O 2, O 3 in the graph version of the ASIC microfluidic array shown in Fig. 3a. It is apparent from the figure that the degree of the the intermediate vertices remain even since their degree is increased by two. Only the degrees of i,j are changed from odd to even in the process. The addition of extra edges implies that the test droplet has to retrace the corresponding cell boundaries in the biochip under testing.

Fig. 3
figure 3

a An ASIC biochip with rectangular electrodes. b Addition of extra edges between a non adjacent vertex pair shown with dotted edges on the grid embedding of its underlying neighborhood graph model (shown with continuous edges). c Eulerized version

Full size image

To minimize the testing time, the Euler tour should be made as short as possible. In other words, we must try to eulerize the graph by adding minimum number of parallel edges between two adjacent vertices. Thus, the odd degree vertices should be paired such that the total number of extra edges required is minimized. In a general graph, this problem can be abstracted as the classical Chinese postman problem [7]. In order to achieve this, instead of finding arbitrary matching between odd degree vertices in the graph model of the ASIC microfluidic array, we proceed as follows. We first, construct a weighted undirected complete graph CG O with the odd degree vertices of the ASIC microfluidic array as nodes. The weight w(i,j) of an edge denotes the minimum number of simple edges required to reach j from i in the ASIC microfluidic array i.e., the shortest Manhattan distance between i and j on the grid embedding of its neighborhood graph. Next, we find a minimum-weight perfect matching in CG O . A perfect matching is a matching, which matches all vertices of the graph, i.e., every vertex of the graph is incident to exactly one edge of the matching. In an weighted graph, minimum matching often refers to minimum-weight perfect matching, defined as a perfect matching where the sum of the weights of the edges in the matching is minimized [5]. This matching is then used to eulerize the graph model of the ASIC microfluidic array by adding extra edges, which guarantees Eulerization with the minimum possible extra edges. Figure 4a shows the graph CG O constructed for the odd degree vertices in the graph model of the ASIC microfluidic array shown in Fig. 3b. A minimum-weight perfect matching in CG O [(O 1, O 2), (O 3, O 4), (O 5, O 6)] is shown in Fig. 4b. The matching is then used to eulerize the graph of Fig. 3b, as shown in Fig. 3c. This minimizes the length of the Euler tour. The number of extra edges introduced between O 1 and O 2 is 6. Similarly, the number of extra edges introduced between O 3, O 4 and O 5, O 6 are 2 and 1 respectively. Hence the length of the Euler tour becomes 30. The number of extra edges and the length of the Euler tour would have gone up to 25 and 46 respectively, if a random matching like [(O 1, O 6), (O 2, O 5), (O 3, O 4)], was used. This eulerizing technique is applicable to various biochip architectures having regular or irregular layout.

Fig. 4
figure 4

a Weighted complete graph CG O for the ASIC of Fig. 3. b Minimum-weight perfect matching of total cost 9

Full size image

In general, minimum matching problem is NP-hard [10]. However, in this special case, where the underlying graph is complete and hence admits a perfect matching, this exact optimization problem can be solved in polynomial time. One of the fundamental methods for computing minimum-weight perfect matching is the blossom algorithm proposed by Edmonds [6]. A straightforward implementation of Edmond’s algorithm can run in time bounded by O(n 2 m), where n and m are the number of nodes and the number of edges in the graph, respectively [3]. The efficiency of the algorithm in terms of bounds on its worst-case running time has improved over the past 40 years. One such improvement achieves the bound O(n(m + n logn)) [9]. For an ASIC embedded on a uniform grid, since the edge weights are integers, even lower bounds are possible. A summary of these complexity results appear in the paper by Cook and Rohe [3].

3.1.1 Eulerizing a Fully Reconfigurable M ×N Microfluidic Array

Although the above eulerizing technique can be applied to any biochip architecture, for the special case of an M ×N microfluidic array, a straightforward technique [31] can be used by exploiting the regularity of the structure. It is observed that the minimum number of additional edges N a required to eulerize an M ×N microfluidic array (such that an Euler tour exists in the corresponding graph) satisfying the adjacency constraint, is given by [1, 31]:

$$ N_a = \left\{ \begin{array}{@{}l@{\quad}l} M+N-4, & \text{if} M \text{and} N \text{are even;}\\ M+N-2,& \text{otherwise}. \end{array} \right. $$
(1)

Since the graph corresponding to an M ×N microfluidic array has exactly 2(M + N − 4) odd-degree vertices, the minimum number of edges required to eulerize the graph appears to be M + N − 4. In an ordinary graph, this number is sufficient since an additional edge can be inserted between any two vertices. But for a microfluidic array, an additional edge becomes meaningful only if it is inserted between two directly adjacent cells. Thus, Eulerization with (M + N − 4) edges is clearly evident only when both M and N are even, because on each of the four boundaries of the chip, there exists an even number of degree 3 nodes, and every adjacent pair of them can be matched with an additional edge. The proof therein [1, 31] does not clearly state why, in the second case (i.e., when either M or N or both are odd), exactly another two additional edges are necessary. We present here a complete proof of the theorem. This is based on the following observation: the size of any random cut in an Euler graph is always even, where a cut is a partition of the vertices of the graph into two disjoint subsets. The size of a cut is the number of edges crossing the cut.

It is easy to see that the graph model of M ×N microfluidic array does not satisfy the above property. For example, the number of edges cut by each of the four cuts shown in the Fig. 5a is odd. As mentioned earlier, when both M and N are even, proof of necessity is trivial, since it is impossible to eliminate 2(M + N − 4) odd-degree vertices with less than M + N − 4 extra edges. The necessity of eight extra edges to eulerize the graph model of a 5 ×5 microfluidic array can be verified by the eight cuts shown in Fig. 5b. Each cut dictates the requirement of at-least one extra edge following the observation stated above and there is exactly one extra edge for each of them. Similarly, the necessity of seven extra edges to eulerize the graph model of 5 ×4 microfluidic array can be verified by the seven cuts shown in Fig. 5c. Generalizing this argument, it follows that exactly M + N − 2 additional edges are necessary and sufficient for eulerizing the graph model of an M ×N microfluidic array, when at-least one of M or N is odd.

Fig. 5
figure 5

Cuts showing the necessity of additional edges for ensuring the existence of Euler tour

Full size image

3.1.2 Eulerizing Defect-Tolerant Biochips with Hexagonal Electrodes

Interstitial space redundancy has emerged as a useful technique in the design of fault-tolerant biochips [1]. A defect-tolerant design for a digital microfluidic biochip, denoted by DTMB(s,k), has interstitial spare cells such that each non-boundary primary cell can be replaced by any one of s spare cells, and each spare cell can be used to replace any one of k primary cells. A DTMB(3,6) design with hexagonal electrodes is shown in Fig. 6a. To detect any faulty primary cell of such defect-tolerant biochip through unidirectional structural testing, only primary cells and the associated boundaries have to be considered. In other words, an Euler tour on the underlying subgraph induced by the primary cells of the biochip has to be determined. Figure 6b shows the underlying subgraph induced by the primary cells in a DTMB(3,6) chip. As apparent from the figure, this subgraph is not eulerian, since there are several nodes with odd degree. The approach described above for eulerizing an ASIC microfluidic biochip can readily be applied to eulerize such a graph. Figure 6c shows an optimally eulerized version thus obtained. The dotted lines in the figure represent the extra edges.

Fig. 6
figure 6

a A DTMB(3,6) design with hexagonal electrodes. b The underlying subgraph induced by the primary cells. c Its optimally eulerized version

Full size image

3.1.3 Eulerizing a Real-Life Pin-Constrained Irregular Microfluidic Array

The number of independent control pins in a biochip is an important cost factor from the fabrication point of view. In order to facilitate manufacturing of low-cost and disposable biochips, pin-count reduction has emerged as a key design consideration for practical applications of digital microfluidic biochips [13, 21]. Depending on applications, pin-constrained designs can be adopted for various biochip architectures including those with regular or irregular geometry. The procedure based on Chinese postman problem, can be used for test planning in all pin-constrained designs as well. An example of irregular pin-constrained architecture is shown in Fig. 7a, which implements a 3-plex assay for measurement of troponin-I, myoglobin, and creatine-kinase-MB (CK-MB), in human physiological fluid (serum). We assume that the rightmost electrode of each of the reactor chains acts as a dispenser. To reduce the number of control pins, the layout uses a bus-based pin-constrained design [39]. The electrodes with the same label (1, 2, 3, ⋯ , a, b, ⋯ ) share the same control pin. Though the 3-plex assay is a shared-pin design, a single droplet can always be transported to any one of its 4-neighbors without any violation of fluidic constraints. Since, the design has only one waste reservoir and several dispensers, for structural testing, finding an Euler path from one node representing a dispenser to the node representing the waste reservoir in the underlying graph would be an appropriate choice. It may be noted that for identification of an Euler path, during eulerizing (termed as semi-eulerizing) the underlying graph, the degrees of source and destination nodes should not be made even. Hence, nodes D 3 and R were excluded while constructing the weighted complete graph for minimum-weight perfect matching. Figure 7b shows the semi-eulerized version of the graph with total cost 143, computed by the proposed procedure. The number of extra edges is 22 (18%).

Fig. 7
figure 7

a 3-plex assay. b Semi-eulerized version of the underlying graph

Full size image

It is apparent that the length of the optimal Euler-tour/Euler-path and consequently testing time varies with the size and architecture of the biochip, since the number of additional edges required for Eulerization depends on the structure of the biochip. Table 1 shows the length of the optimal Euler-tour/Euler-path for biochips with different architectures considered in this subsection.

Table 1 Length of the Euler-tour/Euler-path for biochips of different architectures
Full size table

3.2 Cycle-based Euler Tour Identification

Once the underlying graph is eulerized, the next task is to find an optimal Euler tour. In an earlier work [1, 31], a modified version of the Fleury’s algorithm, based on a probabilistic search procedure, was used. Here, we use a classical method proposed by Hierholzer in the year 1873 [11], which is based on disjoint cycle (closed trail) decomposition. Hierholzer’s algorithm runs in O(m), where m is the number of edges in the eulerian graph, and offers several advantages: (i) it is easy to implement, (ii) it alleviates the need for probabilistic bridge checking, and (iii) it partitions the set of all edges of the underlying graph into edge-disjoint cycles on the fly, which are useful in phase-based testing that reduces test application time.

Hierholzer’s Algorithm

Input: a connected Euler graph G

Output: an Euler tour T

           Start at any vertex v, and construct a closed trail

                  (cycle) T in G.

           While there are edges of G not already in trail T

                  Choose any vertex w in T that is incident on

                            an unused edge.

                  Starting at vertex w, construct a closed trail D

                            of unused edges.

                  Enlarge trail T by splicing trail D into T at

                            vertex w.

           Return T.

Hierholzer’s algorithm can be implemented efficiently by adopting a depth-first search (DFS) technique [4]. The correctness of the algorithm follows from the fact that a connected graph is an Euler graph if and only if it can be decomposed into cycles, i.e., its set of edges can be partitioned into edge-disjoint cycles (closed trails) [5]. Further, when two cycles intersect, they must share an even number of nodes. It may be noted that the existence of w is guaranteed by the assumption that, G is connected and all its nodes are of even degree (and T has only used up an even number of edges which are incident on w). Let us illustrate the technique on the graph model shown in Fig. 8a. Starting from the vertex N 1, we construct a closed trail (T) as N 1 →N 2 → N 3 → N 9 → N 10 → N 11 → N 12 → N 21 → N 1 (denoted by cycle 1 in the figure). Next, we choose the vertex N 3 as w and construct another closed trail (D) as N 3 → N 4 → N 9 → N 12 → N 13 → N 17 → N 19 → N 20 → N 21 → N 3 (denoted by cycle 2 in the figure). Then we splice D into T at node N 3 to enlarge T as follows: N 1 → N 2 → N 3 → N 4 → N 9 → N 12 → N 13 → N 17 → N 19 → N 20 → N 21 → N 3 → N 9 → N 10 → N 11 → N 12 → N 21 → N 1. In this way we continue until all the edges are included in T. The complete process can be depicted as a depth-first traversal of the graph as shown in Fig. 8b, where the solid (dotted) directed edges represent the forward (back) edges.

Fig. 8
figure 8

Illustration of Euler tour identification using Hierholzer’s algorithm

Full size image

3.2.1 Special Case of M ×N Microfluidic Array

It is known that the edges of an Euler graph is decomposable into edge-disjoint cycles, and an Euler tour in the graph can be found by merging (splicing) the edge disjoint cycles [4]. The above procedure based on Hierholzer’s algorithm works by identifying such edge-disjoint cycles one by one and merging them appropriately. If somehow these cycles can be identified a priori, the task of determining Euler tour becomes easier. We show below, such decomposition in the eulerized version of a graph model of the M ×N microfluidic array is very simple due to the regular structure of the graph. Moreover, the splicing becomes straightforward since the structures of the identified cycles are also regular. We present how the eulerized version of the graph model of an M ×N microfluidic array can be decomposed into cycles considering the three possible cases individually.

(i) M, N both are even, (ii) M, N both are odd, (iii) only one of M, N is odd and the other is even.

Figure 9a–c show the cycles into which eulerized version of an 6 ×6 microfluidic array can be decomposed. The graph can be decomposed into five cycles; the one comprising of all the boundary edges, shown in Fig. 9a and denoted by \(C_1^1\), two horizontal cycles, shown in Fig. 9b and denoted by \(C_1^2\) and \(C_2^2\) respectively, two vertical cycles, shown in Fig. 9c and denoted by \(C_1^3\) and \(C_2^3\). In general, the graph corresponding to an M ×N microfluidic array, where both M and N are even, can be decomposed into \(\{\frac{(M-2)}{2}+\frac{(N-2)}{2}+1\}\) cycles. These cycles can be classified into three categories: the first category consists of one cycle comprising of boundary edges, the second category consists of \(\frac{1}{2}(M-2)\) horizontal cycles, and the third category consists of \(\frac{1}{2}(N-2)\) vertical cycles. For example, the cycles shown in Fig. 9 are categorized as follows: \(C_1^1\) belongs to the first category, \(C_1^2\) and \(C_2^2\) belong to the second category, and \(C_1^3\) and \(C_2^3\) belong to the third category.

Fig. 9
figure 9

Cycle decomposition in the graph model of a 6 ×6 array

Full size image

When both M and N are odd, the eulerized version of an M ×N microfluidic array can be decomposed into two cycles, irrespective of the value of M and N. One cycle comprising of only boundary edges and the other comprising of the remaining edges. Figure 10 shows the cycle decomposition in the eulerized version of a 5 ×5 microfluidic array. The cycle comprising of the boundary edges, denoted by \(C_1^1\), is shown in Fig. 10a and the other cycle, denoted by \(C_1^2\), is shown in Fig. 10b.

Fig. 10
figure 10

Cycle decomposition in the graph model of a 5 ×5 array

Full size image

Finally, let us consider the case where one of M, N is odd and the other is even. When M is odd and N is even, such a graph can be decomposed into \(\{\frac{(M-3)}{2}+2\}\) cycles; one consisting of only boundary edges, one complex cycle, and \(\frac{(M-3)}{2}\) horizontal cycles. Similarly, the graph can be decomposed into \(\{\frac{(N-3)}{2}+2\}\) cycles; one consisting of only boundary edges, one complex cycle, and \(\frac{(N-3)}{2}\) vertical cycles, when N is odd and M is even.

Figure 11a–c show the cycle decomposition in the eulerized version of a 7 ×6 microfluidic array.

Fig. 11
figure 11

Cycle decomposition in the graph model of a 7 ×6 array

Full size image

The technique of determining Euler path/tour proposed here is a two-step process viz, (i) properly Semi-eulerizing/Eulerizing the underlying graph, and (ii) identification of Euler path/tour on the Semi-eulerized or Eulerized version respectively. Again, the task of identifying an Euler tour using cycle based technique can be divided into two subtasks viz, (i) decomposing the graph into edge-disjoint cycles and (ii) merging or splicing these cycles. For different biochip architectures, the overall procedure is summarized in Table 2.

Table 2 Proposed strategy for various biochip architectures
Full size table

3.3 Phase-based Testing

It is apparent that Hierholzer’s algorithm can be slightly modified to keep the additional information about the individual edge-disjoint cycles comprising the Euler tour. This property (which is not available in Fleury’s algorithm based Euler tour computation) can be used to adopt the test procedure that may lead to savings in test time in case of a simple pass/fail based phase-wise structural testing. The idea is as follows. The edge-disjoint cycles identified by Hierholzer’s method are recorded and then sorted according to the increasing order of their lengths: C 1, C 2, ⋯ , C k . During test application, instead of considering the entire Euler tour, the entire test procedure is divided into k phases, where each phase corresponds to the traversal of the test droplet along an edge-disjoint cycle. Phase 1 corresponds to the cycle C 1, phase 2 corresponds to the cycle C 2 and so on. At the beginning of a phase, test droplet is routed from the source reservoir to the nearest node incident on the corresponding cycle (which may be considered as the pseudosource/sink). Similarly, after the completion of the traversal along the cycle, the test droplet is routed back to the nearest sink reservoir. The test procedure starts with cycle C 1 (phase 1), and continues through the other phases considering cycles C 2, C 3, ⋯ , C k iteratively one after another. Test application stops as soon as the biochip fails to pass any phase, without executing other phases. The test droplet need not have to traverse entire Euler tour to detect a fault. The early termination of test application may lead to significant savings in testing time. In this way, this approach wins over the conventional test application (where the entire Euler tour is considered), where pass/fail decision is possible only after the test droplet completes the traversal along the entire Euler tour. For example, let us consider the test application on the microfluidic array shown in Fig. 12a. We also consider that the top left cell N 11 acts as the source/sink reservoir. The five cycles identified by the proposed procedure, in the eulerized version of the corresponding graph model, are shown in Fig. 12b. Suppose an electrode short defect exists along the cell boundary (N 33, N 34). This defect can be detected after the execution of phase 2 if the test procedure described above is applied, since the corresponding edge is incident on cycle C 2. The test application time required to detect this defect is 28 time frames, where a time frame represents the time taken by the droplet to move from one cell to an adjacent cell. This includes the extra time required for routing the test droplet between the respective pseudosource/pseudosink of cycles C 1 and C 2 and the original source/sink reservoir (N 11). If the conventional test procedure is applied, the minimum test application time required to detect the same defect would have been equal to 68 time frames, since the length of the total Euler tour is 68. Table 3 shows the savings statistics in detail considering different positions of the fault site. It is apparent that in most of the cases, we have significant savings in testing time. However, if the fault site is located in the last cycle, the proposed test procedure shows poor performance than the conventional one, as indicated by the negative entry under the last column of the last row in the table. The savings in testing time is achieved as a result of reduced droplet transportation, which in turn, also lessens electrode degradation during testing. The phase-based test application also facilitates diagnosis, as an error detected in a particular phase is indicative of a defect present in the cell boundaries considered in that phase.

Fig. 12
figure 12

Illustration of phase-based testing

Full size image
Table 3 Savings statistics for phase-based test droplet routing
Full size table

4 Adaptation of the Proposed Technique for Bidirectional Routing Test Procedure

As mentioned in Section 1, routing test plays an important role in functional testing of a digital microfluidic biochip. To perform bidirectional routing test, test droplet(s) should cross the cell boundaries between each pair of adjacent cells (under 4-neighborhood) in both directions. As a result, routing test problem can be formulated as to find the Euler tour in the directed graph model of the microfluidic array. Euler tour in a directed graph is defined as a directed cycle that traverses all the edges of the graph exactly once. A connected directed graph is eulerian if every vertex of the graph has equal in-degree and out-degree [5]. Directed graph model of a microfluidic biochip (fully reconfigurable M ×N array, or ASIC chips, or hexagonal layouts) can be derived by placing two directed edges in opposite directions between the two nodes representing two adjacent cells. Therefore, the underlying directed graph of a biochip for a fully reconfigurable M ×N microfluidic array, an ASIC chip, or for a hexagonal geometry, is inherently eulerian. Thus, there is no need of eulerizing them by adding extra edges. Hence, Euler tour in these directed graph can be computed by the generalized method for Euler tour identification as described in Section 3.2. Moreover, like structural testing of fully reconfigurable M ×N microfluidic array, straightforward implementation of cycle based technique can be adopted to obtain more efficient routing test procedure. One possible implementation has been illustrated on the digraph of a 5 ×5 microfluidic array in Fig. 13b. The edges are numbered in the order they are traversed to compute the Euler tour starting from the top-left node.

Fig. 13
figure 13

Routing test procedure: a with two passes on the undirected eulerized graph [37]; b proposed unified and optimal Euler tour on the digraph based on cycle decomposition

Full size image

In an earlier work [37], routing test was carried out by applying two iterations of Euler tour-based structural test in opposite directions. Apart from the problem incurred by rule-based probabilistic search procedure, it has other disadvantages. The undirected graph model of the microfluidic array, which is inherently non-eulerian in nature, has to be eulerized by adding some extra edges. The physical significance of an extra (parallel) edge is that a test droplet has to cross this edge twice during the tour. For example, the extra edges required in a 5 ×5 array are shown in Fig. 13a as dotted lines. However, the directed graph model of the microfluidic array is already eulerian, and thus it does not need any extra edges. An Euler tour in this directed graph will yield the optimal solution for the bidirectional routing test problem. The minimum length of the bidirectional Euler tour in an N ×N array is 4N 2 − 4N, as the directed graph model of the microfluidic array contains exactly 4N 2 − 4N edges. On the other hand, the length of the bidirectional Euler tour, obtained by two iterations of Euler tour on the undirected graph in opposite directions as proposed by Xu et al. [37], is 4N 2 − 8, when N is even, or 4N 2 − 4, when N is odd. As a result, some savings in the number of manipulation steps for conducting routing test can be achieved by directly finding the optimal Euler tour in the directed graph model. For example, bidirectional routing test of a 5 × 5 microfluidic array can be done in 80 time frames instead of 96 time frames as needed earlier [37], because the traversal through the extra (dotted) edges is not needed. Similar savings can be observed for bidirectional droplet routing test in ASIC and hexagonal electrode based biochips.

5 Conclusion

We have presented an easy-to-implement and unified technique for Euler tour-based structural testing of digital microfluidic biochips. The methodology can be applied to biochips with various architectures, e.g., fully reconfigurable, application specific, pin-constrained irregular geometry, and hexagonal geometry based biochips. The technique is also suitable for phase-based test application that reduces droplet transportation costs significantly and aids early fault detection during structural testing. The proposed methodology for unidirectional structural testing can easily be adopted to expedite the routing test procedure for functional testing of digital microfluidic biochips as well.