Effect of graph generation on slope stability analysis based on graph theory

Enpu Li,Xioying Zhung,*,Weno Zheng,Yongchng Ci

aState Key Laboratory for Disaster Reduction in Civil Engineering,Department of Geotechnical Engineering,College of Civil Engineering,Tongji University, Shanghai,200092,China

bSchool of Engineering,University of British Columbia,Kelowna,V1V 1V7,Canada

Effect of graph generation on slope stability analysis based on graph theory

Enpu Lia,Xiaoying Zhuanga,*,Wenbo Zhengb,Yongchang Caia

aState Key Laboratory for Disaster Reduction in Civil Engineering,Department of Geotechnical Engineering,College of Civil Engineering,Tongji University, Shanghai,200092,China

bSchool of Engineering,University of British Columbia,Kelowna,V1V 1V7,Canada

A R T I C L EI N F O

Article history:

Received 30 October 2013

Received in revised form

24 April 2014

Accepted 12 May 2014

Available online 24 June 2014

Graph theory

Limit equilibrium method(LEM)and strength reduction method(SRM)are the most widely used methods for slope stability analysis.However,it can be noted that they both have some limitations in practical application.In the LEM,the constitutive model cannot be considered and many assumptions are needed between slices of soil/rock.The SRM requires iterative calculations and does not give the slip surface directly.A method for slope stability analysis based on the graph theory is recently developed to directly calculate the minimum safety factor and potential critical slip surface according to the stress results of numerical simulation.The method is based on current stress state and can overcome the disadvantages mentioned above in the two traditional methods.The inf l uences of edge generation and mesh geometry on the position of slip surface and the safety factor of slope are studied,in which a new method for edge generation is proposed,and reasonable mesh size is suggested.The results of benchmark examples and a rock slope show good accuracy and eff i ciency of the presented method.

©2014 Institute of Rock and Soil Mechanics,Chinese Academy of Sciences.Production and hosting by Elsevier B.V.All rights reserved.

1.Introduction

Graph theory is an important branch of combinatorial mathematics.The theory originated from the Koenigsberg bridge problem,and the mathematician Euler used the theory to address this problem.After hundreds years of development,the graph theory has been used to solve the problems of the shortest path,network fl ow,dynamic planning,etc.It has been widely used in engineering fi elds,such as the analysis of drainage pipe network system,the optimal island distribution of smart grid,the train operation plan, and the tourism route optimization(Bondy and Murty,1976;Wang et al.,2011).

The problem of slope stabilityanalysis(Kim and Lee,1997;Farias and Naylor,1998;Sarma and Tan,2006;Zheng et al.,2009;Guo et al.,2011;Xie et al.,2011;Zhou et al.,2011;Shen et al.,2013) can be transformed to the shortest path one in the graph theory. The directed weighted graph is fi rstly constructed by analyzing mesh and vertex information of the model based on numerical calculation of stress fi eld.Then the slip surface and safety factor can be found out by the shortest path algorithm.

There have been many researchers attempting to use the graph theory to analyze the critical slip surface and the safety factor. Cherkassky et al.(1993)and Xu et al.(2007)studied the slip surface and the safety factor using the Dijkstra algorithm on the basis of fi nite element results.Zhou et al.(2008)used the graph theory to evaluate the stability of slope under the condition of rainfall in fi ltration.Zhuang et al.(2008)developed the meshless graph theory method.Bellman(1957)developed the Bellman-Ford algorithm to search for the critical slip surface of jointed rock.Fang(2007) extended the graph theory to the three-dimensional slope stability analysis,and preliminarily applied it to tunnel slope stability analysis.These methods are based on the current stress state,and can overcome the disadvantages of the conventional limit equilibrium method(LEM)which cannot consider the constitutive relation of rock/soil mass.In comparison,the strength reduction method(SRM)requires iterative calculations and cannot directly locate the slip surface(Zheng et al.,2005).It is a computationally desirable method for slope stability analysis.

The critical slip surface corresponds to the minimum safety factor of slope comprising the edges and vertices of the graph.In this approach,type of edge generation,mesh geometry and mesh density will inf l uence the results of slope stability analysis.Unreasonable distribution of vertices and edges will give erroneous slip surface and safety factor.This issue has not been mentioned in the previous work.For example,in the work of Zhou et al.(2012), only the in fl uences of physical parameters of slope material were discussed based on the graph theory.

On the basis of preliminary work(Zheng et al.,2013),the infl uences of the type of edge generation,mesh geometry and mesh density in the graph theory on the shape of slip surface and the safety factor are investigated in this paper.Practical suggestions are presented on how to use the graph theory for slope stability analysis effectively.The test results of benchmark examples and a rock slope show good ef fi ciency and accuracy of the method.

2.Graph theory and slope stability analysis

The graph is a collection of vertex setV(G)and an edge setE(G) connecting different vertices.A line that connects two vertices is termed as an edge.The graph can be classif i ed into directed graph and undirected graph according to whether an edge has a direction or not.In directed graph,the edge is an unidirectional path,and the pair of nodes connected by each edge is def i ned as a sorted couple belonging to the edge setE(G).An undirected graph can be viewed as a directed graph with edges of bilateral path instead of unidirectional path.

The shortest path problem aims to f i nd the minimum“cost”or“sum of weight”among all possible paths.As shown in Fig.1a,there are seven verticesV0-V6and twelve directed edges,the cost (weight)of each edge is shown on the edge.The shortest path problem is to search for a path that gives the minimum sum of weightfromvertexV0toV6.TheshortestpathisV0→V2→V3→V5→V6as shown in Fig.1b.

The essential of slope stability analysis is to determine the minimum safety factorand the corresponding critical slip surface of slope.Similar to the shortest path problem between two points, determination of the critical slip surface can be converted into searching for“vertices”between starting point and end point of the slope.In this way,the safety factor of slip surface connected by these points is the minimum.

The safety factor is def i ned as the ratio of resistance to sliding force along the slip surface.A weight function is introduced to measure the weight(cost)of each edge when using the graph theory to determine the minimum safety factor.As shown in Fig.2, by assuming the existence of critical slip surfacek,the minimum safety factor of slope can be def i ned as

Fig.1.Sketch of the shortest path problem.

Fig.2.Sketch of critical slip surface.

wherekindicates thekth path andiindicates theith edge comprising thekth path.Note that the summation should not be applied tokbut only toi.

The minimum safety factor of all possible slip surfaces is

Then,we can introduce an auxiliary function as

and therefore the weight of each edge is simply formulated as

The problem of locating the critical slip surface can be converted into searching the corresponding path of the minimumGthrough the above formulas.

When using the FEM for slope stability analysis,the nodes are often used as the vertices in the graph theory,and vertices associated with that nodes are used to generate edges.Edge weights are calculated according to the stress results of the FEM.The tangential and normal forces along the edge can be obtained by averaging the stress at two vertices connected by the edge.In this paper,we use the numerical manifold method for stress analysis,and the vertices and edges in the graph theory follow the same ones as that in FEM without considering joints in the slope.For slope model containing joints,nodes of mathematical meshes and joint elements are used as the vertices in the graph theory.Thus the generation of edges in the graph theory only needs to make some changes in joint place so that the edges of the slope and the weight of edge can be obtained (Zheng et al.,2013).

For the shortest path problem,there are two basic methods, namely Dijkstra algorithm and Bellman-Ford algorithm.Other algorithms are derived on the basis of the above two methods,such as pile optimized Dijkstra algorithm,SPFA algorithm,and Floyd-Warshall algorithm,etc.Dijkstra algorithm is applicable to the shortest path problems without negative weights,while Bellman-Ford algorithm can solve the problems with negative weights.So Bellman-Ford algorithm is used to search for the critical slip surface as the edge weight of slope may be negative.

3.The inf l uence of edge generation

The edge generation has a signif i cant inf l uence on the slope stability analysis.The shortest path searching algorithm can be usedtof i nd a“shortestpath”that makes the minimum safety factorof slope after construction of edges and weights.Different types of edge generation will produce different directions and weights of edges.So an appropriate type of edge generation partly determines the shape of critical slip surface and is a very important issue.

There are two common ways of constructing edges for slope stability analysis.Taking a triangular element for example,the f i rst way is shown in Fig.3,where the vertices correspond to the sets of all nodes of the elements connecting the nodei.The second one is shown in Fig.4,where the vertices collect the sets of nodes at a certain radius of the nodei.The direction of edges is relatively f i xed in the f i rst way.However,the critical slip surface may not appear along these edges.In fact,the properchoice of radiusis also an issue in the second approach.The paper employs a new way of edge generation as shown in Fig.5 where the vertices are the sets of nodes belonging to the elements that connecting the nodei,or nodes of the elements sharing the same edge with the elements connecting the nodei.

Two standard slope examples are tested to verify the inf l uence of the three types of edge generation on the shape of slip surface and safety factor.The f i rst one is the slope stability benchmark example named as EX11(Donald and Giam,1992)of Australian Computer Application Association(ACADS),as shown in Fig.6.The material properties of the homogenous slope areγ=20 kN/m3,c=3 kPa,and φ=19.6°,the slope length and height are 20 m and 10 m,respectively,and the average mesh size is 1.5 m.

The slip surface obtained by the f i rst type of edge generation method(Fig.7)is signif i cantly different from the referenced solution(Fig.8),and the safety factor is 1.6433,about 60%larger than the referenced value(Donald and Giam,1992).

By the second type of edge generation method,the safety factor varies with different searching radii(Fig.9).The slip surface and the safety factor are the same as those by the f i rst type of edge generation method when the searching radius is 2 m(Fig.10a).The number of vertices for construction of edges increases with the searching radius,and the slip surface tends to be more and more exact,and the safety factor converges to the referenced solution. The minimum safety factor is 1.0518 when the searching radius is 3.2 m(Fig.10b).Fig.10c shows the safety factor and slip surface when the searching radius is 3.6 m.

The slip surface obtained by the proposed edge generation method(Fig.11)is similar to the referenced solution,and the safety factor obtained is 1.0518,slightly larger than the LEM solution.It is consistent with the results presented in Dawson et al.(1999).

Fig.3.First type of edge generation.

Fig.4.Second type of edge generation.

Fig.5.The type of edge generation proposed in the paper.

Fig.6.ACADS referenced slope example EX11(Donald and Giam,1992).

Fig.7.Critical slip surface by the f i rst type of edge generation method.

Fig.8.ACADS referenced solution to EX11(Donald and Giam,1992).

Fig.9.Relation between safety factor and searching radius by the second type of edge generation method.

By comparing these three methods,it can be seen that unreasonable slip surface and much larger safety factor are obtained bythe f i rst method.The safety factor and slip surface vary with different searching radiiin the second method,and the safety factor tends to converge when the radius is large enough.However,for non-uniform mesh size,the second method requires varying searching radii crossing different domains(Fig.12).The proposed method appears to be most robust,and the safety factor and slip surface agree well with the referenced solutions.

Fig.10.Critical slip surfaces obtained by the second type of edge generation method under different searching radii.

Fig.11.Critical slip surface obtained by the proposed edge generation method (F=1.0518).

Fig.12.Slope model with varying mesh densities.

Fig.13.Different types of mesh shape.

4.The inf l uence of mesh shape

The mesh quality determines the distribution of vertices and formation of edges,thus inf l uencing the f i nal searching results of the shortest path algorithm.Different types of mesh shape are compared in this section for slope stability analysis.

The meshes used in this study are plotted in Fig.13,and the mesh size is 1.5 m for all types of mesh generation method.Here, the proposed edge generation method is adopted as described in Section 3.The results(Fig.14)show that the shape of slip surface and the safety factor are almost insensitive to the mesh type,and they have limited inf l uence on the slope stability analysis using the graph theory.

5.The inf l uence of mesh density

To balance the eff i ciency and accuracy in the numerical analysis, it is important to choose an appropriate mesh density.In this section,different mesh sizes are adopted and tested for slope stability analysis with the same mesh shape as shown in Fig.6.

Fig.14.Critical slip surfaces obtained by different types of mesh shape.

A nonlinear relationship between the mesh size and calculation time is plotted in Fig.15.It shows that the calculation time significantly decreases with the increase of mesh size.The safety factor almost keeps constant,with slight variation within 1.0-1.05 with respect to the mesh size between 0.5 m and 5 m.Therefore,it can be concluded that the mesh size has minor inf l uence on slope stability in the graph theory.The shape of critical slip surface changes with the varying mesh sizes(Fig.16),and similar slip surface can be obtained with the referenced solution when the mesh size is between 0.5 m and 2 m.The slip surface changes greatly when the mesh size is between 3 m and 5 m.According to experience,the mesh size of 1/10 of the slope height is suggested to obtain a satisfactory result and searching ef fi ciency.

Different mesh sizes are used in different parts of the actual slope model.Local mesh re fi nement is adopted in the keyparts,and sparse mesh in others.Taking the EX11 for example again,the infl uence of different mesh re fi nements on the safety factor is studied.

Mesh re fi nement at slope toe is shown in Fig.17.The slip surface obtained by the graph theory is shown in Fig.18.There is a big turning angle at the top of slope,and the safety factor is 0.9043, which is much more different from the referenced solution.

Mesh re fi nement at slope top is adopted on the basis of above example(Fig.19).The slip surface obtained by the graph theory is shown in Fig.20.The safety factor is 1.0115,similar to the referenced solution.

From the above two examples,it can be seen that mesh density has in fl uences on the slip surface.Reasonable slip surface and safety factor can be obtained by the graph theory when the mesh size is close to 1/10 of the slope height.

Fig.15.Inf l uence of mesh size on safety factor and computation time(F=1.0195).

Fig.16.Critical slip surfaces with different mesh sizes.

Fig.17.Mesh ref i nement at slope toe.

6.Example of a rock slope

In this section,a rock slope in a hydropower station is analyzed with the proposed method.Different from previous benchmark examples,excavations at different steps are involved.

The natural slope is overall in a stable condition.However,the excavation is expected to induce sliding along the weak interlayer. For simplicity,only the main joints are modeled.The model used for the test is shown in Fig.21,the range in horizontal direction is 500 m,and the slope height is 335 m.There is an intersectingstructural plane(g10)in the model which is considered as a governing discontinuity according to geological investigation.The material parameters of the intact rock and the joint are listed in Table 1.

Fig.18.Critical slip surface with mesh ref i nement at slope toe.

The excavation area of the slope is plotted in Fig.21 with four steps in total.The f i rst step is excavated to the height of 1847.5 m above sea level,the second step to the height of 1826.28 m,the third step to the height of 1806.28 m,and the fourth step to the height of 1776 m(Fig.22).

The slip surface and safety factor after each step of excavation are plotted in Fig.23.The shapes of slip surfaces are basically the same before and after the f i rst step of excavation,and the safety factors are 1.0609 and 1.088,respectively.The safety factor increases slightly due to unloading at the slope top.The shape of slip surface changes apparently after the second step of excavation,and the safety factor becomes 1.039,which is slightly smaller than that after the f i rst step of excavation.The joint is exposed after the third step of excavation and the critical slip surface is formed along the joint.Correspondingly,the safety factor is reduced to 0.804.A vertical free face is formed after the fourth step of excavation and the slip surface is similar to that after the third step of excavation, and the safety factor is further reduced to 0.791.The results show that the safety factor decreases with the excavation as the joint surface is exposed and the vertical free face is formed.These factors have great effects on the slope stability.

Fig.19.Mesh ref i nement at slope toe and top.

Fig.20.Critical slip surface with mesh ref i nement at the slope toe and top.

Fig.21.Calculation model of rock slope excavation.

Table 1Material parameters of engineering slope.

Fig.22.Steps of slope excavation.

Fig.23.Critical slip surfaces and safety factors after each step of excavation.

Fig.24.Comparison of the safety factors between the SRM and the method based on the graph theory.

The SRM is also used here for comparison.The safety factors obtained by the two methods are very close to each other as shown in Fig.24.

7.Conclusions

In this paper,the inf l uences of edge generation,mesh shape and mesh density in the method based on graph theory on the position and shape of slip surface and safety factors are investigated.The results show that the proposed edge generation method can provide multi-directional choices for f i nding the critical slip surface of the slope and the results agree well with referenced solutions. Mesh shape was found to have limited inf l uence on the slope stability.However,mesh size and mesh density have substantial effects on the shape of slip surface.The average mesh size of about 1/ 10 of the slope height is suggested to ensure a balance between reliable results and computational eff i ciency.The proposed method removes the diff i culties in many assumptions and iterative calculations of the conventional methods and the results of a rock slope are similar to those of the SRM.It shows the validity of the presented method based on the graph theory.

Conf l ict of interest

We wish to con fi rm that there are no known con fl icts of interest associated with this publication and there has been no signi fi cant fi nancial support for this work that could have in fl uenced its outcome.

Acknowledgment

The authors gratefully acknowledge the support of the National Natural Science Foundation of China(Grant No.41130751),China ScholarshipCouncil,ResearchProgramforWesternChina Communication(Grant No.2011ZB04)and China Central University Funding.

Bellman R.Dynamic programming.Princeton,USA:Princeton University Press; 1957.

Bondy JA,Murty USR.Graph theory with applications.London:The Macmillan Press Ltd.;1976.

Cherkassky BV,Goldberg AV,Radzik T.Shortest paths algorithms:theory and experimental evaluation.Technical report 93-1480.Stanford:Stanford University;1993.

Dawson EM,Roth WH,Drescher A.Slope stability analysis by strength reduction. Geotechnique 1999;49(6):835-40.

Donald IB,Giam P.The ACADS slope stability programs review.In:The 6th International Symposium on Landslides,vol.3;1992.pp.1665-70.Christchurch, New Zealand.

Fang J.Slope stability analysis using direct search method based on 3D FEM and its application in tunnel excavation.PhD Thesis.Shanghai:Tongji University;2007 (in Chinese).

Farias MM,Naylor DJ.Safety analysis using fi nite elements.Computers and Geotechnics 1998;22(2):165-81.

Guo MW,Ge XR,Wang SL.Slope stability analysis under seismic load by vector sum analysis method.Journal of Rock Mechanics and Geotechnical Engineering 2011;3(3):282-8.

Kim JY,Lee SR.An improved search strategy for the critical slip surface using fi nite element stress fi elds.Computers and Geotechnics 1997;21(4):295-313.

Sarma SK,Tan D.Determination of critical slip surface in slope analysis.Geotechnique 2006;56(8):539-50.

Shen J,Karakus M,Xu C.Chart-based slope stability assessment using the generalized Hoek-Brown criterion.International Journal of Rock Mechanics and Mining Sciences 2013;64:210-9.

Wang G,Wang Y,Ren J.Theory,implementation and application of graph theory. Beijing:Peking University Press;2011(in Chinese).

Xie M,Wang Z,Liu X,Xu B.Three-dimensional critical slip surface locating and slope stability assessment for lava lobe of Unzen volcano.Journal of Rock Mechanics and Geotechnical Engineering 2011;3(1):82-9.

Xu W,Zhou J,Deng J,Shi C,Zhang Z.Slope stability analysis of limit equilibrium fi nite element method based on the Dijkstra algorithm.Chinese Journal of Geotechnical Engineering 2007;29(8):1159-72(in Chinese).

Zheng H,Tian B,Liu D,Feng Q.On de fi nitions of safety factor of slope stability analysis with fi nite element method.Chinese Journal of Rock Mechanics and Engineering 2005;24(13):2225-30(in Chinese).

Zheng W,Zhuang X,Li Y,Cai Y.Graph theory for stability analysis of rock/soil slopes based on numerical manifold method.Chinese Journal of Geotechnical Engineering 2013;35(11):2045-52(in Chinese).

Zheng Y,Tang X,Zhao S,Deng C,Lei W.Strength reduction and step-loading fi nite element approaches in geotechnical engineering.Journal of Rock Mechanics and Geotechnical Engineering 2009;1(1):21-30.

Zhou C,Chen Y,Jiang Q,Lu W.A generalized multi- fi eld coupling approach and its application to stability and deformation control of a high slope.Journal of Rock Mechanics and Geotechnical Engineering 2011;3(3):193-206.

Zhou J,Deng J,Xu F.A slope stability analysis method combined with limit equilibrium and fi nite element simulation.In:Advances in future computer and control systems,vol.1.Berlin:Springer;2012.pp.241-7.

Zhou J,Xu W,Deng J,Liu X.Stability analysis of slope under the condition of rainfall in fi ltration.Journal of Hydraulic Engineering 2008;39(9):1066-73(in Chinese).

Zhuang X,Cai Y,Zhu H,Zhou D.Rock slope stability analysis based on meshless methodandshortest pathalgorithms.ChineseQuarterly ofMechanics 2008;29(4):537-43(in Chinese).

Dr.Xiaoying Zhuangis now an Associate Professor in the Department of Geotechnical Engineering,College of Civil Engineering,Tongji University(TJU).Dr.Zhuang has focused on interdisciplinary research of geomechanics and computationalmechanicssince2005.HerPhDwas devoted to the cutting edge research of 3D fracture.She was awarded the“Zienkiewicz Prize for the best PhD Thesis in Computational Mechanics in 2010”.She pursued further research as a postdoctoral fellow at Norwegian University of Science and Technology on multiscale fracture modeling of nano-coating,which concluded when she accepted the academic post at TJU.At TJU,she quickly became a key academic staff member and set up her research directions of multiphysics and multiscale modeling.Dr.Zhuang’s key research areas include 3D fracture modeling,computational methods and constitutive models for rock mechanics and rock engineering. She developed a numerical modeling framework for arbitrary 3D crack propagation. She is also devoted to the THM modeling for compressed air energy storage in hard rock as porous media containing strong discontinuities.She has published over 50 papers including 30 SCI journal papers.She is currently the committee member of ISRM DDA Commission and ISRM THMC Commission and editorial board member of Theoretical and Applied Fracture Mechanics,KSCE Journal of Civil Engineering and Frontiers of Structural and Civil Engineering.In 2013,she has been awarded the Marie Curie International Incoming Fellowship of FP7 by European Research Commission.

*Corresponding author.Tel.:+86 21 65983982.

E-mail address:xiaoying.zhuang@gmail.com(X.Zhuang).

Peer review under responsibility of Institute of Rock and Soil Mechanics,Chinese Academy of Sciences.

Slope stability analysis

Edge generation

Mesh geometry