Method for efficiently retrieving topology-specific data for point-to-point networks
View Patent ↗Network topology codes are computed and used as keys to retrieve topology-specific information for isomorphic networks.
1. In a computer a method of providing topology-specific data for a given point-to-point network, comprising the steps of:
pre-computing and making available topology-specific data for a plurality of point-to-point networks by a computer;
calculating and making available a respective unique topology code for each of the plurality of networks by a computer;
calculating a topology code by a computer for the given network;
using the calculated topology code for the given network by a computer as a key to look up the pre-computed topology-specific data for networks having the same topology code; and
retrieving the pre-computed topology-specific data for the given network,
wherein candidate topology codes are calculated by evaluating a graph of each network and using the evaluations to populate an adjacency matrix.
2. The method of claim 1 wherein topology codes are compiled by mapping adjacency matrix elements to bits into the topology codes.
3. The method of claim 2 wherein only the portion of the adjacency matrix on one side of a diagonal is populated.
4. The method of claim 1 wherein the evaluation is a Breadth-First-Search (BFS) of a tree representation of the graph.
5. The method of claim 4 wherein traversals of all possible BFS tree representations of the graph are considered in calculating candidate topology codes.
6. The method of claim 5 wherein the candidate topology code with the maximum value is taken to be the topology code representing the graph.
7. The method of claim 6 wherein if the latest-computed digit of a candidate topology code gives the string a lower value than the same length string of a previously computed candidate code, the calculation of the current candidate code is aborted.
8. The method of claim 6 wherein the node ordering which first specified the label ordering used to generate the topology code represents a canonical labeling for the graph.
9. The method of claim 1 wherein the evaluation is a Depth-First-Search (DFS) of a tree representation of the graph.
10. The method of claim 9 wherein traversals of all possible DFS tree representations of the graph are considered in calculating candidate topology codes.
11. The method of claim 10 wherein the candidate topology code with the maximum value is taken to be the topology code representing the graph.
12. The method of claim 11 wherein if the latest-computed digit of a candidate topology code gives the string a lower value than the same length string of a previously computed candidate code, the calculation of the current candidate code is aborted.
13. The method of claim 11 wherein the DFS tree which first specified the label ordering used to generate the topology code represents a canonical labeling for the graph.