Patent ID: 8423948

Claim:
A device which supports designing a wiring path on a printed circuit board, the device comprising: a directional graph definition unit to define, on a target area surface on which the wiring path is generated, a directional graph having a grid point as a node and a line as a branch connecting adjacent grid points; a wiring prohibited area information acquisition unit to acquire an input about wiring prohibited area information about a position of an area in which an arrangement of wiring is prohibited on the target area surface; a wiring information acquisition unit to acquire an input about wiring information as information about a set of plural sets of grid points connected by respective wiring in the grid points defined on the target area surface; a flow network generation unit to generate a flow network by setting a flow capacity to “0” for a branch connected to a grid point placed in an area indicated by the wiring prohibited area information in branches configuring the directional graph, setting a flow capacity to “1” for other branches, and connecting a starting point and an end point of a flow through a branch having the flow capacity of “1” to a pair of grid points belonging to each set of the plural sets of grid points; a flow path search unit to search the flow network for a path of a flow having a maximum amount of flow from the starting point to the end point under the flow capacity set by the flow network generation unit for each branch; and a wiring path determination unit to determine the plural wiring paths connecting respective pairs of grid points belonging to respective sets of the plural sets of grid points indicated by the wiring information according to a search result of the path by the flow path search unit.