Data processing: vehicles – navigation – and relative location – Navigation – Determination of travel data based on the start point and...
Reexamination Certificate
2000-04-27
2003-10-21
Camby, Richard M. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Determination of travel data based on the start point and...
C709S239000
Reexamination Certificate
active
06636800
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The Present invention is directed to a computer-assisted processing of a graph that comprises nodes and edges.
2. Description of the Related Art
A fast, computer-assisted determination of the shortest paths in directed or undirected graphs is required in the greatest variety of computer-assisted applications.
A number of methods for determining shortest paths are known for this purpose. An overview of known methods, for example the Moore/Pape method or of the Dijkstra algorithm as well, may be found in B. V. Cherkassky et al., Shorest Path Algorithm, Theory and Experimental Evaluation. A corresponding method, however, includes the disadvantage that nearly all nodes of the graph must be taken into consideration given start and destination nodes lying far apart in order to identify the shortest path between a prescribed starting part and a prescribed destination point.
H. P. Canibol and E. Muller, Schoner fahren, focus and P. Robke-Doerr, Pfad-Finder disclose a computer-assisted navigation system in a motor vehicle. Maps are stored in a memory of the navigation system, whereby individual locations on the map (for example, houses, railroad stations, points of interest, etc.) are represented by nodes of a graph. The connections between the locations (streets, paths, etc.) are represented by edges of the graph. The shortest or, respectively, fastest path between the starting position and the target position is determined in the navigation system for a predetermined starting position and a predetermined target position upon employment of a method for determining shortest paths.
DE 195 13 960 A1 discloses a method for imaging a graph in a memory on the basis of a plurality of depth and width searches in differing direction.
DE 196 06 010 A1 discloses a location data bank for the determination of routes within a traffic route network.
What is to be understood below by a shortest path is the cheapest path under a predetermined cost function on the edges of a graph (for example, geographical length, anticipated travel time, etc.)
The known navigation system exhibits the disadvantage that an optimized route, i.e. the shortest path between the starting position and the target position, can only be determined given extremely high calculating outlay, so that considerable computer performance must be made available given a fast processing of an order for route determination, as a result whereof the navigation system is rather expensive.
In some applications, an extremely great number of shortest paths must be identified in a predetermined network, as a result whereof the criterion of a fast determination of shortest paths acquires even significantly more significance.
Given centralized systems, a central server must service a plurality of inquires for route determination from a plurality of client navigation systems and must be able to rapidly determine a great number of shortest paths for this purpose.
SUMMARY OF THE INVENTION
The present invention is thus based on the problem of processing a graph that comprises nodes and edges such that a determination of a shortest path becomes possible faster than is possible with known methods.
The problem is solved by the method for computer-assisted processing of a graph that has nodes and edges, whereby the graph describes a structure of a technical system,
whereby the nodes are grouped into at least two regions,
whereby the following steps are implemented for each region and for at least some of the nodes of the region;
a) one node is selected as root node;
b) a tree of shortest paths is determined for the root node in the graph with the root node as root of the tree;
c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
The invention also provides an arrangement for computer-assisted processing of a graph that has nodes and edges, having a processor unit that is configured such that
the nodes are grouped into at least two regions;
the following steps are implemented for each region and for at least some of the nodes of the region:
a) one node is selected as root node;
b) a tree of shortest paths is determined for the root node in the graph having the root node as root of the tree;
c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
A graph that comprises nodes and edges is processed in the method. The nodes of the graph are grouped into at least two regions. The following steps are implemented for each region and for at least some of the nodes:
a) one node is selected as a root node;
b) a tree of shortest paths in the graph with the the root node as root of the tree is determined for the root node;
c) a node of an edge of the graph is then marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
The arrangement for processing a graph that comprises nodes and edges contains a processor unit that is configured such that the following steps are implemented for each region and for at least some of the nodes of the region that are grouped into at least two regions:
a) a node is selected as the root node;
b) a tree of shortest paths in the graph with the root node as the root of the tree is determined for the root node;
c) a node of an edge of the graph is marked for the region when, proceeding from the node to the root node, the edge is contained in a shortest path to the root node.
The shortest path can be contained in the tree of shortest paths or can be contained in a further shortest path to the root node that is not in the tree of shortest paths.
Due to this extremely simple type of pre-processing of a graph, a considerable enhancement of the determination speed of a shortest path is achieved in the determination of shortest paths in the processed graph.
Any desired method for determining shortest paths, for example the Moore/Pape method or the Dijkstra algorithm as well in the respective application, bidirectionally and well, with or without target alignment via remaining path length estimation or any other method for determining shortest paths can be utilized for calculating the shortest paths in the respective application as well as in the pre-processing, i.e. in the method for processing the graph.
The substantial saving in calculating time in the determination of shortest paths as a result of the pre-processing of the invention also makes it possible to equip the navigation system with substantially less computer power, so that the costs of the navigation system can be substantially reduced.
Developments of the invention provide that the method steps a) through c) are implemented for all nodes of the respective region. The marking ensues by allocation of a binary value to the node in the edge of the respective region. The nodes are grouped into a plurality of regions in one embodiment. In a preferred development, a shortest path between a predetermined starting node and a predetermined target node is determined upon employment of the marked nodes. Specifically, the following steps are implemented for determining the shortest path between the starting node and the target node: a starting region is determined and stored, the starting node being grouped thereto; a target region is determined and stored, the target node being grouped thereto; only those edges are taken into consideration in the determination of the shortest path proceeding from the starting node for which the following is valid; a first node of the edge is marked for the target region proceeding from the starting node in the starting region, and a second node of the edge is marked for the starting region proceeding from the starting node in the starting region. In further detail, the following steps are implemented for the determination of the shortest path between the starting node and the target node: only those edges for which
Enders Reinhard
Lauther Ulrich
Camby Richard M.
Staas & Halsey , LLP
LandOfFree
Method and device for computer assisted graph processing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for computer assisted graph processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for computer assisted graph processing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3174130