DETAILED ACTION
This Action is in response to Applicant’s amendment filed on 08/08/25.
Claims 1-6 and 16 have been amended.
Claims 1-20 are pending.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Response to Arguments
Argument A) – The applicant argues, in regards to the 103 rejection of claim 1, that the cited references fail to disclose the limitations “determining…flows respectively for edges of the network graph” based on “resolving a linear system of weights associated with edges…over a reduced network graph….” and “propagating a solution of the linear system…” (see applicant’s remarks; pages 8 and 9).
Response to argument A) - The examiner submits that the applicant’s arguments do not constitute a complete reply to the office action, and therefore do not comply with 37 CFR 1.111 (b) and (c) because they do not specifically point out how the language of the claim patentably distinguishes it from the references and do not clearly point out the patentable novelty which he or she thinks the claim presents in view of the state of the art disclosed by the references. Further, the arguments do not show how the amendments avoid such references.
In particular, the applicant merely recites the limitations of the claim and then states that the reference(s) fail to disclose the limitations without specifically pointing out the differences between the claim limitations and the reference. Therefore, the examiner submits the references do in fact disclose the limitations, as shown in the maintained rejection below.
Argument B) – The applicant’s arguments with respect to the 103 rejection of claim 16 (see applicant’s remarks; page 9) have been considered but are moot because the new ground of rejection does not rely on any reference applied in the prior rejection of record for any teaching or matter specifically challenged in the argument.
In particular, the examiner has introduced Vliegen to disclose the amended limitation “determining, based on a flow induced in the candidate subgraph by the load, the flow induced in the candidate subgraph recovered using at least one interpolation transform of the plurality of interpolation transforms, at least one alternative path”, as shown in the rejection below.
Argument C) – The applicant argues, in regards to the 103 rejection of claim 20, that the cited references fail to disclose the limitations “determining, based on flows induced in the plurality of reduced subgraphs by the equivalent load, a candidate subgraph of the network graph comprising a plurality of alternative paths, wherein the flows are recovered using a plurality of interpolation transforms respectively associated with the plurality of reduced subgraphs.” (see applicant’s remarks; page 10).
Response to argument C) - The examiner submits that the applicant’s arguments do not constitute a complete reply to the office action, and therefore do not comply with 37 CFR 1.111 (b) and (c) because they do not specifically point out how the language of the claim patentably distinguishes it from the references and do not clearly point out the patentable novelty which he or she thinks the claim presents in view of the state of the art disclosed by the references. Further, the arguments do not show how the amendments avoid such references.
In particular, the applicant merely recites the limitations of the claim and then states that the reference(s) fail to disclose the limitations without specifically pointing out the differences between the claim limitations and the reference. Therefore, the examiner submits the references do in fact disclose the limitations, as shown in the maintained rejection below.
Further, the applicant states similar arguments for the dependent claims with respect to the above independent claims (see applicant’s remarks; page 10). As such, the same rationale discussed above applies equally as well to the dependent claims.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
Claims 1-5, 8, 11, 12 and 13-15 are rejected under 35 U.S.C. 103 as being unpatentable over Koren et al. (U.S. 7,830,815 B1) in view of Allen (U.S. 10,320,698 B1).
Regarding claim 1, Koren discloses a computer-implemented method for generating alternative network paths, the method comprising:
obtaining, by a computing system comprising one or more processors, a network graph (see Koren; column 4 lines 10-12, 36-39 and column 14 lines 41-42; Koren discloses collecting, i.e. “obtaining”, a graph which represents nodes and edges in a network, i.e. “a network graph”. A system comprising a processor performs the functions, i.e. “by a computing system…”);
determining, by the computing system, flows respectively for edges of the network graph (see Koren; column 4 lines 55-57 and column 14 lines 41-42; Koren discloses network flows refers to a measure of proximity between nodes calculated by assigning a limited capacity to each edge in the network graph, i.e. “determining…flows respectively for edges of the network graph”. The system performs the functions, i.e. “by the computing system…”); and
determining, by the computing system and based on the flows, a plurality of alternative paths across the network graph (see Koren; column 4 lines 61-67 and column 14 lines 41-42; Koren discloses network flows favor high weight edges and captures, i.e. “determining”, the premise that increasing the number of alternative paths, i.e. “determining…based on the flows, a plurality of alternative paths…”, between nodes increases proximity, thereby gaining from the alternative paths. The system performs the functions, i.e. “by the computing system…”).
While Koren discloses “weights associated with edges” (see Koren; column 4 lines 55-62; Koren discloses assigning capacity to each edge proportional to its weight and network flows favoring high weight edges), as well as, analysis on sub-graphs (see Koren; column 3 lines 43-47), Koren does not explicitly disclose a network graph comprising a plurality of subgraphs; resolving a linear system of weights associated with the edges, the linear system resolved over a reduced network graph comprising an equivalent subgraph obtained using a node elimination transform to eliminate an interior node of a subgraph of the plurality of subgraphs; and propagating a solution of the linear system into a respective partition of a plurality of partitions of the network graph to determine at least one of the flows within the respective partition.
In analogous art, Allen discloses a network graph comprising a plurality of subgraphs (see Allen; column 6 lines 61-64; Allen discloses dividing, the graph into smaller subgraphs, i.e. “a plurality of subgraphs”);
resolving a linear system of weights associated with the edges, the linear system resolved over a reduced network graph (see Allen; column 3 lines 10-14, 63-65, column 11 lines 61-61; Allen discloses constructing a network graph such that each edge between two nodes is weighted, i.e. “weights associated with the edges”, then solving, i.e. “resolving”, a linear system of equations for the network graph based at least in part on reducing the graph by using an appropriate subgraph, i.e. “resolved over a reduced network graph”) comprising an equivalent subgraph obtained using a node elimination transform to eliminate an interior node of a subgraph of the plurality of subgraphs (see Allen; column 3 lines 37-38, column 6 lines 61-67 and column 23 lines 5-14; Allen discloses the placer removes nodes and edges, i.e. “using a node elimination transform”, so that the subgraphs are balanced by cutting between nodes, i.e. “to eliminate an interior node of a subgraph of the plurality of subgraphs”), and
propagating a solution of the linear system into the subgraph to obtain a solution at the interior nodes (see Allen; column 3 lines 63-67, column 6 line 61 – column 7 line 2, column 11 lines 44-51, 61-62 and column 17 lines 40-42; Allen discloses solving the linear system of equations based on a subgraph. In particular, solving individual iterations of the linear equation problem by subdividing the graph into subgraphs. Determining a number of allowed iterations, i.e. “propagating”, to reach a solution for an appropriate subgraph, i.e. “propagating a solution…into a respective partition” to calculate the network flow based distinct paths of the subgraph, i.e. “…to obtain a solution at the interior nodes”).
One of ordinary skill in the art would have been motivated to combine Koren and Allen because they both disclose network graphs, and as such, are within the same environment.
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filling date of the claimed invention, to incorporate solving a linear system of weights for a network graph as taught by Allen into the system of Koren in order to provide the benefit of scalability by allowing solving a system of linear equations for the network graph (see Koren; column 5 lines 24-25) to include the analysis of sub-graphs (see Koren; column 3 lines 43-47) to include solving the linear system of equations based on a subgraph (see Allen; column 3 lines 63-67).
Regarding claim 2, Koren and Allen discloses all the limitations of claim 1, as discussed above, and further the combination of Koren and Allen clearly discloses wherein determining the flows comprises: partitioning, by the computing system, the network graph into the plurality of subgraphs (see Allen; column 6 lines 61-64; Allen discloses a placer, i.e. “the computing system”, dividing, i.e. “partitioning”, the graph into smaller subgraphs); and
generating, by the computing system and using the node elimination transform, a plurality of equivalent subgraphs respectively for the plurality of subgraphs (see Allen; column 3 lines 37-38, column 6 lines 61-67 and column 23 lines 5-14; Allen discloses the placer, i.e. “the computing system”, removes nodes and edges, i.e. “a node elimination transform”, so that the subgraphs are balanced, i.e. “a plurality of equivalent subgraphs…”);
wherein the linear system is resolved over the plurality of equivalent subgraphs (see Allen; column 3 lines 63-65, column 6 lines 61-67 and column 11 lines 61-62; Allen discloses solving a linear system, i.e. “linear system is resolved”, of equations for the network graph based at least in part on reducing the graph by using appropriate balanced subgraphs, i.e. “over the plurality of equivalent subgraphs”).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 1.
Regarding claim 3, Koren and Allen discloses all the limitations of claim 1, as discussed above, and further the combination of Koren and Allen clearly discloses wherein the solution of the linear system describes a load on a boundary of the subgraph (see Allen; column 3 lines 56-65, column 6 lines 61-67 and column 11 lines 61-62; Allen discloses solving a linear system, i.e. “the solution of the linear system”, of equations for the network graph based at least in part on reducing the graph and the edge weight, i.e. “load on a boundary of the subgraph”), the solution at the interior node describes a load on the interior node (see Allen; column 3 lines 56-65, column 6 lines 61-67, column 9 lines 48-53; Allen discloses solving the linear system based on edge weight of a vertex/node in the graph, i.e. “load on the interior node”), and wherein propagating the solution of the linear system into the subgraph to obtain the solution at the interior node comprises interpolating the load on the boundary to the interior node (see Allen; column 3 lines 56-67, column 6 line 61 – column 7 line 2, column 9 lines 48-53, column 11 lines 44-51, 61-62 and column 17 lines 40-42; Allen discloses solving the linear system of equations based on a subgraph. In particular, solving individual iterations using the edge weight, i.e. “load on the boundary to the interior node”, of the linear equation problem by subdividing the graph into subgraphs. Determining a number of allowed iterations, i.e. “propagating”, to reach a solution for an appropriate subgraph, i.e. “propagating the solution…” to calculate the network flow based distinct paths of the subgraph, i.e. “…to obtain a solution at the interior nodes”).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 2.
Regarding claim 4, Koren and Allen discloses all the limitations of claim 1, as discussed above, and further the combination of Koren and Allen clearly discloses wherein a boundary of the subgraph comprises at least two network bottlenecks (see Koren; column 5 lines 6-16; Koren discloses a minimal edge capacity and adding bottlenecks) and wherein generating the equivalent subgraph comprises:
eliminating, by the computing system, and using the node elimination transform, the interior node (see Allen; column 3 lines 37-38, column 6 lines 61-67 and column 23 lines 5-14; Allen discloses the placer, i.e. “the computing system”, removing nodes and its edges, i.e. “the node elimination transform,”, so that the subgraphs are balanced, i.e. “, i.e. “eliminating…the interior node”); and
replacing, by the computing system, the interior node with an equivalent connection directly between the at least two network bottlenecks (see Koren; column 5 lines 6-16; Koren discloses a minimal edge capacity and adding bottlenecks, i.e. “replacing… with an equivalent connection directly between the at least two network bottlenecks”, of multiple pathways. The system performs the functions, i.e. “by the computing system…”).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 3.
Regarding claim 5, Koren and Allen discloses all the limitations of claim 4, as discussed above, and further the combination of Koren and Allen clearly discloses wherein the interior node is eliminated using a star-mesh reduction (see Koren; column 11 lines 36-42; Koren discloses using a numeral reduction, i.e. “star-mesh reduction”, for the nodes of the subgraphs).
Regarding claim 8, Koren and Allen discloses all the limitations of claim 2, as discussed above, further the combination of Koren and Allen clearly discloses wherein the plurality of subgraphs correspond to a hierarchical structure having a plurality of scales (see Allen; column 11 lines 60-62 and column 12 lines 12-17; Allen discloses reducing the subgraphs by which all nodes include a scaled magnitude value, i.e. “hierarchical structure having a plurality of scales”), with one or more subgraphs of the plurality of subgraphs associated with each of the plurality of scales (see Allen; column 11 lines 60-62, and column 12 lines 12-17; Allen discloses all nodes of the subgraphs associated with a scaled magnitude value), and wherein the linear system is resolved in order of decreasing scale (see Allen; column 10 lines 61-65, column 12 lines 12-17 and column 16 lines 38-40; Allen discloses iteratively solving linear system equations with values of the nodes having a scaled magnitude and the values decreasing).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 2.
Regarding claim 11, Koren and Allen discloses all the limitations of claim 1, as discussed above, further the combination of Koren and Allen clearly discloses wherein, for a given fault condition on the network graph, the plurality of alternative paths provide at least one alternative path unbroken by the fault condition (see Koren; column 4 lines 60-67 and column 9 lines 63-65; Koren discloses providing alternative paths based on favoring high weight edges, as well as, unused paths drops, i.e. “fault condition”. In other words, paths with no path drops, i.e. “unbroken by the fault condition”).
Regarding claim 12, Koren and Allen discloses all the limitations of claim 1, as discussed above, further the combination of Koren and Allen clearly discloses wherein determining the plurality of alternative paths comprises: for a plurality of iterations: determining, by the computing system, a candidate path having a flow amount (see Allen; column 4 line 66 – column 5 line 10 and column 17 lines 40-51; Allen discloses a subset of candidate components, e.g. path, for the graph. And the network flow calculated using the bandwidth of the distinct paths, i.e. “a candidate path having a flow amount”); adding, by the computing system, the candidate path to the plurality of alternative paths (see Koren; column 8 lines 10-18; Koren discloses the sum, i.e. “adding”, of the alternative paths with each alternative path growing the number of alternative paths, i.e. “candidate path”); and removing, by the computing system, the flow amount from a total flow (Koren; column 5 lines 3-16- Koren discloses removing the maximal flow in the graph).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 1.
Regarding claim 13, Koren and Allen discloses all the limitations of claim 12, as discussed above, further the combination of Koren and Allen clearly discloses wherein the candidate paths are determined in order of decreasing flow amount (see Allen; column 4 line 66 – column 5 line 10, column 10 lines 61-65, column 12 lines 12-17, column 16 lines 38-40 and column 17 lines 40-51; Allen discloses a subset of candidate components, e.g. path, for the graph. And the network flow calculated using the bandwidth of the distinct paths. Further, iteratively solving linear system equations with values of the nodes having a scaled magnitude and the values decreasing, i.e. “in order of decreasing flow amount”).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 12.
Regarding claim 14, Koren and Allen discloses all the limitations of claim 1, as discussed above, further the combination of Koren and Allen clearly discloses wherein determining the plurality of alternative paths comprises: determining, by the computing system, a candidate subgraph comprising one or more flows greater than a threshold (see Koren; column 13 lines 38-49; Koren discloses the most probable path flows are determined by a threshold, i.e. “one or more flows greater than a threshold”. Pruning edges in a neighborhood of the graph is based on a shortest path of the flow. The pruned neighborhood is taken as the candidate sub-graph); and
for a plurality of iterations: determining, by the computing system, a candidate path through the candidate subgraph having costs respectively associated with one or more path segments along the candidate path (see Allen; column 4 line 66 – column 5 line 10 and column 17 lines 40-51; Allen discloses a subset of candidate components, e.g. path, for the graph. And the network flow calculated using the bandwidth, i.e. “costs respectively associated with one or more path segments”, of the distinct paths);
adding, by the computing system, the candidate path to the plurality of alternative paths (see Koren; column 4 lines 58-64 and column 8 lines 10-18; Koren discloses the sum, i.e. “adding”, of the alternative paths with each alternative path growing the number of alternative paths, i.e. “candidate path”); and
increasing, by the computing system, the costs (see Koren; column 4 lines 58-64; Koren discloses determining the max units to be delivered from node to node and increasing the number of alternative paths increases the proximity; i.e. “increasing… the cost”. In other words, the cost to deliver the units increases as the proximity between the nodes increases).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 1.
Regarding claim 15, Koren and Allen discloses all the limitations of claim 1, as discussed above, further the combination of Koren and Allen clearly discloses wherein the candidate paths are determined in order of increasing cost (see Koren; column 4 lines 58-64; Koren discloses determining to increase the number of alternative paths increases the proximity; i.e. “increasing… the cost” to deliver the units from node to node. In other words, “in order of increasing cost” by the proximity increasing and therefore the distance between each node).
Claims 6 and 7 are rejected under 35 U.S.C. 103 as being unpatentable over Koren et al. (U.S. 7,830,815 B1) in view of Allen (U.S. 10,320,698 B1), as applied to claims 2 and 4 above, and further in view of Noon (U.S. 2013/0187941 A1).
Regarding claim 6, Koren and Allen disclose all the limitations of claim 1, as discussed above. While Koren discloses analysis of the sub-graphs (see Koren; column 3 lines 43-47), the combination of Koren and Allen does not explicitly disclose recovering, by the computing system, one or more flows within at least one subgraph of the plurality of subgraphs using an interpolation transform; and wherein the interpolation transform provides a flow mapping to the at least one subgraph from at least one equivalent subgraph respectively corresponding to the at least one subgraph.
In analogous art, Noon discloses recovering, by the computing system, one or more flows within the subgraph using an interpolation transform (see Noon; paragraphs 0189, 0107 and 0244; Noon discloses a graph includes two or more subgraphs and generating commands to shade, e.g. color, all nodes associated with a first subgraph and a second subgraph i.e. “plurality of subgraphs”. Edge coloring for the nodes is generated by interpolating, i.e. “interpolation transform”, two colors of the nodes, for each subgraph, that the edge connects. The graph includes a distance, i.e. “flow”, for the nodes that is of bounded degree); and
wherein the interpolation transform provides a flow mapping to the subgraph from the equivalent subgraph (see Noon; paragraphs 0189, 0107 and 0244; Noon discloses a graph includes two or more subgraphs and generating commands to shade, e.g. color, all nodes associated with a first subgraph and a second subgraph i.e. “plurality of subgraphs”. Edge coloring for the nodes is generated by interpolating, i.e. “interpolation transform”, two colors of the nodes, for each subgraph, that the edge connects. The graph includes a distance for the nodes that is of bounded degree. In other words, a plurality of interpolating of coloring is done, via the generated commands that an edge connects for each subgraph, i.e. “a flow mapping to the subgraph from the equivalent subgraph”, which is of a bounded agree).
One of ordinary skill in the art would have been motivated to combine Koren, Allen and Noon because they both disclose network graphs, and as such, are within the same environment.
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filling date of the claimed invention, to incorporate Noon’s interpolation into the combined system of Koren and Allen in order to provide the benefit of an improved user experience by allowing the user to understand the different regions of a graph via aesthetically pleasing edge coloring (see Noon; paragraph 0244).
Regarding claim 7, Koren, Allen and Noon disclose all the limitations of claim 6, as discussed above, and further the combination of Koren, Allen and Noon clearly discloses wherein the interpolation transform is precomputed (see Noon; 0244; Noon discloses he interpolation is automatically generated, and therefore is “precomputed”).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 6.
Claim 9 is rejected under 35 U.S.C. 103 as being unpatentable over Koren et al. (U.S. 7,830,815 B1) in view of Allen (U.S. 10,320,698 B1), as applied to claims 2 and 4 above, and further in view of Mubarek et al. (U.S. 2021/0095975 A1).
Regarding claim 9, Koren and Allen disclose all the limitations of claim 1, as discussed above. While Koren discloses a “network graph”, as discussed above, the combination of Koren and Allen does not explicitly disclose wherein the network graph corresponds to a road system.
In analogous art, Mubarek discloses wherein the network graph corresponds to a road system (see Mubarek; paragraph 0029; Mubarek discloses a road network graph, i.e. “road system”).
One of ordinary skill in the art would have been motivated to combine Koren, Allen and Mubarek because they both disclose network graphs, and as such, are within the same environment.
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filling date of the claimed invention, to incorporate Mubarek’s road network graph into the combined system of Koren and Allen in order to provide the benefit of scalability by allowing measuring proximity between nodes in a network (see Koren; column 3 lines 39-42) to include a road network to detect the relative distance between vehicles of the road network (see Mubarek; paragraph 0068).
Regarding claim 10, Koren, Allen and Mubarek disclose all the limitations of claim 9, as discussed above, and further the combination of Koren, Allen and Mubarek clearly discloses wherein the flows correspond to traffic flows (see Mubarek; paragraph 0078; Mubarek discloses a roadway graph uses information to inform pathing algorithms to indicate traffic conditions along the roadway, i.e. “flows correspond to traffic flows”).
The prior art used in the rejection of the current claim is combined using the same motivation as was applied in claim 9.
Claims 16-19 are rejected under 35 U.S.C. 103 as being unpatentable over Koren et al. (U.S. 7,830,815 B1) in view of Noon (U.S. 2013/0187941 A1), and further in view of Vliegen et al. (U.S. 2021/0326387 A1).
Regarding claim 16, Koren discloses a system for generating alternative network paths, the system comprising: one or more processors (see Koren; column 14 lines 41-42; Koren discloses the system comprises a processor); and
one or more memory devices storing non-transitory computer-readable instructions that are executable to cause the one or more processors to perform operations (see Koren; column 14 lines 55-58; Koren discloses a memory executed by a processor to implement functions), the operations comprising:
obtaining a network graph comprising a plurality of nodes and a plurality of edges disposed therebetween (see Koren; column 4 lines 10-12 and 36-39; Koren discloses collecting, i.e. “obtaining”, a graph which represents nodes and edges in a network, i.e. “a network graph comprising a plurality of nodes and a plurality of edges”); and
determining a plurality of reduced subgraphs respectively corresponding to a plurality of subgraphs of the network graph, a respective reduced subgraph comprising one or more boundary nodes of a respective subgraph (see Koren; column 9 lines 4-13, column 10 lines 58-63 and column 13 lines 12-14; Koren discloses smaller sub-graphs with fewer than 30 nodes, i.e. “determining a plurality of reduced subgraphs corresponding to…subgraphs of the network graph”, of the larger graph, i.e. “network graph”. Paths are merged without exceeding a fixed bound on the number of nodes, i.e. “one or more boundary nodes of the respective subgraph”. In particular, reducing to find a sub-graph, i.e. “a respective subgraph”, by transforming edge weights with a value for a node that is a provable lower bound);
obtaining a query indicating a load on the network graph corresponding to a source and a sink (see Koren; column 4 lines 37-41 and 55-59; Koren discloses graphs contain source nodes, i.e. “source”, and terminal nodes, i.e. “sink”. The network flow refers to a measure of proximity between nodes, e.g. source and terminal, calculated by assigning a limited capacity to each edge in the network, one proportional to its weight, and then determining, based on the request for the measure, i.e. “obtaining a query…”, the maximal number of units that may be delivered from node to node, i.e. “…indicating a load on the network graph”);
determining, based on the load, an equivalent load on the plurality of reduced subgraphs (see Koren; column 4 lines 58-61, column 5 lines ; Koren discloses determining the maximal number of units that may be delivered, i.e. “load”, from node to node. This maximal flow may then be taken as a measure, i.e. “based on the load”, of node to node proximity and then determining the same maximal flow between the two graphs, i.e. “reduced subgraphs”);
determining, based on flows induced in the plurality of reduced subgraphs by the equivalent load, a candidate subgraph of the network graph comprising a plurality of alternative paths (see Koren; column 4 lines 55-67, column 8 lines 10-12, 42-45, column 13 lines 4-10, 48-49 and column 13 line 66 – column 14 line 7; Koren discloses determining the maximal number of units that may be delivered, i.e. “…equivalent load”, from node to node and network flows favor high weight edges and capture the premise that increasing the number of alternative paths, i.e. “determining, based on the flows…”, between nodes increases proximity, thereby gaining from the alternative paths and the subgraph is induced, i.e. “…induced in the plurality of reduced subgraphs”, to determine a candidate sub-graph, i.e. “a candidate subgraph of the network graph comprising a plurality of alternative paths”, by finding a sub-graph containing the highest weight paths. The graph induced by the pruned neighborhood is taken as the candidate sub-graph).
While Koren discloses “determining a plurality of reduced subgraphs…”, as discussed above, as well as, analysis of the sub-graphs (see Koren; column 3 lines 43-47), Koren does not explicitly disclose generating a plurality of interpolation transforms respectively for the plurality of subgraphs, a respective interpolation transform mapping demands on the one or more boundary nodes of the respective subgraph to internal nodes of the respective subgraph.
In analogous art, Noon discloses generating a plurality of interpolation transforms respectively for the plurality of subgraphs, a respective interpolation transform mapping demands on the one or more boundary nodes of the respective subgraph to internal nodes of the respective subgraph (see Noon; paragraphs 0107, 0189, and 0244; Noon discloses a graph includes a distance for the nodes that is of bounded degree. Further, the graph includes two or more subgraphs and generating commands to shade, e.g. color, all nodes associated with a first subgraph and a second subgraph i.e. “plurality of subgraphs”. Edge coloring for the nodes is generated by interpolating, i.e. “interpolation transform”, two colors of the nodes, for each subgraph, that the edge connects. In other words, a plurality of interpolating of coloring is done, via the generated commands, i.e. “interpolation transform mapping demands”, for the two nodes, i.e. “one more boundary nodes” and “internal node”, that an edge connects for each subgraph which is of a bounded agree, and as such, one node at one end of the edge would be the “internal node” and the other node at the other end of the edge would be the “boundary node” since the graph is of a bounded degree).
One of ordinary skill in the art would have been motivated to combine Koren and Noon because they both disclose network graphs, and as such, are within the same environment.
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filling date of the claimed invention, to incorporate Noon’s interpolation into the system of Koren in order to provide the benefit of an improved user experience by allowing the user to understand the different regions of a graph via aesthetically pleasing edge coloring (see Noon; paragraph 0244).
While Koren discloses “determining, based on flows induced…a candidate subgraph” and Noon discloses “generating a plurality of interpolation transforms respectively for the plurality of subgraphs…”, as discussed above, the combination of Koren and Noon does not explicitly disclose determining, based on a flow induced in the candidate subgraph by the load, the flow induced in the candidate subgraph recovered using at least one interpolation transform of the plurality of interpolation transforms, at least one alternative path.
In analogous art, Vliegen discloses determining, based on a flow induced in the candidate subgraph by the load, the flow induced in the candidate subgraph recovered using at least one interpolation transform of the plurality of interpolation transforms, at least one alternative path (see Vliegen; paragraphs 0087, 0088, 0091 and 0128; Vliegen discloses a graph may be a flow network, i.e. “flow”, and include a subgraph, i.e. “candidate subgraph”. In particular, the graph is obtained as a subgraph of a complete induced graph, i.e. “based on a flow induced in the candidate subgraph…”, in which a set of paths, i.e. “at least one alternative path”, is determined from a global set of paths using node position that is interpolated, i.e. “using at least one interpolation transform”).
One of ordinary skill in the art would have been motivated to combine Koren, Noon and Vliegen because they all disclose network graphs, and as such, are within the same environment.
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filling date of the claimed invention, to incorporate the feature of determining a set of paths from a global set of paths, as taught by Vliegen, into the combined system of Koren and Noon in order to provide the benefit of improved stability for a network graph layout for path-induced graphs, thus making it easier for a user to observe changes (see Vliegen; paragraphs 0005 and 0006).
Regarding claim 17, Koren, Noon and Vliegen disclose all the limitations of claim 16, as discussed above, and further the combination of Koren, Noon and Vliegen clearly discloses wherein determining the candidate subgraph comprises: pruning edges of the network graph corresponding to a flow below a threshold (see Koren; column 13 lines 38-49; Koren discloses the most probable path flows are determined by a threshold, i.e. “a flow below a threshold”. Pruning edges in a neighborhood of the graph, i.e. “pruning edges of the network graph”, is based on a shortest path of the flow. The pruned neighborhood is taken as the candidate sub-graph, i.e. “determining the candidate subgraph”).
Regarding claim 18, Koren, Noon and Vliegen disclose all the limitations of claim 16, as discussed above, and further the combination of Koren, Noon and Vliegen clearly discloses wherein the plurality of reduced subgraphs are determined using a star-mesh reduction (see Koren; column 11 lines 36-42; Koren discloses using a numeral reduction, i.e. “star-mesh reduction”, for the subgraphs).
Regarding claim 19, Koren, Noon and Vliegen disclose all the limitations of claim 16, as discussed above, and further the combination of Koren, Noon and Vliegen clearly discloses for a plurality of iterations: determining a candidate path through the candidate subgraph having costs respectively associated with one or more path segments along the candidate path (see Koren; column 4 lines 55-67, column 8 lines 10-12, 42-45, column 13 lines 4-10, 48-49 and column 13 line 66 – column 14 line 7; Koren discloses determining the maximal number of units that may be delivered, i.e. “…equivalent load”, from node to node and network flows favor high weight edges and capture the premise that increasing the number of alternative paths, i.e. “determining, based on the flows…”, between nodes increases proximity, thereby gaining from the alternative paths and the subgraph is induced, i.e. “…induced in the plurality of reduced subgraphs”, to determine a candidate sub-graph, i.e. “a candidate subgraph of the network graph comprising a plurality of alternative paths”, by finding a sub-graph containing the highest weight paths. The graph induced by the pruned neighborhood is taken as the candidate sub-graph);
adding the candidate path to the plurality of alternative paths (see Koren; column 8 lines 10-18; Koren discloses the sum, i.e. “adding”, of the alternative paths with each alternative path growing the number of alternative paths, i.e. “candidate path”); and
increasing the costs (see Koren; column 4 lines 58-64; Koren discloses determining the max units to be delivered from node to node and increasing the number of alternative paths increases the proximity; i.e. “increasing the cost”. In other words, the cost to deliver the units increases as the proximity between the nodes increases).
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over Koren et al. (U.S. 7,830,815 B1) in view of Noon (U.S. 2013/0187941 A1).
Regarding claim 20, Koren discloses one or more memory devices storing non-transitory computer-readable instructions that are executable to cause one or more processors to perform operations (see Koren; column 14 lines 55-58; Koren discloses a memory executed by a processor to implement functions), the operations comprising:
obtaining a query indicating a load on a network graph corresponding to a source and a sink (see Koren; column 4 lines 37-41 and 55-59; Koren discloses graphs contain source nodes, i.e. “source”, and terminal nodes, i.e. “sink”. The network flow refers to a measure of proximity between nodes, e.g. source and terminal, calculated by assigning a limited capacity to each edge in the network, one proportional to its weight, and then determining, based on the request for the measure, i.e. “obtaining a query…”, the maximal number of units that may be delivered from node to node, i.e. “…indicating a load on the network graph”);
determining, based on the load, an equivalent load on a plurality of reduced subgraphs (see Koren; column 4 lines 58-61, column 5 lines ; Koren discloses determining the maximal number of units that may be delivered, i.e. “load”, from node to node. This maximal flow may then be taken as a measure, i.e. “based on the load”, of node to node proximity and then determining the same maximal flow between the two graphs, i.e. “reduced subgraphs”); and
determining, based on flows induced in the plurality of reduced subgraphs by the equivalent load, a candidate subgraph of the network graph comprising a plurality of alternative paths (see Koren; column 4 lines 55-67, column 8 lines 10-12, 42-45, column 13 lines 4-10, 48-49 and column 13 line 66 – column 14 line 7; Koren discloses determining the maximal number of units that may be delivered, i.e. “…equivalent load”, from node to node and network flows favor high weight edges and capture the premise that increasing the number of alternative paths, i.e. “determining, based on the flows…”, between nodes increases proximity, thereby gaining from the alternative paths and the subgraph is induced, i.e. “…induced in the plurality of reduced subgraphs”, to determine a candidate sub-graph, i.e. “a candidate subgraph of the network graph comprising a plurality of alternative paths”, by finding a sub-graph containing the highest weight paths. The graph induced by the pruned neighborhood is taken as the candidate sub-graph).
While Koren discloses “determining a plurality of reduced subgraphs…”, as discussed above, as well as, analysis of the sub-graphs (see Koren; column 3 lines 43-47), Koren does not explicitly disclose wherein the flows are recovered using a plurality of interpolation transforms respectively associated with the plurality of reduced subgraphs.
In analogous art, Noon discloses wherein the flows are recovered using a plurality of interpolation transforms respectively associated with the plurality of reduced subgraphs (see Noon; paragraphs 0107, 0189, and 0244; Noon discloses a graph includes a distance, i.e. “flows are recovered”, for the nodes that is of bounded degree. Further, the graph includes two or more subgraphs and generating commands to shade, e.g. color, all nodes associated with a first subgraph and a second subgraph i.e. “plurality of reduced subgraphs”. Edge coloring for the nodes is generated by interpolating, i.e. “interpolation transforms”, two colors of the nodes, for each subgraph, that the edge connects).
One of ordinary skill in the art would have been motivated to combine Koren and Noon because they both disclose network graphs, and as such, are within the same environment.
Therefore, it would have been obvious to a person of ordinary skill in the art, before the effective filling date of the claimed invention, to incorporate Noon’s interpolation into the system of Koren in order to provide the benefit of an improved user experience by allowing the user to understand the different regions of a graph via aesthetically pleasing edge coloring (see Noon; paragraph 0244).
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
Banaei-Kashani et al. (U.S. 2022/0180745 A1) discloses simulating a traffic network as a graph and generating a plurality of alternative paths.
Nikolova et al. (U.S. 2009/0175171 A1) discloses paths that can be modeled as a stochastic network graph which includes nodes connected by edges and the nodes are intermediate points where alternative paths can be selected for a particular route.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ADAM A COONEY whose telephone number is (571)270-5653. The examiner can normally be reached M-F 7:30am-5:00pm (every other Fri off).
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Umar Cheema can be reached at 571-270-3037. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/A.A.C/Examiner, Art Unit 2458 11/10/25
/UMAR CHEEMA/Supervisory Patent Examiner, Art Unit 2458