ROUTING INFORMATION PROCESSING METHOD, COMPUTER PROGRAM, AND SYSTEM

• US 20140320515A1
• Filed: 04/11/2014
• Published: 10/30/2014
• Est. Priority Date: 04/30/2013
• Status: Abandoned Application

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Yanagisawa, Hiroki
• Application Number:
  US14/250,554
• Publication Number:
  US 20140320515A1
• Time in Patent Office: Days
• US Class Current: 345/589
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G01C 21/3841 Data obtained from two or more sources, e.g. probe vehicles
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

Routing information processing method, computer program, and system. A method for processing routes in a graph, the method including coloring vertices in the graph in such a manner that a condition N_P>N_C is satisfied, wherein a number of vertices in the graph is represented by N_P and a number of colors assigned to the vertices is represented by N_C, and wherein a series of colors assigned to the vertices is identified uniquely, the series of colors representing a series of vertices corresponding to each of the routes; and storing a series of vertices corresponding to a route as a series of colors assigned to the vertices into the storing means.

Claims

1. A method for processing routes in a graph, the method comprising:

coloring vertices in the graph in such a manner that a condition N_P>

N_C is satisfied, wherein a number of vertices in the graph is represented by N_P and a number of colors assigned to the vertices is represented by N_C, and wherein a series of colors assigned to the vertices is identified uniquely, the series of colors representing a series of vertices corresponding to each of the routes; and

storing a series of vertices corresponding to a route as a series of colors assigned to the vertices.

2. The method according to claim 1, wherein the vertices in the graph are colored in such a manner that at least one of c(u)≠

c(u′

) and c(v)≠

c(v′

) is satisfied for two edges (u,v) and (u′

,v′

) in the graph, wherein c(x) represents a color assigned to a vertex x.

3. The method according to claim 1, wherein the vertices in the graph are colored based on a greedy algorithm.

4. The method according to claim 1, wherein the vertices in the graph are colored based on a greedy algorithm, while a neighboring vertex that is adjacent to a first vertex and a second vertex that is adjacent to the neighboring vertex are taken into consideration.

5. The method according to claim 1, wherein coloring is based on harmonious coloring.

6. The method according to claim 5, wherein coloring is based on harmonious coloring if the graph is an undirected graph.

7. The method according to claim 5, wherein coloring is based on harmonious coloring if the graph is a directed graph, while the directed graph is treated as an undirected graph.

8. The method according to claim 1, further comprising:

receiving an instruction to search for a route; and

searching for a series of vertices corresponding to the searched route as a series of colors assigned to the vertices.

9. The method according to claim 8,

wherein coloring includes providing attributes of a character string to the vertices in the graph,

wherein storing includes storing the series of colors as a character string, and

wherein searching includes searching for a character string corresponding to the searched route.

10. The method according to claim 1, wherein the routes are routes on a road network in which the vertices correspond to intersections.

11. The method according to claim 10, wherein the routes on the road network are generated from probe car data.

12. A computer program product for processing routes in a graph, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions readable/executable by a device to cause the device to perform a method comprising:

coloring vertices in the graph in such a manner that a condition N_P>

N_C is satisfied, wherein a number of vertices in the graph is represented by N_P and a number of colors assigned to the vertices is represented by N_C, and wherein a series of colors assigned to the vertices is identified uniquely, the series of colors representing a series of vertices corresponding to each of the routes; and

storing a series of vertices corresponding to a route as a series of colors assigned to the vertices.

13. A system for processing routes in a graph, the system comprising:

a memory;

a processor device communicatively coupled to the memory; and

a module for processing a plurality of routes in a graph coupled to the memory and the processor to carry out the steps of a method comprising;

coloring vertices in the graph in such a manner that a condition N_P>

N_C is satisfied, wherein a number of vertices in the graph is represented by N_P and a number of colors assigned to the vertices is represented by N_C, and wherein a series of colors assigned to the vertices is identified uniquely, the series of colors representing a series of vertices corresponding to each of the routes; and

storing a series of vertices corresponding to a route as a series of colors assigned to the vertices.

14. The system according to claim 13, wherein the vertices in the graph are colored in such a manner that at least one of c(u)≠

c(u′

) and c(v)≠

c(v′

) is satisfied for two edges (u,v) and (u′

,v′

) in the graph, wherein c(x) represents a color assigned to a vertex x.

15. The system according to claim 13, wherein the vertices in the graph are colored based on a greedy algorithm.

16. The system according to claim 13, wherein the vertices in the graph are colored based on a greedy algorithm, while a neighboring vertex that is adjacent to a first vertex and a second vertex that is adjacent to the neighboring vertex are taken into consideration.

17. The system according to claim 13, wherein coloring is based on harmonious coloring.

18. The system according to claim 17, wherein coloring is based on harmonious coloring if the graph is an undirected graph.

19. The system according to claim 13, further comprising:

receiving an instruction to search for a route; and

searching for a series of vertices corresponding to the searched route as a series of colors assigned to the vertices.

20. The system according to claim 13, wherein the routes are routes on a road network in which the vertices correspond to intersections.