Patent ID: 7356480

Claim:
A method of data transformation via efficient path discovery using a digraph, the method comprising: providing at least two input files to be transformed using a digraph: providing in said digraph including a plurality of ordinary nodes, at least one of a composition node and a decomposition node, and a plurality of arcs interconnecting any of said nodes, a source node s connected to a set S of source nodes in said digraph via outgoing arcs of zero cost, wherein any of said composition nodes represents a transformation of at least two inputs to said composition node into one output from said composition node, wherein all of said inputs are required for said transformation to occur, and wherein each of said inputs includes different data: initializing to zero a cumulative cost of the path to s; providing a composition node tâ€² connected to a set T of target nodes in said digraph via incoming arcs of zero cost; providing a target node t connected to composition node tâ€² via an incoming arc of zero cost; defining a set W of nodes in said digraph initially including only node s; defining a set V of all nodes in said digraph; determining the cumulative costs of the paths to all nodes y in V that are connected to node s by an arc; while W<>V: selecting a node x in V from all nodes in V that are not in W whose cumulative cost is minimal; adding node x to W; for each node y in V to which x has an outgoing arc: if y is not a composition node, determining the cumulative cost of the path to y as the lesser of a) the current known cumulative cost of the path to y, and b) the cumulative cost of the path to x plus the cost of the arc connecting x to y; if y is a composition node, and all nodes that have outgoing arcs to y are in W, determining the cumulative cost of the path to y as the lesser of a) the current known cumulative cost of the path to y, and b) the sum of the cumulative costs of the paths to all nodes that have outgoing arcs to y; determining a path from S to T as comprising the arcs whose cost was added to the final cumulative costs of the nodes of T; and providing an output file constructed by transforming said input files according to transformations represented by said nodes along said path from S to T in said digraph.