Method and device for extracting skeleton topology structure of electric power grid

The present invention relates to and claims the benefit of the filing date of commonly-owned, PCT Patent Application No. PCT/CN2012/074087, filed Apr. 16, 2012, which further claims the benefit of priority date of commonly-owned, co-pending Chinese Patent Application No. CN 201110140427.8, filed on May 27, 2011, the entire contents and disclosure of which is incorporated by reference as if fully set forth herein.

The present invention generally relates to an electric power grid, and more specifically to a method and device for extracting skeleton topology structure of the electric power grid.

An electric power system as a whole consists of electric components connected in a certain form, such as generators, transformers, buses, switches, disconnector, and lines. Performance of its electric function is restricted by component characteristics and connecting relations of the components. With regardless of physical component characteristics of the grid, the electric power system can be abstracted as a grid topology formed by branches and nodes connected by the branches. Considering the restrictions of component characteristics and their connecting relations, an electric power grid actually includes two types of topology structures: geometry topology and physical topology. The geometry topology represents the geometrical connecting status of grid devices, while the physical topology represents the physical electric coupling relations of grid components.

Analysis of grid topology structure of an electric power system is usually conducted in the following two aspects. The first aspect lies in establishing of the grid topology structure. According to the status of switches, the grid connected by various devices can be indicated by a matrix of connecting relations of branches and nodes, which can be used for analyzing and computing the power system. Also, identification of inter-connected individual sub-device is the ground for physical analyzing, computing and studying of the electric power system. The second aspect lies in studying and utilizing the grid topology structure to excavating the internal relations between its topology structure and physical functions, so as to make it more convenient and easier for analyzing and controlling the electric power system. In actual operation, different business departments of an electric power grid company need to make analysis and computing of the electric power system according to their own business needs. Thereby, different points of concerns to primary topology structure of the electric power system are focused on abstracting different skeleton topology networks from a primary topology structure. Currently, the business departments of the electric power grid company mainly extracts skeleton topology structure from the primary topology structure manually according to their business needs and based on experience of experts. However, there are actually a huge number of components within an electric power system and the lines are heavy and complicated. For reasons such as load changes, equipment maintenance and active optimizations, the grid is continuously renovated at the equipment level, and the primary topology structure is often changed. If the business departments extract and maintain skeleton topology structure from the primary topology structure manually, the working procedures would be overloaded with details and the costs would be high.

Therefore, it is necessary to provide a method for automatic and efficient extracting skeleton topology structure according to operational needs.

In order to solve these problems, this invention provides an automatic and efficient method and device for extracting skeleton topology structure.

According to one aspect of the invention, a method for extracting a skeleton topology structure of an electric power grid is provided. The method comprises: receiving a description of a topology sub-structure corresponding with user's need and a description of a skeleton topology sub-structure extracted from the topology sub-structure; generating a first incidence matrix based on the description of the topology sub-structure and generating a second incidence matrix based on the description of the skeleton topology sub-structure; generating a third incidence matrix based on a primary topology structure of electric power grid; searching from the third incidence matrix a sub-matrix that matches the first incidence matrix; obtaining a fourth incidence matrix by using the second incidence matrix to transform the matching sub-matrix; and generating a skeleton topology structure corresponding to the primary topology structure based on the fourth incidence matrix.

According to a second aspect of the invention, a device for extracting a skeleton topology structure of an electric power grid is provided. The device comprises: a receiving module configured to receive a description of a topology sub-structure corresponding with user's need and a description of a skeleton topology sub-structure extracted from the topology sub-structure; an incidence matrix generating module configured to generate a first incidence matrix based on the description of the topology sub-structure, to generate a second incidence matrix based on the description of the skeleton topology sub-structure, and to generate a third incidence matrix based on a primary topology structure of electric power grid; a searching module configured to search from the third incidence matrix a sub-matrix that matches the first incidence matrix; a matrix transforming module configured to obtain a fourth incidence matrix by using the second incidence matrix to transform the matching sub-matrix; and a skeleton topology structure generating module configured to generate a skeleton topology structure corresponding to the primary topology structure according to the fourth incidence matrix.

The method and device for extracting skeleton topology structure according to this invention can automatically and efficiently extract skeleton topology structure according to business needs.

In combination with the drawings and in reference to the following detailed descriptions of exemplified embodiments, the invention itself, preferred embodiments, objectives and advantages of this invention can be better understood.

FIG. 1 shows the method for extracting a skeleton topology of the electric power grid according to an embodiment of this invention.

FIG. 2 shows a diagram of the topology substructure, according to an embodiment of this invention.

FIG. 3 shows a directed graph of the connecting relations of nodes-branches formed by abstracting the topology substructure in FIG. 2 , according to an embodiment of this invention.

FIG. 4 shows diagram of the skeleton topology substructure, according to an embodiment of this invention.

FIG. 5 shows a directed graph of the connecting relations of nodes-branches formed by abstracting the skeleton topology substructure in FIG. 4 , according to an embodiment of this invention.

FIG. 6 shows diagram of the primary topology structure, according to an embodiment of this invention.

FIG. 7 shows a directed graph of the connecting relations of nodes-branches formed by abstracting the topology substructure in FIG. 6 , according to an embodiment of this invention.

FIG. 8 shows a flow chart of searching an incidence matrix of the topology substructure within the incidence matrix of a primary topology structure of the electric power grid.

FIG. 9 shows a specific process for implementing Step S 802 in FIG. 8 .

FIG. 10 shows a specific process for implementing Step S 804 in FIG. 8 .

FIG. 11 shows a skeleton topology structure corresponding to the primary topology structure, according to an embodiment of this invention.

FIG. 12 shows a block diagram of the device for extracting skeleton topology in an electric power grid, according to an embodiment of this invention.

FIG. 13 is a schematic block diagram of the structure of the computing devices capable of implementing the embodiments of this invention.

In the following discussion, the method and device for extracting a skeleton topology structure of an electric power grid according to the embodiments of this invention will be described in combination with the attached drawings, so that objectives and advantages of this invention can be better understood.

FIG. 1 shows a method for extracting a skeleton topology of the electric power grid according to an embodiment of this invention. The method comprises: in Step S 101 , receiving descriptions of a topology sub-structure corresponding with user's need and receiving descriptions of skeleton topology sub-structure extracted from the topology sub-structure; in Step S 102 , generating a first incidence matrix based on descriptions of the topology sub-structure and generating a second incidence matrix based on descriptions of the skeleton topology sub-structure; in Step S 103 , generating a third incidence matrix based on a primary topology structure of the electric power grid; in Step S 104 , searching from the third incidence matrix a sub-matrix that matches the first incidence matrix; in Step S 105 , generating a fourth incidence matrix by using the second incidence matrix to transform the matching sub-matrix; in Step S 106 , generating skeleton topology structure corresponding to the primary topology structure according to the fourth incidence matrix.

In step S 101 , a description of a topology sub-structure that corresponds with the need of user and a description of a skeleton topology sub-structure extracted from the topology sub-structure are received. Because different business departments of an electric power company have different business needs and different business analysis objectives, their points of concerns are different even for a same primary topology structure of electric power grid. Thereby, different business departments need to specify topology substructures that correspond with their business needs, and specify skeleton topology substructures extracted from the topology substructures. With regards to a primary topology structure of a whole electric power system, the topology substructure is subset of the primary topology structure, and the skeleton topology sub-structure is further simplification of the topology substructure, which is made by the departments according to their business needs. According to an embodiment of this invention, the user is not only provided with an editing tool with graphic interface so that the user can edit topology structures concerned personally, but also can select a topology substructure concerned from a primary topology structure and make further simplification to the topology substructure to form a skeleton topology substructure. According to another embodiment of this invention, files containing topology substructures and skeleton topology substructures edited by the user can be imported.

In step S 102 , a first incidence matrix is generated based on the description of the topology sub-structure, and a second incidence matrix is generated based on the description of the skeleton topology sub-structure, in which the first incidence matrix corresponds to the incidence matrix of the topology sub-structure and the second incidence matrix corresponds to the incidence matrix of the skeleton topology sub-structure. In the field of electric power transmission, the incidence matrix can be used to describe an incidence relationship between the connections among electric components and the electric components within a topology structure of the electric power grid. Specifically, the primary topology structure of an electric power grid connecting various devices can be abstracted as a directed graph of the connecting relations of nodes-branches, in which the nodes indicate the electric components while the branches indicate the connections of the electric components. A topology structure of an electric power grid with n nodes and b branches can be indicated by an n×b matrix. Row vectors of the matrix correspond to the nodes while column vectors of the matrix correspond to the branches of the electric power grid. Vector a ij the matrix is defined as:

Each column of the incidence matrix corresponds to a branch, every branch must connect two nodes, and the directions are one inward and the other outward. Thus, every column contains only two nonzero elements, +1 and −1. If summing elements of all rows by columns, a row with each element as zero would be obtained. Thereby, the rows of a matrix are not independent to each other. For elements of any of the rows, they can be obtained by summing all rows other than this row and changing the signs of the sum. Taking the topology substructure in FIG. 2 as an example to describe the generation of corresponding incidence matrix, the first step is to abstract the topology substructure in FIG. 2 to form the directed graph of the connecting relations of nodes-branches. It can be seen from the directed graph that the connection between node 1 and node 3 is disconnector 1 , the connection between node 2 and node 4 is disconnector 2 , the connection between node 3 and node 5 is ground disconnector 1 , the connection between node 4 and node 5 is ground disconnector 2 , the connection between node 3 and node 4 is breaker 1 . A row vector V includes bus segment 1 , bus segment 2 , dummy point 3 , dummy point 4 , dummy point 5 . A column vector M includes disconnector 1 , disconnector 2 , breaker 1 , ground disconnector 1 , ground disconnector 2 . According to the above description of the incidence matrix, an incidence matrix A=V×M corresponding to the topology substructure is obtained.

Again taking the topology substructure in FIG. 2 as an example, because the user is a dispatch department of electric power system, more concerns are given to the status of buses and switches, the skeleton topology substructure extracted according to user needs only include buses and switches. FIG. 4 shows the skeleton topology substructure according to an embodiment of this invention. FIG. 5 shows a directed graph of the connecting relations of nodes-branches formed by abstracting the skeleton topology substructure in FIG. 4 , according to an embodiment of this invention. With the method of generating the incidence matrix, an incidence matrix A′ corresponding to the skeleton topology substructure is obtained.

In step S 103 , a third incidence matrix is generated based on a primary topology structure of the electric power grid, in which the third incidence matrix corresponds to the incidence matrix of the primary topology structure. The primary topology structure of the electric power grid corresponds to the electric power grid as a target of analysis. Generally, the electric power grid, as a target of analysis, covers a city or a district. A city-level medium electric transmission system has about 400 lines, 120 substations. Each substation has about 500 primary devices and each line has about 50 primary devices. Major devices include: main transformers, switches, breakers, buses, lines, current transformers, voltage transformers, reactors and ground disconnector. That means the primary topology structure of corresponding electric power grid has complicated lines and numerous electric components. Based on the above description of the incidence matrix, the incidence matrix of primary topology structure is generated according to the primary topology structure of the electric power grid. To make it convenient for descriptions, a simple primary topology structure is schematically selected in an embodiment of this invention. FIG. 6 shows a diagram of the primary topology structure, according to an embodiment of this invention. By abstracting the topology substructure in FIG. 6 , the directed graph of the connecting relations of nodes-branches in FIG. 7 is formed. The row vector V′ includes auxiliary bus segment 1 , auxiliary bus segment 2 , dummy point 3 , dummy point 4 , dummy point 5 , main bus segment 2 , main bus segment 1 , outgoing line 2 , outgoing line 1 . The column vector M′ includes disconnector 1 , disconnector 2 , breaker 1 , ground disconnector 1 , ground disconnector 2 , breaker 2 , breaker 3 , disconnector 3 , disconnector 4 . Then according to the description of the incidence matrix, the incidence matrix A″=V′×M′ corresponding to the primary topology structure is obtained.

In step S 104 , a sub-matrix that matches the first incidence matrix is searched from the third incidence matrix, that is, a sub-matrix that matches the incidence matrix of a topology substructure is searched from the incidence matrix of a primary topology structure of the power grid. FIG. 8 shows a flow chart of searching an incidence matrix of the topology substructure from the incidence matrix of a primary topology structure of the electric power grid. Specifically, the flow starts from Step S 801 . In step S 802 , the row vectors and column vectors of the incidence matrix of a topology substructure is searched from the row vectors and column vectors of the incidence matrix of a primary topology structure, respectively. Specifically, FIG. 9 shows the specific process for implementing Step S 802 in FIG. 8 . In step S 8021 , the row vectors of the incidence matrix of a topology substructure are searched one by one from the row vectors of the incidence matrix of a primary topology structure. In step S 8022 , the row vectors searched out are added into the row vectors' list, and the row numbers of the row vectors within the incidence matrix of the primary topology structure is recorded. In step S 8023 , it is judged whether the row vectors' list includes all row vectors in the incidence matrix of the primary topology structure. If result of the judgment is no, the flow ends; if result of the judgment is yes, the flow proceeds to Step S 8024 , in which the column vectors of the incidence matrix of a topology substructure is searched one by one from the column vectors of the incidence matrix of a primary topology structure. In Step S 8025 , the column vectors searched out are added into the column vectors' list, and the column numbers of the column vectors within the incidence matrix of the primary topology structure is recorded. In step S 8026 , it is judged whether the column vectors' list includes all column vectors in the incidence matrix of the primary topology structure. If result of the judgment is no, the flow ends; if result of the judgment is yes, the flow proceeds to Step S 803 in FIG. 8 . Those skilled in the art will appreciate that when searching the row vectors and column vectors of the incidence matrix of a topology substructure from the row vectors and column vectors of the incidence matrix of a primary topology structure, the sequence is not invariable. It is also possible to search column vectors of the incidence matrix of a topology substructure first, and then search the row vectors of the incidence matrix of a topology substructure after making sure that all the column vectors of the incidence matrix of a topology substructure are searched out. In this way, objective of this invention can also be achieved. In Step S 803 , if all the row vectors and column vectors of the incidence matrix of a topology substructure are searched out from the row vectors and column vectors of the incidence matrix of a primary topology structure, it is determined that possibly matching sub-matrix contained in the incidence matrix of primary topology structure. By referring to the row vectors and column vectors of the incidence matrix of a topology substructure, the row vectors and column vectors searched out are permutated and combined, possibly matching sub-matrix contained in the incidence matrix of primary topology structure can be determined. In Step S 804 , a sub-matrix that matches the incidence matrix of the topology substructure is filtered out from the possibly matching sub-matrix contained in the incidence matrix of primary topology structure. FIG. 10 shows a specific process for implementing Step S 804 in FIG. 8 . In Step S 8041 , the vector coordinates of the possibly matching sub-matrix are mapped with the vector coordinates of the incidence matrix of the topology substructure. In step S 8042 , the vector values of the vector coordinates of the possibly matching sub-matrix is compared with the vector values of the vector coordinates of the incidence matrix of the topology substructure having mapping relations. In step S 8043 , it is judged whether each vector value in the possibly matching sub-matrix is same as the mapping vector values. If result of the judgment is no, then the flow proceeds to Step S 805 and ends. If result of the judgment is yes, then the flow proceeds to Step S 8044 , in which the sub-matrix that matches the incidence matrix of the topology substructure is filtered out, and the flow ends.

According to the above embodiment of this invention, the incidence matrix A of a topology substructure is searched from the incidence matrix A″ of a primary topology structure. With the searching method, the row vectors V of the incidence matrix A of the topology substructure is searched out one by one from the row vectors V′ of the incidence matrix A″. That is, the buses and dummy points are searched from row vectors V′ of the incidence matrix A″. Because both auxiliary buses and main buses are buses, the row vectors searched out include auxiliary bus segment 1 , auxiliary bus segment 2 , dummy point 3 , dummy point 4 , dummy point 5 , main bus segment 2 , main bus segment 1 . The row vectors searched out are added into the row vectors' list as indicated in Table 1, and the row number of the row vectors searched out within the incidence matrix of the primary topology structure is recorded. At this moment, it is judged that the row vectors list includes all row vectors of the incidence matrix of the topology substructure. Thus, the column vectors M of the incidence matrix of the topology substructure is searched out one by one from the column vectors M″ of the incidence matrix of the primary topology structure. That is, the disconnector, breakers and ground disconnector are searched from the column vectors M″ of the incidence matrix of the primary topology structure. The column vectors searched out include disconnector 1 , disconnector 2 , breaker 1 , ground disconnector 1 , ground disconnector 2 , breaker 2 , breaker 3 , disconnector 3 , and disconnector 4 . The column vectors searched out are added into the column vectors' list as indicated in Table 2, and the column number of the column vectors searched out within the incidence matrix of the primary topology structure is recorded. At this moment, it is judged that the column vectors list includes all column vectors of the incidence matrix of the topology substructure.

Based on row vectors and column vectors searched out, the possibly matching sub-matrix present in the incidence matrix of the topology substructure is determined. Based on principles of permutation and combination, column vectors have the following 6 possibilities: U 1 , U 2 , . . . U 6 ; row vectors have the following 18 possibilities: W 1 , W 2 , . . . W 18 . Thereby, ultimately there could be 108 possibly matching sub-matrixes obtained: B 1 , B 2 , . . . B 108 . For the sake of brief description, only 3 of the possibilities, B 1 , B 2 and B 3 , are given as examples. Others are omitted herein.

⋯

Tanking B 1 as an example, according to method of generating incidence matrix, a sub-matrix B 1 is obtained.

The vector coordinates of the possibly matching sub-matrix are mapped with the vector coordinates of the incidence matrix of the topology substructure. Taking B 1 as an example, the coordinates of vector b ij of B 1 are mapped with the coordinates of vector a ij of the incidence matrix A of the topology substructure. By reference to the row vectors' table and column vectors' table, their mapping relations are recorded.

(b 11 , a 11 ) (b 12 , a 12 ) (b 13 , a 13 )(b 14 , a 14 )(b 15 , a 15 ) (b 21 , a 21 ) (b 22 , a 22 ) (b 23 , a 23 )(b 24 , a 24 )(b 25 , a 25 ) (b 31 , a 31 ) (b 32 , a 32 ) (b 33 , a 33 )(b 34 , a 34 )(b 35 , a 35 ) (b 41 , a 41 ) (b 42 , a 42 ) (b 43 , a 43 )(b 44 , a 44 )(b 45 , a 45 ) (b 51 , a 51 ) (b 52 , a 52 ) (b 53 , a 53 )(b 54 , a 54 )(b 55 , a 55 )

The vector values of vector coordinates having mapping relations, such as the following values having mapping relations: (b 11 , a 11 ), b 11 =1, a 11 =1, b 11 =a 11 ; (b 12 , a 12 ), b 12 =0, a 12 =0, b 12 =a 12 ; . . . (b 55 , a 55 ), b 55 =−1, a 55 =−1, b 55 =a 55 are compared one by one. It is determined therefrom that each vector value of the sub-matrix B 1 is same as the vector value of the mapped vector value in the incidence matrix A. Then it is determined that the sub-structure B 1 is a matching topology substructure.

Also taking B 2 as an example, a substructure B 2 is obtained by the method of generating incidence matrix described above.

The coordinates of vector b ij of B 2 are mapped with the coordinates of vector a ij of the incidence matrix A of the topology substructure. By reference to the row vectors' table and column vectors' table, their mapping relations are recorded.

(b 12 , a 11 ) (b 18 , a 12 ) (b 13 , a 13 )(b 14 , a 14 )(b 15 , a 15 ) (b 22 , a 21 ) (b 28 , a 22 ) (b 23 , a 23 )(b 24 , a 24 )(b 25 , a 25 ) (b 32 , a 31 ) (b 38 , a 32 ) (b 33 , a 33 )(b 34 , a 34 )(b 35 , a 35 ) (b 42 , a 41 ) (b 48 , a 42 ) (b 43 , a 43 )(b 44 , a 44 )(b 45 , a 45 ) (b 52 , a 51 ) (b 58 , a 52 ) (b 53 , a 53 )(b 54 , a 54 )(b 55 , a 55 )

The vector values of vector coordinates having mapping relations are compared one by one. For example, if the following values having mapping relations (b 12 , a 11 ), b 12 =0, a 11 =1, b 12 and a 11 are not equal, it is determined therefrom that sub-matrix B 2 is not a matching topology substructure.

Then, the remaining possibly matching sub-matrixes are traversed. It is finally filtered out that only B 1 is a matching topology substructure. The section surrounded by a black frame in the following incidence matrix A″ is the matching sub-matrix B 1 .

In step S 105 , a fourth incidence matrix is obtained by using the second incidence matrix to transform the matching sub-matrix, in which the fourth incidence matrix corresponds to the incidence matrix of the skeleton topology structure of the primary topology structure.

In step S 106 , a skeleton topology structure corresponding to the primary topology structure is generated according to the fourth incidence matrix.

According to an embodiment of this invention, obtaining the fourth incidence matrix by using the second incidence matrix to transform the matching sub-matrix comprises: replacing the matching sub-matrix with the second incidence matrix to obtain the fourth incidence matrix; then generating the skeleton topology structure corresponding to the primary topology structure according to the fourth incidence matrix.

According to the above embodiment of this invention, a incidence matrix B of skeleton topology structure corresponding to the primary topology structure is generated by replacing the matching sub-matrix B 1 with the incidence matrix A′ of the skeleton topology structure. The skeleton topology structure as shown in FIG. 11 corresponding to the primary topology structure is generated according to the incidence matrix B of the skeleton topology structure corresponding to the primary topology structure.

According to another embodiment of this invention, generating a fourth incidence matrix by using the second incidence matrix to transform the matching sub-matrix comprises the steps of: determining a transformation matrix according to the first incidence matrix and second incidence matrix; obtaining a fourth incidence matrix by using the transformation matrix to transform the matching sub-matrix; generating a skeleton topology structure corresponding to the primary topology structure according to the fourth incidence matrix.

According to the above embodiment of this invention, taking incidence matrixes A and A′ computed in Step S 102 as an example, the transformation matrix is determined according to the incidence matrix of the topology substructure and the incidence matrix of the skeleton topology substructure. The relation among the incidence matrix of the topology substructure, the incidence matrix of the skeleton topology substructure and the transformation matrix of the skeleton topology substructure is A×H=A′. Based on knowledge of matrix conversion, a transformation matrix is obtained with H=A −1 ×A′. By using the formulation H=A −1 ×A′, the transformation matrix H is obtained. The incidence matrix corresponding to primary topology structure and skeleton topology structure is generated by using the transformation matrix H and matching sub-matrix B 1 . By using formulation B 1 ×H=A′, B 1 is transformed into A′, and incidence matrix B of skeleton topology structure corresponding to the primary topology structure is generated.

Based on the same inventive concept, this invention provides a device for extracting skeleton topology of electric power grid. FIG. 12 shows a block diagram of the device for extracting skeleton topology in an electric power grid, according to an embodiment of this invention. The device comprises: a receiving module 1201 configured to receive a description of a topology sub-structure corresponding with user's need and a description of skeleton topology sub-structure extracted from the topology sub-structure; an incidence matrix generating module 1202 configured to generate a first incidence matrix based on the description of the topology sub-structure, to generate a second incidence matrix based on the description of the skeleton topology sub-structure, and to generate a third incidence matrix based on a primary topology structure of the electric power grid; a searching module 1203 configured to search from the third incidence matrix a sub-matrix that matches the first incidence matrix; a matrix transforming module 1204 configured to obtain a fourth incidence matrix by using the second incidence matrix to transform the matching sub-matrix; and a skeleton topology structure generating module 1205 configured to generate the skeleton topology structure corresponding to the primary topology structure according to the fourth incidence matrix.

According to an embodiment of this invention, the matrix transforming module 1204 is further configured to: generate a fourth incidence matrix by using the second incidence matrix to replace the matching sub-matrix.

According to an embodiment of this invention, the matrix transforming module 1204 is further configured to: determine the transformation matrix according to the first incidence matrix and second incidence matrix; and obtain a fourth incidence matrix by using the transformation matrix to transform the matching sub-matrix.

According to an embodiment of this invention, the searching module 1203 further comprises: a vector searching module, being configured to search the row vectors and column vectors of the first incidence matrix from the row vectors and column vectors of the third incidence matrix respectively; a sub-matrix determining module, being configured to determine that possibly matching sub-matrix is contained in the third incidence matrix if all the row vectors and column vectors of the first incidence matrix are searched out from the row vectors and column vectors of the third incidence matrix; a sub-matrix filtering module, being configured to filter out the sub-matrix matching the first incidence matrix from the possibly matching sub-matrixes contained in the third incidence matrix.

According to an embodiment of this invention, the vector searching module is further configured to: search the row vectors of the first incidence matrix one by one from the row vectors of the third incidence matrix; add the row vectors searched out into the row vectors' list, and record the row number of the row vectors in the third incidence matrix; search the column vectors of the first incidence matrix from the column vectors of the third incidence matrix if it is determined that the row vectors' list includes all row vectors in the first incidence matrix; add the column vectors searched out into the column vectors' list, and record the column number of the column vectors in the third incidence matrix; judge whether the column vectors' list includes all column vectors in the first incidence matrix;

According to an embodiment of this invention, the sub-matrix determining module is further configured to: by reference to the row vectors and column vectors of the incidence matrix of a topology substructure, permutate and combine the row vectors and column vectors searched out to determine possibly matching sub-matrix contained in the third incidence matrix.

According to an embodiment of this invention, the sub-matrix filtering module is further configured to: map the vector coordinates of the possibly matching sub-matrix with the vector coordinates of the first incidence matrix; to compare the vector values of the vector coordinates of the possibly matching sub-matrix with the vector values of the vector coordinates of the first incidence matrix having mapping relations; if the vector value of each vector coordinate of the possibly matching sub-matrix is same as the vector value of vector coordinates of the first incidence matrix having mapping relations, to filter out the sub-matrix matching the first incidence matrix from the possibly matching sub-matrixes.

The method and device for extracting skeleton topology structure according to this invention can automatically and efficiently extract skeleton topology structures according to business needs. Thus, the frequent occurrence of collisions caused by different frequencies in updating skeleton topology structures by various business departments can be avoided.

FIG. 13 is a schematic block diagram of the structure of the computing devices for implementing the embodiments of this invention. The computer system in FIG. 13 comprises CPU (central processing unit) 1301 , RAM (random access memory) 1302 , ROM (read-only memory) 1303 , system bus 1304 , hard disc controller 1305 , keyboard controller 1306 , serial interface controller 1307 , parallel interface controller 1308 , display controller 1309 , hard disc 1310 , keyboard 1311 , serial peripheral equipment 1312 , parallel peripheral equipment 1313 and display 1314 . Among these components, the CPU 1301 , RAM 1302 , ROM 1303 , hard disc controller 1305 , keyboard controller 1306 , serial interface controller 1307 , parallel interface controller 1308 , display controller 1309 are connected to system bus 1304 ; hard disc 1310 is connected to hard disc controller 1305 ; keyboard 1311 is connected to keyboard controller 1306 ; serial peripheral equipment 1312 is connected to serial interface controller 1307 ; parallel peripheral equipment 1313 is connected to parallel interface controller 1308 ; and display 1314 is connected to display controller 1309 .

The function of each component in FIG. 13 is well known in this field, and the structure in FIG. 13 is conventional. Such a structure is not only used in PC, but also in handhold devices such as Palm PC, PDA (personal digital assistant), mobile phones. In different appliances, such as in realizing the user terminal containing the user module according to this invention or the host server containing the network application servers according to this invention, some components can be added to the structure shown in FIG. 13 , or some components in FIG. 13 can be omitted. The system shown in FIG. 13 is controlled by computer readable instructions, generally stored in hard disc 1310 , EPROM or other nonvolatile memories as software. The software can also be downloaded from internet (not indicated in the drawing). The software stored in hard disc 1310 or downloaded from internet can be loaded in RAM 1302 and executed by CPU 1301 , so as to carry out functions defined by the software.

Although the computer system described in FIG. 13 can support the technical solution provided according to this invention, it is just an example of a computer system. Those skilled in the art will appreciate that embodiments of this invention can also be realized with many other designs of computer systems.

The exemplarily embodiments of the present invention have been described by reference to the attached drawings, but it should be understood that this invention is not limited to these exact embodiments, and those of ordinary skill in the art can make modifications and variations without departing from the scope and spirit of the invention. All these modifications and variations are intended to be included within the scope of this invention defined by the attached claims.

It should be understood that at least some aspects of this invention can be alternatively implemented as program products. Programs defining functions relating to this invention can be transmitted to data storage device or computer devices through various signal bearing media. The signal bearing media include but not limit to read only medium (such as CD-ROM), writable storage medium (such as floppy disc and hard disc driver, read/write CD ROM, optical medium) as well as communication media like computers having ethernet and telephone networks. Thereby, it should be understood that among these signal bearing media, when they carry or coded with the computer readable instructions managing the methodology functions of this invention, they represent alternative embodiments of this invention. This invention can be realized in forms of hardware, software, firmware or their combinations. This invention can be realized on one computer device in a centralized manner, or be realized in a dispersed manner. With the dispersed manner, different components are dispersed on a number of inter-connected computer devices. Any computer devices or other devices that are suitable for executing the methods described herein are appropriate. Preferably, this invention is carried out in a form of combination of computer software and general purpose computer hardware. In this way of realizing the invention, when the computer program is loaded and executed, the computer device is controlled to execute the method of this invention or constitute the system of this invention.

The above description is intended to describe with examples the preferred embodiment of this invention. The above descriptions of preferred embodiments are not exhaustive, neither it is intended to limited to the invention in the definite form disclosed. In view of this teaching, many modifications and variations are possible. These modifications and variations are apparent for those skilled in the art, and are within the scope of this invention defined by the attached claims.