APPARATUS AND METHOD FOR GENERATING A SHORTEST-PATH TREE IN A GRAPH

• US 20160055660A1
• Filed: 08/11/2015
• Published: 02/25/2016
• Est. Priority Date: 08/25/2014
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: YAMANE, Yasuo
• Granted Patent: US 9,892,532 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/0481 based on specific properties of the displayed interaction object or a metaphor-based environment, e.g. interaction with desktop elements like windows or icons, or assisted by a cursor's changing behaviour or appearance
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

An apparatus generates, for each of vertices in a graph represented by the vertices and edges connecting the vertices, a first shortest-path tree rooted at a first root vertex equal to the each vertex, where the first shortest-path tree represents shortest paths from the first root vertex to vertices. The apparatus generates a vertex in the first shortest path tree whose distance from the first root vertex is a natural number of N, based on searching for one or more child vertices of a vertex within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex whose distance from the first root vertex is N−1, where the vertex for searching is included in both the first shortest-path tree and the second shortest-path tree.

Claims

1. A method for causing a computer to execute a process comprising:

generating, for each of vertices in a graph represented by the vertices and edges connecting the vertices, a first shortest-path tree rooted at a first root vertex that is equal to the each vertex in the graph, the first shortest-path tree representing shortest paths from the first root vertex to vertices, a path between two vertices being a sequence of edges connecting a sequence of adjacent vertices through which the two vertices are connected to each other, a length of the path being a number of edges included in the path, a shortest path between the two vertices being a path whose length is smallest among all paths between the two vertices, a distance between the two vertices being a length of the shortest path between the two vertices, wherein

the generating a vertex in the first shortest path tree whose distance from the first root vertex is a natural number of N is performed based on searching for one or more child vertices of a vertex within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex whose distance from the first root vertex is N−

1, and the vertex for searching is included in both the first shortest-path tree and the second shortest-path tree.

2. The method of claim 1, further comprising:

assigning, to each of the vertices constituting the shortest-path tree, an attribute indicating a corresponding vertex that is included in the second shortest-path tree; and

when a vertex in the first shortest-path tree whose distance from the first root vertex is N is generated, setting the attribute at a value indicating the corresponding vertex in the second shortest-path tree.

3. The method of claim 1, wherein,

in a case where the graph is an unweighted directed graph, the second root vertex adjacent to the first root vertex is a vertex into which an edge going out of the first root vertex goes.

4. The method of claim 1, wherein,

in a case where the graph is an unweighted undirected graph, the second root vertex adjacent to the first root vertex is a vertex that is connected with the first root vertex via an edge.

5. The method of claim 2, wherein

a first type of object indicating attributes of a vertex in the graph and a second type of object indicating attributes of a vertex within a shortest-path tree in the graph are managed in association with each other.

6. The method of claim 5, wherein

the first type of object includes, as the attributes, an identifier of a vertex in the graph, information on vertices adjacent to the vertex identified by the identifier, a depth of an already generated shortest-path tree whose root is the vertex identified by the identifier, information on the second type of object corresponding to the first type of object, which indicates the root vertex of the shortest path tree, information on vertices included in the already generated shortest-path tree, and information on vertices, for each distance from the vertex identified by the identifier, which are included in the already generated shortest-path tree;

and

the second type of object includes, as the attributes, information on a vertex associated with the second type of object, information on a parent vertex and child vertices of the vertex within the shortest-path tree, and the attribute indicating the corresponding vertex included in the second shortest-path tree.

7. An apparatus comprising:

a processor configured to generate, for each of vertices in a graph represented by the vertices and edges connecting the vertices, a first shortest-path tree rooted at a first root vertex that is equal to the each vertex in the graph, the first shortest-path tree representing shortest paths from the first root vertex to vertices, a path between two vertices being a sequence of edges connecting a sequence of adjacent vertices through which the two vertices are connected to each other, a length of the path being a number of edges included in the path, a shortest path between the two vertices being a path whose length is smallest among all paths between the two vertices, a distance between the two vertices being a length of the shortest path between the two vertices, wherein

the generating a vertex in the first shortest path tree whose distance from the first root vertex is a natural number of N is performed based on searching for one or more child vertices of a vertex within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex whose distance from the first root vertex is N−

1, and the vertex for searching is included in both the first shortest-path tree and the second shortest-path tree; and

a memory coupled to the processor, the memory being configured to store information on the shortest-path trees.

8. The apparatus of claim 7, wherein

the processor assigns, to each of the vertices constituting the shortest-path tree, an attribute indicating a corresponding vertex that is included in the second shortest-path tree;

and

when a vertex in the first shortest-path tree whose distance from the first root vertex is N is generated, the processor sets the attribute at a value indicating the corresponding vertex in the second shortest-path tree.

9. The apparatus of claim 7, wherein,

in a case where the graph is an unweighted directed graph, the second root vertex adjacent to the first root vertex is a vertex into which an edge going out of the first root vertex goes.

10. The apparatus of claim 7, wherein,

in a case where the graph is an unweighted undirected graph, the second root vertex adjacent to the first root vertex is a vertex that is connected with the first root vertex via an edge.

11. The apparatus of claim 8, wherein

the processor manages a first type of object indicating attributes of a vertex in the graph and a second type of object indicating attributes of a vertex within a shortest-path tree in the graph in association with each other.

12. The apparatus of claim 11, wherein

the first object includes, as the attributes, an identifier of a vertex in the graph, information on vertices adjacent to the vertex identified by the identifier, a depth of an already generated shortest-path tree whose root is the vertex identified by the identifier, information on the second type of object corresponding to the first type of object, which indicates the root vertex of the shortest path tree, information on vertices included in the already generated shortest-path tree, and information on vertices, for each distance from the vertex identified by the identifier, which are included in the already generated shortest-path tree;

and

the second type of object includes, as the attributes, information on a vertex associated with the second type of object, information on a parent vertex and child vertices of the vertex within the shortest-path tree, and the attribute indicating the corresponding vertex included in the second shortest-path tree.

13. A non-transitory, computer-readable recording medium having stored therein a program for causing a computer to execute a process comprising:

generating, for each of vertices in a graph represented by the vertices and edges connecting the vertices, a first shortest-path tree rooted at a first root vertex that is equal to the each vertex in the graph, the first shortest-path tree representing shortest paths from the first root vertex to vertices, a path between two vertices being a sequence of edges connecting a sequence of adjacent vertices through which the two vertices are connected to each other, a length of the path being a number of edges included in the path, a shortest path between the two vertices being a path whose length is smallest among all paths between the two vertices, a distance between the two vertices being a length of the shortest path between the two vertices, wherein

the generating a vertex in the first shortest path tree whose distance from the first root vertex is a natural number of N is performed based on searching for one or more child vertices of a vertex within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex whose distance from the first root vertex is N−

1, and the vertex for searching is included in both the first shortest-path tree and the second shortest-path tree.

14. The non-transitory, computer-readable recording medium of claim 13, wherein the process further includes:

assigning, to each of the vertices constituting the shortest-path tree, an attribute indicating a corresponding vertex that is included in the second shortest-path tree; and

when a vertex in the first shortest-path tree whose distance from the first root vertex is N is generated, setting the attribute at a value indicating the corresponding vertex in the second shortest-path tree.

15. The non-transitory, computer-readable recording medium of claim 13, wherein,

in a case where the graph is an unweighted directed graph, the second root vertex adjacent to the first root vertex is a vertex into which an edge going out of the first root vertex goes.

16. The non-transitory, computer-readable recording medium of claim 13, wherein,

in a case where the graph is an unweighted undirected graph, the second root vertex adjacent to the first root vertex is a vertex that is connected with the first root vertex via an edge.

17. The non-transitory, computer-readable recording medium of claim 14, wherein

a first type of object indicating attributes of a vertex in the graph and a second type of object indicating attributes of a vertex within a shortest-path tree in the graph are managed in association with each other.

18. The non-transitory, computer-readable recording medium of claim 14, wherein

the first type of object includes, as the attributes, an identifier of a vertex in the graph, information on vertices adjacent to the vertex identified by the identifier, a depth of an already generated shortest-path tree whose root is the vertex identified by the identifier, information on the second type of object corresponding to the first type of object, which indicates the root vertex of the shortest path tree, information on vertices included in the already generated shortest-path tree, and information on vertices, for each distance from the vertex identified by the identifier, which are included in the already generated shortest-path tree;

and

the second type of object includes, as the attributes, information on a vertex associated with the second type of object, information on a parent vertex and child vertices of the vertex within the shortest-path tree, and the attribute indicating the corresponding vertex included in the second shortest-path tree.