Software for constructing of A-chains with ordered enclosing for a plane connected 4-regular graph

The task of constructing the cutting path of the tool when the part cut off from the sheet does not require additional cuts and the trajectories of cuts intersections are forbidden (the touches are allowed) may arise in CAD/CAM-systems of technological preparation of cutting processes. Formally, such a task can be formulated as the problem of constructing a self-non-intersecting chain in a plane Euler graph representing a homeomorphic image of a cutting plan. Finally, the tasks of constructing routes satisfying the technological constraints are reduced to defining an A-chain with ordered enclosing for a plane connected 4-regular graph. This article is devoted to the algorithm for finding such a chain. The execution of this algorithm consists of two stages. At the first stage, cut-vertices of rank k are identified and splitted. At the second stage, the construction of the chain starts from an arbitrary vertex incident to the outer face; the first edge of the chain is chosen to be an edge of maximal rank incident to a given vertex; next, an iterative process is organized where, as the next edge, an unpassed edge of maximum rank is chosen, which is the left or right neighbour of the current one. It is shown that the algorithm constructs a route with the indicated properties in linear time for a plane connected 4-regular graph. The considered algorithms are realized as a computer program. The examples of some test problems are given in this paper.