Spatial Network Generation Tool for Performance Analysis of Water Distribution Networks - Pattern Recognition for Reliability Assessment of Water Distribution Networks - page 75

In general, the process is conducted by manipulating the elements of the matrix constructed
to satisfy selected boundary conditions. All possibilities will be taken into consideration
initially meaning one sub-graph created for each degree of vertex i.e. each edge that connects
it. For instance, in Table 4.7 on the left, the degree of vertex n1 is three when it is connected
with all the edges in that row. On top of it, sub-graphs can also be produced with vertex
degree one and two. Consequently, the total set of pipe combinations for n1 is: {1, 2, 3,(1,2),
(1,3),(2,3),(1,2,3)}, total seven. This total number can be calculated by Equation 4.4 where n
stands for the maximum number of connected edges to the vertices i.e. nodes.

n

n ! 3 3 3

∑ =

4.4 nCr = = + + = 7

r ! ( n − r )! 1 ( 3 − 1 )! 2 ( 3 − 2 )! 3 ( 3 − 3 )!

r 1

As the matrix table further shows, nodes n2 and n3 have one edge each, with combinations
{5} and {6}, respectively. The total number of combinations for four nodes is therefore
7x1x1 = 7. Finally, the total number of sub-graphs created by subsequently withdrawing
matrix elements will be 49.

4.4.1 Non-Random Generation

Non-random generation will consider all possible combinations of matrix elements. This can
be done by the recursive combination process starting from the last row of the matrix. For the
sub-graph in Figure 4.8/Table 4.7 on the left, the list of all the possibilities will look as in
Table 4.8. The process starts by making a combination of the first column {1,5,6}, then
continues by searching the next element in the last row to replace the last element in this first
combination. In the particular example, that one is not available as well is the case with the
second (last) row. Finally, the successively made combinations are {2,5,6}, {3,5,6},
{1,2,5,6}, {1,3,5,6}, {2,3,5,6} and {1,2,3,5,6}.

Table 4.8 List of combinations for the sub-graph in Figure 4.8 - left

Column 1 Column 2 Column 3 Column 4 Column 5 Column 6 Column 7

Row 1 1 2 3 1,2 1,3 2,3 1,2,3

Row 2 5 - - - - - -

Row 3 6 - - - - - -

The above seven combinations are generated while taking the elements from all three rows.
The same process is to be repeated for the subsets of two rows and one row. After eliminating
combinations with number of edges smaller than n -1, those that would qualify from the
subset of two rows are {1,2,5}, {1,3,5}, {2,3,5}, {1,2,3,5}, {1,2,6}, {1,3,6}, {2,3,6},
{1,2,3,6}, and from one row is only {1,2,3}.

The drawback of the process is that it deals with huge number of possible network layouts,
which grows exponentially with the number of nodes, as illustrated in Figure 4.10. Although
many of these networks will be eliminated during the screening step, the total number of
'acceptable' layouts will still be big, probably too big for any sensible water distribution
analysis, inflicting unnecessarily long computational times.