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

4.3 GRAPH THEORY CONCEPTS USED IN NETWORK GENERATION

ALGORITHM

The network generation tool (NGT) presented in this chapter aims to generate sufficiently
large samples of synthetic networks that resemble water distribution practice. For this
purpose, an algorithm has been developed where links connect a set of reservoirs, tanks,
and/or nodes prepared initially in EPANET, with spatial and topographic characteristics ( x , y
and z coordinates), as well as the initial nodal demands, of users' choice. To enhance the
process and avoid configurations that are not typical in reality, the following four principles
have been built into the algorithm: (1) to respect the maximum defined number of nodal
connections, (2) to give priority to the closest available node for connection, (3) to avoid
crossings between pipes (without connecting them), and (4) to avoid pipe duplication that
could occur by connecting the same nodes in reversed order. These principles have
implications on the way the graph matrices are manipulated during the programme execution.
For the sake of consistency, the generated networks are exclusively simple graphs i.e. do not
have parallel pipes; those should be added manually afterwards, if necessary.

An example of graph/network and its corresponding matrix is shown in Figure 4.7 and Table
4.5, respectively.

From node To node

n1 n2 n3 n4

n1 0 1 2 3

n2 1 0 4 5

n3 2 4 0 6

n4 3 5 6 0

Figure 4.7/Table 4.5 Matrix representation of a graph

Not containing self-connected nodes, the diagonal of the matrix will be filled with zero
values, splitting it into two symmetrical parts. The upper triangular matrix and lower
triangular matrix are created, as shown in Table 4.6, each of them sufficiently describing the
network connectivity and reducing the original matrix to a simpler form.

Table 4.6 Upper triangular matrix (left) and lower triangular matrix (right)

From node To node From node To node

n1 n2 n3 n4 n1 n2 n3 n4

n1 0 1 2 3 n1 0

n2 0 4 5 n2 1 0

n3 0 6 n3 2 4 0

n4 0 n4 3 5 6 0