Method for generating nested container with no intersection and full coverage in the same layer and readable storage medium

Abstract

A method for generating a nested container with no intersection and same layer full coverage, including: giving a right undirected graph G(V, E, W) and network measurement index set {Ti} for dividing nodes in G, each network measurement index Ti corresponding to a Ci layer container set {Ci k}; deleting an edge weighing greater than Ti, and segmenting G into subgraphs, each a connected component; setting all nodes in the subgraph Gcm not in the Ci layer container as set L; selecting one node from set L as current anchor aj; starting with anchor aj, performing breadth-first search on all nodes in L and Ci+1 layer container containing aj with the path communicated therewith less than Ti forming a Ci layer container with anchor aj; setting j′=j+1, determining whether L is a null set; setting m=m+1, determining whether all subgraphs are processed; setting i=i−1, and determining whether i=1 is satisfied.

Claims

1. A method for generating nested container with no intersection and full coverage in the same layer, specifically comprising: step 1) giving a right undirected graph G (V, E, W) and a network measurement index set {Ti} to divide nodes in the right undirected graph G, such that each network measurement index Ti corresponds to a Ci layer container set {Ci k}; thereof, the network measurement index Ti is specifically time delay or hop or bandwidth, Ti<Ti+1, 1≤i≤I−1, I is a constant, 0≤k≤K−1, and K is the number of Ci layer containers, and the number of layers i is initialized to I−1; step 2) deleting an edge with the weight being greater than Ti, segmenting the right undirected graph G in step 1) into several sub-graphs, thereof each sub-graph is a connected component; and sorting the several sub-graphs in an order of number of nodes from smallest to largest, thereof each sub-graph is donated as Gcm=(Vcm, Ecm, Wcm); thereof 1≤m≤M, M is the number of sub-graphs, m is a serial number of a sub-graph, and m, that is, the number of sub-graphs, is initialized to 1; if p isolated nodes exist in the several sub-graphs, then each isolated node is directly set as an anchor, and becomes an independent Ci layer container, and it is assumed that j′=j+p, and m=m+p; and the number of anchors j is initialized to 1; step 3) setting all the nodes in the sub-graph Gcm in step 2) which are not added in the Ci layer container as a set L; step 4) selecting one node from the set L in step 3) as a current anchor aj; step 5) taking the current anchor aj as a starting point, and performing breadth-first search on all the nodes in the set L and in the Ci+1 layer container containing aj with a path communicated therewith being less than Ti, to form a Ci layer container with aj as an anchor; step 6) setting j′=j+1, judging whether the set L is a null set; if the set L is a null set, then going to the next step, and if the set L is not a null set, then returning to step 3), until the set L is a null set; step 7) setting m=m+1, judging whether all the sub-graphs are processed, if all the sub-graphs are processed, then going to the next step, if all the sub-graphs are not processed, then returning to step 3), until all the sub-graphs are processed; and step 8) setting i=i−1, judging whether i=1 is satisfied; if i=1 is satisfied, then the process is finished and all the Ci containers are constructed; if i=1 is not satisfied, then returning to step 2), until all the Ci containers are constructed.

2. The method for generating a nested container with no intersection and full coverage in a same layer of claim 1, wherein the Ci container is constructed and nested from top to bottom, and the number of layers of the Ci container gradually decreases.

3. The method for generating a nested container with no intersection and full coverage in a same layer of claim 1, wherein in step 4), selecting a node with the best performance indexes such as bandwidth, calculation and storage in the set L as a current anchor.

4. The method for generating a nested container with no intersection and full coverage in a same layer of claim 1, wherein as to the right undirected graph G (V, E, W) in step 1), V is a set of nodes which contains any network element with an independent address, E is a set of edges between nodes in a measuring record, and W is a set of weights between nodes in a measuring record.

5. The method for generating a nested container with no intersection and full coverage in a same layer of claim 1, wherein in step 1), when i=1, a C1 layer container is a bottom layer container, and is constituted by multiple network elements, and a C2 layer container is constituted by multiple C1 layer containers, and so on, and the Ith layer is a top layer container CI, and is constituted by multiple CI−1 layer containers.

6. A computer readable storage medium with a computer program stored thereon, wherein the computer program is executed by a processor through the method for generating a nested container with no intersection and full coverage in a same layer in claim 1.

7. The computer readable storage medium with a computer program stored thereon, wherein the computer program is executed by a processor through the method for generating a nested container with no intersection and full coverage in a same layer in claim 2.

8. The computer readable storage medium with a computer program stored thereon, wherein the computer program is executed by a processor through the method for generating a nested container with no intersection and full coverage in a same layer in claim 3.

9. The computer readable storage medium with a computer program stored thereon, wherein the computer program is executed by a processor through the method for generating a nested container with no intersection and full coverage in a same layer in claim 4.

10. The computer readable storage medium with a computer program stored thereon, wherein the computer program is executed by a processor through the method for generating a nested container with no intersection and full coverage in a same layer in claim 5.

Description

BRIEF DESCRIPTION OF DRAWINGS

(1) FIG. 1 is a flow chart of a method for generating a nested container with no intersection and full coverage in a same layer of the present invention.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(2) As shown in FIG. 1, the present invention provides a method for generating a nested container with no intersection and full coverage in a same layer, specifically comprising:

(3) step 1) giving a right undirected graph G (V, E, W) and a network measurement index set {Ti} to divide nodes in the right undirected graph G, such that each network measurement index Ti corresponds to a Ci layer container set {Ci k};

(4) wherein, the network measurement index Ti is specifically time delay or hop or bandwidth, Ti<Ti+1, 1≤i≤I−1, I is a constant, 0≤k≤K−1, and K is the number of Ci layer containers, and the number of layers i is initialized to I−1;

(5) step 2) deleting an edge with a weight being greater than Ti, segmenting the right undirected graph G in step 1) into several sub-graphs, wherein each sub-graph is a connected component; and sorting the several sub-graphs in an order of number of nodes from smallest to largest, wherein each sub-graph is donated as Gcm=(Vcm, Ecm, Wcm); wherein 1≤m≤M, M is the number of sub-graphs, m is a serial number of a sub-graph, and m, that is, the number of sub-graphs, is initialized to 1; c herein is not a parameter, c means child, is only a label, represents a sub-graph, and mainly functions to distinguish G from Gc. If p isolated nodes exist in the several sub-graphs, then each isolated node is directly set as an anchor, and becomes an independent Ci layer container, and it is assumed that j′=j+p, and m=m+p; and the number of anchors j is initialized to 1;

(6) step 3) setting all the nodes in the sub-graph Gcm in step 2) which are not added in the Ci layer container as a set L;

(7) step 4) selecting one node from the set L in step 3) as a current anchor aj;

(8) step 5) taking the current anchor aj as a starting point, and performing breadth-first search on all the nodes in the set L and in the Ci+1 layer container containing aj with a path communicated therewith being less than Ti, to form a Ci layer container with aj as an anchor;

(9) step 6) setting j′=j+1, judging whether the set L is a null set; if the set L is a null set, then going to the next step, and if the set L is not a null set, then returning to step 3), until the set L is a null set;

(10) step 7) setting m=m+1, judging whether all the sub-graphs are processed, if all the sub-graphs are processed, then going to the next step, if all the sub-graphs are not processed, then returning to step 3), until all the sub-graphs are processed; and

(11) step 8) setting i=i−1, judging whether i=1 is satisfied; if i=1 is satisfied, then the process is finished and all the Ci containers are constructed; if i=1 is not satisfied, then returning to step 2), until all the Ci containers are constructed.

(12) The Ci container is constructed and nested from top to bottom, and the number of layers of the Ci container gradually decreases.

(13) Preferably, in step 4), a node with the best performance indexes such as bandwidth, calculation and storage in the set L is selected as a current anchor;

(14) in the above technical solution, as to the right undirected graph G (V, E, W) in step 1), V is a set of nodes which contains any network element with an independent address, E is a set of edges between nodes in a measuring record, and W is a set of weights between nodes in a measuring record.

(15) In the above technical solution, in step 1), when i=1, a C1 layer container is a bottom layer container, and is constituted by multiple network elements, and a C2 layer container is constituted by multiple C1 layer containers, and so on, and the Ith layer is a top layer container CI, and is constituted by multiple CI−1 layer containers.

(16) The present invention further provides a computer readable storage medium with a computer program stored thereon, and the computer program is executed by a processor through the above method for generating a nested container with no intersection and full coverage in a same layer.

(17) Finally, it should be noted that, the above embodiments are merely used for explaining technical solutions of the present invention, rather than for limiting the present invention. Although the present invention has been described in detail with reference to embodiments, those skilled in the art should understand that, any modifications or equivalent substitutions made to the technical solutions of the present invention all do not depart from spirit and scope of the technical solutions of the present invention, and should be encompassed in the scope of claims of the present invention.