Method and device for computer assisted graph processing
AssigneeSiemens Aktiengesellschaft
InventorsUlrich Lauther, Reinhard Enders
Life of this patent
Estimating the term…
Abstract
Nodes of a graph 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 respective region: a) one node is selected as a root node; b) a tree of shortest paths is determined for the root node in the graph having the a 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.
Claims18
A method for computer-assisted processing of a graph that includes nodes and edges, whereby the graph describes a structure of a technical system, comprising the steps of:
- grouping the nodes into at least two regions,
- implementing the following steps for each of said at least two regions and for at least some of the nodes of the region;
- a) selecting one node as a root node;
- b) determining a tree of shortest paths for the root node in the graph with the root node as a root of the tree;
- and
- c) marking a node of an edge of the graph for the region when the edge is contained in a shortest path to the root node proceeding from the node to the root node.
An arrangement for computer-assisted processing of a graph that includes nodes and edges, comprising:
- a processor unit that is configured such that
- the nodes are grouped into at least two regions;
- the following steps are implemented for each of said at least two regions and for at least some of the nodes of the region:
- a) one node is selected as a root node;
- b) a tree of shortest paths is determined for the root node in the graph having the root node as a 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.
An arrangement for determining a shortest path between a starting node and a target node in a graph that includes nodes and edges, the graph describing a structure of a technical system, comprising:
- a processor unit in said arrangement that is configured such that the shortest path is determined upon employment of graphs that are processed according to the following steps:
- 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 a root node;
- b) a tree of shortest paths is determined for the root node in the graph having the root node as a root of the tree;
- and
- c) a node of an edge of the graph is marked for the region when the edge is contained in a shortest path to the root node proceeding from the node to the root node.
Dependencies are inferred from the claim text.