Apparatus and method for generating a shortest-path tree in a graph

• US 9,892,532 B2
• Filed: 08/11/2015
• Issued: 02/13/2018
• Est. Priority Date: 08/25/2014
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Yamane, Yasuo
• Primary Examiner(s): Merouan, Abderrahim
• Application Number:
  US14/823,380
• Publication Number:
  US 20160055660A1
• Time in Patent Office: 917 Days
• 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 at least one processor to execute a process comprising:

generating, for each of vertices in a graph that is configured to represent relationships between pieces of data represented by the vertices and edges connecting the vertices so as to cause the data to be searched for by using the graph, a shortest-path tree rooted at a root vertex that is equal to each vertex in the graph so that end-point vertices of each shortest path tree, whose distance from the root vertex is an integer of n equal to or greater than 0, are generated at a same time, the end-point vertex being a vertex positioned at an end point of a shortest path starting from the root vertex,

the shortest-path tree representing shortest paths from the root vertex to all the end-point 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

generation of a distance N vertex among first vertices in a first shortest path tree, whose distance from a first root vertex is a natural number of N greater than 1 and which is adjacent to a distance N−

1 vertex among the first vertices of the first shortest-path tree, whose distance from the first root vertex is N−

1, is performed based on searching for zero or more child vertices of a second vertex corresponding to the distance N−

1vertex of the first shortest path tree within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex, which is located on the shortest path from the first root vertex to the distance N−

1 vertex.

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 that is configured to represent relationships between pieces of data represented by the vertices and edges connecting the vertices so as to cause the data to be searched for by using the graph, a shortest-path tree rooted at a root vertex that is equal to each vertex in the graph so that end-point vertices of each shortest path tree, whose distance from the root vertex is an integer of n equal to or greater than 0, are generated at a same time, the end-point vertex being a vertex positioned at an end point of a shortest path starting from the root vertex,

the shortest-path tree representing shortest paths from the root vertex to all the end-point 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

generation of a distance N vertex among first vertices in a first shortest path tree, whose distance from a first root vertex is a natural number of N greater than 1 and which is adjacent to a distance N−

1 vertex among the first vertices of the first shortest-path tree, whose distance from the first root vertex is N−

1, is performed based on searching for zero or more child vertices of a second vertex corresponding to the distance N−

1vertex of the first shortest path tree within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex, which is located on the shortest path from the first root vertex to the distance N−

1 vertex.

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 that is configured to represent relationships between pieces of data represented by the vertices and edges connecting the vertices so as to cause the data to be searched for by using the graph, a shortest-path tree rooted at a root vertex that is equal to each vertex in the graph so that end-point vertices of each shortest path tree, whose distance from the root vertex is an integer of n equal to or greater than 0, are generated at a same time, the end-point vertex being a vertex positioned at an end point of a shortest path starting from the root vertex,

the shortest-path tree representing shortest paths from the root vertex to all the end-point 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

generation of a distance N vertex among first vertices in a first shortest path tree, whose distance from a first root vertex is a natural number of N greater than 1 and which is adjacent to a distance N−

1 vertex among the first vertices of the first shortest-path tree, whose distance from the first root vertex is N−

1, is performed based on searching for zero or more child vertices of a second vertex corresponding to the distance N−

1vertex of the first shortest path tree within a second shortest-path tree rooted at a second root vertex adjacent to the first root vertex, which is located on the shortest path from the first root vertex to the distance N−

1 vertex.

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.