System and methods for optimizing networks of weighted unweighted directed graphs

A method, executing on a data processing system having a controller and a memory, for optimizing a recognition network, the recognition network comprising a plurality of nodes and a plurality of transitions connecting the nodes, comprising:

• determining, for each of at least some of the nodes, shortest distances to at least one other node;
• and
• reweighting at least some of the plurality of nodes and the plurality of transitions based on the determined shortest distances,
• wherein said determining comprises determining single-source shortest distances from each of at least some of the nodes,
• wherein determining the single-source shortest distances from each of at least some of the nodes comprises:
• selecting a source node “s”;
• defining a destination array “d” and a total weight array “r”;
• defining a queue “S”;
• selecting a strongly connected component “X” of the recognition network in a topological order;
• for each selected strongly connected component “X”,
• adding each node “q” of the selected strongly connected component “X” to the queue “S”;
• extracting a node “q” from the queue “S”;
• relaxing, for each transition extending from the extracted node “q”, the departing edges “e” of the extracted node “q”, and
• repeating the extracting and relaxing steps until the queue “S” is empty;
• and
• repeating the topological order selecting step until each strongly connected component “X” has been selected.

A method, executing on a data processing system having a controller and a memory, for optimizing a recognition network, the recognition network comprising a plurality of nodes and a plurality of transitions connecting the nodes, comprising:

• determining, for each of at least some of the nodes, shortest distances to at least one other node;
• and
• reweighting at least some of the plurality of nodes and the plurality of transitions based on the determined shortest distances,
• wherein determining, for each of at least some of the nodes, shortest distances to at least one other node comprises:
• determining if at least one of the plurality of nodes and the plurality of transitions of the recognition network have been weighted;
• and
• if the plurality of nodes and the plurality of transitions of the recognition network have not been weighted, arbitrarily weighting the transitions of the recognition network.

A method, executing on a data processing system having a controller and a memory, for optimizing a recognition network, the recognition network comprising a plurality of nodes and a plurality of transitions connecting the nodes, comprising:

• determining, for each of at least some of the nodes, shortest distances to at least one other node;
• and
• reweighting at least some of the plurality of nodes and the plurality of transitions based on the determined shortest distances,
• wherein reweighting at least some of the plurality of nodes and the plurality of transitions based on the determined shortest distances comprises:
• selecting a source node toward which at least some of the plurality of nodes and the plurality of transitions will be reweighted;
• selecting a destination node of the recognition network as a current node;
• identifying at least one transition directly connected to the current node and on a path between the source node and destination node;
• selecting one of the at least one identified transitions;
• determining if an other node connected to the selected transition was previously reweighted;
• if the other node was not previously weighted:
• adding a current weight of a transition connecting the current node and the other node to the other node, and
• resetting the weight of the transition connecting the current node and the other node to a predetermined value;
• if the other node was previously weighted, resetting the weight of the transition connecting the current node and the other node based on the current weight of the transition, a weight of the current node and a weight of the other node;
• repeating the selecting, determining adding and resetting steps for each identified transition;
• selecting another node on a path between the source node and the destination node as the current node;
• and
• repeating the identifying, transition selecting, determining, adding, resetting and node selecting steps until each transition on each path between the source node and the destination node has been selected.

A method, executing on a data processing system having a controller and a memory, for reweighting a weighted directed graph stored in the memory, comprising:

• selecting a node of the weighted directed graph;
• determining at least one path extending from the selected node in a pushing direction;
• and
• pushing a weight of at least one transition of the at least one determined path onto at least one node of the at least one determined path,
• wherein:
• determining at least one path comprises determining at least one node directly connected to the selected node in the pushing direction;
• and
• pushing at least one weight comprises:
• for each determined node, if that node does not have a weight pushed onto it:
• pushing a weight of a transition directly connecting that node to the selected node on to that node, and
• setting the weight of that transition to a predetermined value, and
• for each determined node, if that node has a weight pushed onto it, modifying the weight of that transition based on a weight of that node, a weight of the selected node, and the unmodified weight of that transition.

A method, executing on a data processing system having a controller and a memory, for reweighting a weighted directed graph stored in the memory, comprising:

• selecting a node of the weighted directed graph;
• determining at least one path extending from the selected node in a pushing direction;
• and
• pushing a weight of at least one transition of the at least one determined path onto at least one node of the at least one determined path,
• wherein pushing at least one weight comprises:
• determining a single source shortest distance from the selected node to each other node of the directed graph in the pushing direction;
• pushing, for each other node of the directed in the pushing direction, the single source shortest distance for that node onto that node;
• and
• reweighting each transition of each path based on an original weight of that transition and weights of the nodes connected by that transition.

A reweighting system that reweighs a recognition network having a plurality of nodes and a plurality of transitions connecting the nodes, comprising:

• a controller;
• a memory that stores the recognition network;
• a shortest distance determining circuit that determines for each of at least some of the nodes, shortest distances to at least one other node;
• and
• a weight pushing circuit that reweights at least some of the plurality of nodes and the plurality of transitions based on the determined shortest distances,
• further comprising a weight assigning circuit that assigns arbitrary weights to the transitions of an unweighted recognition network.

A method, executing on a data processing system having a controller and a memory, the memory storing a directed graph comprising a plurality of nodes and a plurality of transitions connecting the nodes, for determining, for each of at least some of the nodes, single-source shortest distances from each of at least some of the nodes, comprising:

• selecting a source node “s”;
• defining a destination array “d” and a total weight array “r”;
• defining a queue “S”;
• adding the source node “s” to the queue “S”;
• extracting a node “q” from the queue “S”;
• relaxing, for each transition extending from the extracted node “q”, the departing edges “e” of the extracted node “q”;
• and
• repeating the extracting and relaxing steps until the queue “S” is empty.