How to draw a graph on 1C

The implementation in the query language 1C of the method of arranging graph vertices on a plane based on the use of electromechanical analogy is described. In this case, the vertices of the graph are represented by electric charges of the same name, and the arcs are represented by springs. The forces of interaction of the vertices in this system translate them from a random initial to the desired final position. The processing of drawing graphs “GraphOgraph” is presented, which implements this approach, also showing the dynamics of the process. A graph can be specified manually by a list of edges, selected from several predefined examples, or generated according to the information base.

1. THEORETICAL PART

The graph structure using electromechanical analogy is determined by two tables: a table of edges and a table of vertices.
The table of ribs “Ribs” contains three columns: the name of one vertex of the rib (Name1), the name of the opposite vertex of the rib (Name2) and the value of the spring elasticity with which the rib is modeled (Elasticity).

First Name1	Name2	Elasticity
Top1	Top2	Elasticity1
...	...	...
Peak A	TopB	Elasticity AB

The value of elasticity should be the greater, the closer the vertices are connected. If the graph represents a social network, then “resilience” can be proportional to the number of messages between the corresponding network members. If the graph represents a transport system, then the elasticity will be the less, the greater the distance between the nodes. 
The vertex table contains two columns: the name of the vertex (Name) and the value of the electric charge of the vertex (Charge). 

Name	Charge
Top1	Charge1
...	...
Peak A	Charge

The magnitude of the charge can be proportional to the place that the vertex should occupy in the figure, since a stronger charged vertex will repulse neighboring vertices with greater force. For example, when constructing a graph of connections between Infostart participants, a rating can be used as the value of the peak (charge) value. 

The current state of the system is determined by the state table containing the current coordinates of the vertices and consisting of the columns: vertex name (Name), current horizontal coordinate (X) and vertical coordinate (Y). For simplicity, the vertex table and the state table can be combined by writing the charge and current coordinates into one “Vertices” table.

Name	Charge	X	At
Top1	Charge1	X1	U1
...	...	...	...
Peak A	Charge	HA	UA

The dynamics of the described system can be modeled using the Euler method. It allows you to get the coordinates of the vertices after a short period of time based on the current coordinates, knowing the speed and direction (vector) of the movement of each vertex.

For our purposes, it is easier to assume that the displacement velocity is proportional to the force acting on the vertex (movement in a viscous medium). To find the force acting on a particular vertex, you need to add up all the forces acting on it from other vertices. The force of action from the side of each vertex will consist of the repulsive force determined by the Coulomb law in proportion to the product of the charges of the vertices divided by the square of the distance between them. And the forces of attraction in the case of a bond (rib). The magnitude of the force of attraction obeys Hooke's law, that is, it is directly proportional to the product of the bond elasticity by the distance between the vertices. As a result, the repulsive force will act horizontally on peak A with coordinates A.X and A.U from the side of peak B with coordinates B.X and B.U.

(A.X - B.X) / Distance AB * A.Charge * B.Charge / ((A.X - B.X) * (A.X - B.X) + (A.U - B.U) * (A.U - B.U))

and the vertical repulsion force

(A.U - B.U) / Distance AB * A.Zaryad * B.Zaryad / ((A.X - B.X) * (A. X - B.X) + (A.U - B.U) * (A.U - B.U))

where

Distance AB = SQRT ((A.X - B.X) * (A.X - B.X ) + (A.U - B.U) * (A.U - B.U))

Elements of the form (A.X - B.X) / Distance AB are projections of the direction vector of the force having a unit length. Such a vector affects the direction, but does not change the magnitude of the force.

If there is a rib between the vertices, the force of attraction will also act. Horizontally, its value will be determined by the formula

((B.X - A.X) / Distance AB) * Elasticity

AB * Distance AB , A by the formula

((B.U - A.U) / Distance AB) * Elasticity AB * Distance AB.

Having added two forces and making the necessary reductions, we obtain the formula of horizontal force

(A.X - B.X) (A.Zaryad * B.Zaryad / Distance AB / ((A.X - B.X) * (A.X - B. X) + (A.U - B.U) * (A.U - B.U)) - Elasticity AB)

and vertical force

(A.U - B.U) (A.Charge * B.Charge / Distance AB / ( (A.X - B.X) * (A.X - B.X) + (A.U - B.U) * (A.U - B.U)) - Elasticity AB)

Moving along X and Y can be obtained by multiplying the sum of the forces acting on the side of all the vertices by the step size in time “Step”. Thus, if the current coordinates of the vertices are known, using the indicated formulas, one can obtain the following coordinates and so on until the system goes into a stable state, where the sum of the forces acting on each vertex is close to zero.

All of the above is realized by repeating the execution of one rather simple query:

SELECT Ribs. Name1, Ribs.
Name2, Ribs. Elasticity PLACE Ribs FROM & Ribs AS Ribs
;
SELECT Ribs. Name1, Ribs. Name2, Ribs. Elasticity. PLACE
ARCS
FROM THE RIBS AS RIBS UNITE
ALL.
SELECT Ribs. Name2, Ribs. Name1, Ribs. Elasticity.
FROM RIBS AS
RIBS TO INDEX ON RIBS. Name1, Ribs
. Name2 ;
CHOOSE Tops. Name, Tops. Charge, Tops. X, Tops. U
PLACE Tops
FROM & Tops AS Tops
;
CHOOSE
    A. Name,
    MAXIMUM (A.Charge) AS Charge,
    MAXIMUM (A.X) + & Step * AMOUNT ((A.X - B.X) * (A.Charge * B.Charge / ((A.X - B.X) * (A.X - B.X) + (A.U - B.U) * (A.U - B.U)) - IS NULL (Arc. Elasticity, 0))) AS X,
    MAXIMUM (A.U) + & Step * AMOUNT ((A.U - B.U) * (A.Zaryad * B.Zaryad / ((A.X - B.X) * (A.X - B.X) + (A.U - B.U) * (A.U - B.U)) - THERE is NULL (Dougie. Elasticity, 0))) AS
FROM
    A         vertex AS A
        INTERNAL CONNECTION
OF Apex AS B. A. Name <> B. Name
        LEFT JOIN CONNECTION AS
        ARCS BY A.Name = Arcs.Name1
            AND (B.Name = Arcs.Name2)
GROUP BY
    A.Name

In the first request of the packet, the table of edges is entered, in the second of the edges arcs are formed, that is, the forces edges are directed both from the first to the second vertex, and from the second to the first, in the third query, a table of vertices is entered, and in the fourth, the necessary calculations are performed. For this, three tables are connected: the table of vertices A and the table of vertices B by the condition of inequality of the names of the vertices and the table of arcs by the condition that the names of the ends of the arcs coincide with the names of the vertices. Next, a grouping is performed on the vertices of table A, during which a superposition of forces is calculated, which is multiplied by Step and added up with the current coordinates.

Attentive readers will notice that the “Distance AB” divider is missing in the formulas. This is due to the fact that in the query language 1C there is no function for calculating the square root SQRT. That is, in this query, it is actually considered that the repulsive force is inversely proportional not to the square of the distance between the vertices, but simply to the distance. Thus, the repulsive force is given excessive long-range. There is nothing wrong with this, since for the task of drawing graphs this is not so essential. However, in the query actually used in the processing, this difficulty is overcome. This is done by calculating the square root using the Heron iteration formula

Distance AB '= (Distance AB + Square Distances AB / Distances AB) / 2,

where the previous distance value is taken from the previous iteration of the request, and the initial one is one. Such a solution didn’t slow down the calculation process much. The specified mode is included in the processing by ticking "LawCoulomb". Also, in a real query, additional optimization was performed: reloading of arcs and indexing of arcs in each iteration were excluded, and the sum of squares of distances for each pair of vertices is considered not four times, as in the original query, but one. If you wish, in order to eliminate the quadratic dependence of the query execution time on the number of vertices, you can divide the plane into cells (or cells) and consider repulsion only for the vertices of neighboring cells. However, so far no such optimization has been carried out and it is unclear how necessary it is - to draw graphs from 100 - 200 vertices of speed is enough.

As in other problems of numerical solution of systems of nonlinear differential equations, the important question is the choice of time step. A larger step leads to an increase in the speed of the solution, but up to certain limits when the dynamic system loses stability. In all the following examples, with charges and elasticity, 1 step was taken equal to 0.2, except for graphs of nomenclature groups and contractors, where the step had to be reduced to 0.05. In general, an understandable rule applies - the greater the elasticity, the smaller the step.

2. PRACTICAL PART

Processing "GrafOgraf" is attached to the article(emphasis on the letter "o"). With its help, you can set the structure of the graph and observe the dynamics of constructing its drawing (if the "Show process" checkbox is enabled). Processing allows you to change the decision step - it should be positive, but not too large. You can change the threshold for moving to stop - this parameter may be zero, but then you will have to interrupt the simulation process manually (Ctrl-Break). You can set the required graph size in millimeters - the graph is automatically scaled, trying to occupy the given rectangle. You can increase or decrease the graph, as well (on the vertex tab), rotate it clockwise or counterclockwise, or flip it (relative to the diagonal). You can specify the color of the edges and the color of the vertices (all at the same time - a different color for each vertex and edge has not yet been set). In addition, by setting the first rib elasticity, using the “Compare” button, you can make the elasticity of all ribs the same as that of the first rib. A similar action is programmed to charge the vertices. Here's what the processing control panel looks like:



The graph structure can be set manually by specifying its list of edges. The vertices to be joined are defined by the names represented by the text strings. In a specific application, processing can be specialized so that the vertices are specified by references to objects of the infobase. Then the decryption will open the corresponding objects. When editing edges, the list of vertices is automatically generated (the charge can be corrected). The gathered parameters and the graph structure can be saved as report settings.

If there is no graph whose drawing you want to see, you can work with ready-made demo examples. In this case, you can select the number of vertices of the example graph (64 by default).

The following are the figures obtained for the examples sewn into processing. The dynamics of the construction (and it is also very interesting) is better to see by running the processing.

1. Grid (adjacent vertices are connected into cells of a rectangular grid)

 

2. Necklace (the tops are connected in a ring)

 

3. Tangle (all vertices are directly connected)

 
to get this beautiful picture, it was necessary to zero out the elasticity of the ribs in the middle of the ring. Otherwise, the view would be completely different:
 

4. The binary tree

 

5. 5-ary tree

6. Star (all vertices are connected to one central vertex)

here, the inherent drawback of the method is clearly visible - the straight edge 1-13 does not bypass vertex 5, but intersects it.

7. Metro Moscow

while enlarging the picture, the circuit is well read. In evidence, a fragment of the central part is shown at a larger magnification.

8. Metro Peter

Anyone who knows Peter will notice that the Vasileostrovskaya and Primorskaya stations are out of place, but there is nothing to be done - such a model.

9. The group graph of the “Nomenclature” directory (such a directory must exist in the configuration where the processing starts)

10. The group graph of the “Contractors” directory (this directory must also exist in the configuration where the processing starts)

Regarding metro schemes, we can add that when they were built, I had to go to a certain trick. The fact is that, due to the initial random arrangement of the stations, long radial branches behind the ring line (for Moscow) are very likely to overlap and are no longer straightened. It would be possible (a) to build a graph by increasing the stations (as the metro was built), (b) connect the middle stations of the departure branches with a large virtual ring with weak “straightening” connections, (c) fix the end stations, or (d) take into account the district with the initial dispersion of stations station. The last method has been selected. It is also worth noting that the number (187 taking into account the same name) of the Moscow metro stations is already close to the limit of the method's capabilities. In the status bar when the method is running, the number of frames per second that processing has time to build is noted. On the example of the metro, the processing (file base, laptop, disabled process display and Coulomb's law) showed approximately 2.4 fps. The structure of the metro is recorded in the mock-ups of processing, if you wish, you can add an image of any other metro.

All other drawings are built almost instantly or quite quickly and completely automatically from information only on the structure of graphs. Only scaling and rotation were used. The relatively small number of vertices shown in the examples is explained not by the limited capabilities of the method, but by the desire to make the drawings smaller.

It seems that these examples should be enough to prove the efficiency and practical applicability of the method. But the presentation of relationships in the form of graphs is so universal that, no doubt, there are still many other illustrative examples. In particular, it was still possible to build any kind of family tree, the structure of comments for the selected article on Infostart, the connections of 1C: Document Management users, and so on and so forth. By adding a few lines of code, you can draw arrows on arcs and thus draw oriented graphs.

You can offer other ways to "configure" this "typical" model for a specific task, except for vertex objects, multi-colored vertices, multi-colored arcs and arrows on them. For example, it is extremely easy to add a third dimension and solve the problem of placing vertices in space. You can fix some vertices, each time zeroing the calculated movement. After that, you can add a "flow" so that the peaks are "related" in the right direction. Well, or to introduce the force of repulsion of vertices from arcs too, in order to correct the inherent disadvantage of the considered algorithm - the intersection of “alien” vertices by arcs.

CONCLUSIONS

As a result, we can draw the following conclusions from the processing tests on the above examples: the method works ideally in the case of relatively loose graphs of symmetric and regular structure. In the case of the other extreme - the complicated complicated structure of the graph, sometimes (but not always!) It may be necessary to manually correct some parameters (step, charge, repulsion law, elasticity, current coordinates) or even choose a fundamentally different algorithm. There are limitations (in theory - surmountable) and the size of the graph. But, on the other hand, unlike other algorithms, the implementation of this method is feasible on pure 1C without using any external components with a simple query of 14 lines (in the main part).

Well, in general, the considered approach once again shows the flexibility of the query language and how interconnected scientific disciplines are. In solving this specific practical task of automation, knowledge was required from several different areas of mathematics and physics. Even Pythagoras' theorem came in handy. In general, knowledge is power!

File processing.

(C) ildarovich