CN112150581B - Distributed self-adaptive graph vertex coloring method and system - Google Patents

Abstract

The invention discloses a distributed _adaptive graph vertex coloring method and system, comprising: respectively acquiring the coloring information set C ^t-1 ( vi); Coloring conflict judgment is performed on each vertex _vi ; wherein, for any vertex vi, if the value rs of the current probability generator is satisfied that the value _rs of the current probability generator is less than or equal to the first threshold α and the coloring information c _i of the _{vertex vi} ∈C ^t‑1 (v _i ) and c _i ∈B ^t (v _i ), then determine that the vertex v _i and its adjacent vertices produce coloring conflicts; determine the available color set U(v _i ) corresponding to each vertex v _i , A color is randomly selected from the available color set U(vi ₎ corresponding to each vertex v _i according to the second threshold β _, and the coloring information c _i of each vertex v _i is determined; All adjacent vertices v _j send their coloring information c _i ; if the coloring information of each vertex v _i is different from the color of all its adjacent vertices, the coloring information of each vertex in the undirected graph is determined.

Description

A Distributed Adaptive Graph Vertex Shading Method and System

technical field

The present invention relates to the technical field of data processing, and more particularly, to a distributed adaptive graph vertex coloring method and system.

Background technique

The NP-C problem is one of the seven major mathematical problems in the world. Even today with the rapid development of information technology, there are still a large number of NP-C problems to be solved in various fields. The graph vertex coloring problem (GVCP, graph vertex coloring problem) is one of the most famous NP-C problems. GVCP studies how to color the vertices of an undirected connected graph such that adjacent vertices with common edges have different colors. Specifically, GVCP determination mainly considers whether the coloring task can be completed with a given k colors, while GVCP quality optimization focuses on minimizing the k value, and they are widely used in practical scenarios such as task scheduling, register allocation, and scheduling. Therefore, studying the determination and quality optimization of GVCP not only has important theoretical significance for the exploration and solution of NP-C problems, but also has broad commercial application value.

Due to the high complexity of directly calculating GVCP, the currently commonly used solution is heuristic solution, that is, the optimal solution is gradually sought through iterative approximation. Even so, in the era of big data, the scale of graph data has grown explosively, making it difficult for traditional centralized (single-machine) iterative methods to complete computing tasks within a reasonable time. In recent years, the new distributed processing systems based on cloud computing have good scalability in terms of computing and storage capabilities, and can provide effective support for the iterative solution of GVCP. Among them, the distributed graph computing system Pregel proposed by Google and its open source implementation and extension such as GraphLab are the most suitable. They provide a vertex-centric programming interface and performance optimization, so that users at the application level only need to care about business logic and do not need to understand the details of distributed processing.

In a distributed graph computing system, graph vertex data is distributed to different tasks (such as physical machines, processes or threads, etc.) in order to increase the parallelism of shading processing. In an iteration process, the vertices on each task are colored in parallel, and the selected color is broadcast to the adjacent vertices connected by edges in the form of messages, and the system coordinates the processing progress of each task through the global synchronization roadblock (synchronous calculation). ) and make sure that all vertices receive all the message data they should receive at the time of computation. It should be noted that the messages sent in this iteration can only be used in the next iteration after the roadblock. However, specific to GVCP calculation, logically topologically adjacent vertices may belong to different tasks physically, and it is very likely that the same color will be selected during the parallel coloring process, resulting in coloring conflicts. On the other hand, the existence of synchronization roadblocks leads to a lag in the propagation of coloring information, that is, poor real-time performance. Poor real-time performance results in only the next iteration being aware of shading conflicts and proceeding with color selection. However, the re-selection process may still produce coloring conflicts, and eventually fall into infinite oscillation, resulting in the failure of the algorithm to converge. In order to solve this problem, the existing technology either calculates independent sets step by step and then colorizes sequentially in batches in units of independent sets to avoid simultaneous coloring of adjacent vertices, or introduces random disturbances to coloring by breaking the global synchronization roadblock to jump out of the oscillation cycle. . However, the former introduces additional computational overhead and maintenance overhead of independent set results, while the latter greatly increases the difficulty of program debugging and fault-tolerant control due to the uncontrollable perturbation (difficult to reproduce).

SUMMARY OF THE INVENTION

The present invention proposes a distributed adaptive graph vertex coloring method and system to solve the problem of how to efficiently and accurately color undirected graph vertices.

In order to solve the above problems, according to an aspect of the present invention, a distributed adaptive graph vertex coloring method is provided, and the method includes:

Step 1, respectively obtain the coloring information set C ^t-1 (vi ₎ of all adjacent vertices of each vertex v _i in the undirected graph in the previous iteration process; wherein, t is the current number of iterations;

Step 2: Perform coloring conflict judgment on each vertex vi; wherein, for any vertex vi, if the current probability generator value _rs is less than or equal to the first threshold α and the coloring information c _{i ∈} of the vertex vi is _satisfied C ^t-1 (v _i ) and c _i ∈ B ^t (v _i ), then determine that the vertex vi and its adjacent vertices have a color conflict, and update the state accumulation monitoring variable _si corresponding to the vertex _vi to be the initial threshold; where, s _i is used to record the number of iterations that the coloring information of the vertex v _i has not changed continuously; B ^t (vi ₎ is the current iteration step that the vertex v _i has received at the update time and is located at the vertex v _i The coloring information of some adjacent vertices of the task;

Step 3: Determine the available color set U(v _i ) corresponding to each vertex v _i , and randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i according to the second threshold β, and determine each color. coloring information c _{i of each vertex v i ;}

Step 4, for each vertex v _i , send its coloring information c _i to all its adjacent vertices v _j along the edge;

Step 5, determine whether the coloring information of each vertex v _i is different from the color of all its adjacent vertices; wherein, if it is satisfied, then directly determine the coloring information of each vertex in the undirected graph; if not, then Adjust the first threshold α and the second threshold β according to the running information, and return to step 1 to re-iterate until the coloring information of each vertex v _i and the colors of all its adjacent vertices are different, stop, and determine the undirected graph Shading information for each vertex in .

Preferably, wherein the method further comprises:

When judging coloring conflict for each vertex v _i , if the current value rs of the probability generator is not satisfied, the value _rs is less than or equal to the first threshold α and the coloring information of the vertex v _i is c _i ∈ C ^t-1 (vi ₎ And c _i ∈ B ^t (vi ), then it is determined that the vertex v _i and its adjacent vertex v _j have no coloring conflict, update s _{i =s i +1} , and go to step 4 directly.

Preferably, wherein the method further comprises:

Before the next iteration, the first threshold α is dynamically adjusted using the following formula, including:

α=p+(p-dv/maxd)×γ,

γ=|V ^x |/|V|,

Among them, p is the preset basic threshold, the value range is 0 to 1; d _v is the degree of the current vertex v _i , maxd is the maximum degree of all the vertices in the undirected graph, γ is 0 to 1 The convergence control parameter of 1; |V| is the number of all vertices in the undirected graph, and |V ^x | is the number of vertices whose color has not changed in the preset continuous x-step iterative calculation.

Preferably, wherein the determining the available color set U(v _i ) corresponding to each vertex v _i , randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i , and determine each vertex The coloring information _ci of _vi , including:

Determine the available color set U(vi ₎ corresponding to each vertex v _i

For any vertex v _i , if |U(vi ₎ | is less than the second threshold β, then color expansion is performed, the maximum used color value is incremented by β as a unit step, and added to the available color set in U( _vi );

Arrange the colors in the current available color set U(v _i ) corresponding to each vertex v _i in ascending order of color numbers, select the top-β colors and put them into the array, and take the value r _c modulo β according to the value of the random shader. The remainder is used as an array subscript for color selection, and the coloring information of each vertex v _i is determined as c _{i_} =arrayOfTop-β[r _c modβ].

Preferably, wherein the method further comprises:

Before the next iteration, the second threshold β is dynamically adjusted using the following formula, including:

γ=|V ^x |/|V|,

为向上取整数运算符，γ为取值为0到1的收敛调控参数；|V|为所述无向图中的全部顶点数量，|V^x|为在预设的连续x步迭代计算中颜色均未发生变化的顶点数量。in,

is an upward integer operator, γ is a convergence control parameter with a value from 0 to 1; |V| is the total number of vertices in the undirected graph, |V ^x | is in the preset continuous x-step iterative calculation The number of vertices for which none of the colors have changed.

According to another aspect of the present invention, a distributed adaptive graph vertex shader system is provided, the system comprising:

The coloring information set acquisition unit is used to obtain the coloring information set C ^t-1 (vi ₎ of all adjacent vertices of each vertex v _i in the undirected graph in the previous iteration process; wherein, t is the current number of iterations ;

The coloring conflict judgment unit is used to judge the coloring conflict for each vertex _vi ; wherein, for any vertex vi, if the value rs of the current probability generator is satisfied that the value _rs of the current probability generator is less than or equal to the first threshold α and the coloring of the vertex _vi is Information c _i ∈ C ^t-1 (vi ) and c _{i ∈} B ^t (vi ₎ , then determine that the vertex vi and its adjacent vertices have coloring conflicts, and update the state accumulation monitoring variable _si corresponding to the vertex _vi to be the initial Threshold; wherein, s _i is used to record the number of iterations that the coloring information of the vertex v _i has not changed continuously; B ^t (vi _{) is the current iteration step that the vertex v i has} received at the update time and is located in The coloring information of some adjacent vertices of the task where the vertex v _i is located;

The coloring unit is used to determine the available color set U(v _i ) corresponding to each vertex v _i , and randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i according to the second threshold β, Determine the coloring information c _{i of each vertex v i ;}

a message broadcasting unit, for each vertex v _i , sending its coloring information c _i to all its adjacent vertices v _j along the edge;

A coloring information determination unit, used to determine whether the coloring information of each vertex v _i is different from the colors of all its adjacent vertices; wherein, if it is satisfied, the coloring information of each vertex in the undirected graph is directly determined; if If not satisfied, then adjust the first threshold α and the second threshold β according to the running information, and enter the coloring information set acquisition unit to iterate again, until the coloring information of each vertex v _i and the color of all its adjacent vertices are different, stop, And determine the coloring information of each vertex in the undirected graph.

Preferably, the coloring conflict judgment unit further includes:

When judging coloring conflict for each vertex v _i , if the current value rs of the probability generator is not satisfied, the value _rs is less than or equal to the first threshold α and the coloring information of the vertex v _i is c _i ∈ C ^t-1 (vi ₎ And c _i ∈ B ^t (vi ), it is determined that the vertex v _i and its adjacent vertex v _j have no coloring conflict, update s _{i =s i +1} , and directly enter the message broadcasting unit.

Preferably, wherein the system further comprises:

A first threshold adjustment unit, configured to dynamically adjust the first threshold α by using the following formula before performing the next iteration, including:

α=p+(p-dv/maxd)×γ,

γ=|V ^x |/|V|,

Among them, p is the preset basic threshold, the value range is 0 to 1; d _v is the degree of the current vertex v _i , maxd is the maximum degree of all the vertices in the undirected graph, γ is 0 to 1 The convergence control parameter of 1; |V| is the number of all vertices in the undirected graph, and |V ^x | is the number of vertices whose color has not changed in the preset continuous x-step iterative calculation.

Preferably, the coloring unit determines the available color set U(v _i ) corresponding to each vertex v _i , and randomly selects a color from the available color set U(vi ₎ corresponding to each vertex v _i , respectively, and determines The shading information c _i of each vertex v _i , including:

Determine the available color set U(vi ₎ corresponding to each vertex v _i

For any vertex v _i , if |U(vi ₎ | is less than the second threshold β, then color expansion is performed, the maximum used color value is incremented by β as a unit step, and added to the available color set in U( _vi );

Arrange the colors in the current available color set U(v _i ) corresponding to each vertex v _i in ascending order of color numbers, select the top-β colors and put them into the array, and take the value r _c modulo β according to the value of the random shader. The remainder is used as an array subscript for color selection, and the coloring information of each vertex v _i is determined as c _{i_} =arrayOfTop-β[r _c modβ].

Preferably, wherein the system further comprises:

The second threshold adjustment unit is configured to dynamically adjust the second threshold β by using the following formula before the next iteration, including:

γ=|V ^x |/|V|,

为向上取整数运算符，γ为取值为0到1的收敛调控参数；|V|为所述无向图中的全部顶点数量，|V^x|为在预设的连续x步迭代计算中颜色均未发生变化的顶点数量。in,

is an upward integer operator, γ is a convergence control parameter with a value from 0 to 1; |V| is the total number of vertices in the undirected graph, |V ^x | is in the preset continuous x-step iterative calculation The number of vertices for which none of the colors have changed.

The invention provides a distributed adaptive graph vertex coloring method and system, aiming at the deficiencies of the prior art in solving the problems of coloring information propagation delay and parallel coloring conflict, in a distributed synchronous computing environment, through the coordination between vertices Processing goes directly to the shading. Among them, in view of the propagation delay of coloring information, considering the applicability of stride computing technology and the randomness of stride processing remote task messages, a local message streaming visibility technology is proposed, which allows vertices to be in the same task and have The shading information (ie B ^t (v _i )) of the local vertices that have completed shading is visible in real time to speed up information propagation and ensure correctness, and to ensure the reproducibility of the calculation process by globally synchronizing and recording the update order of local vertices; For the problem of parallel coloring conflicts, reproducible random disturbances (ie, the first threshold and the second threshold) are injected from the perspectives of coloring timing and color selection to alleviate the coloring conflicts of adjacent vertices and accelerate the convergence. The corresponding technology can directly Vertices are colored without calculating independent sets, which improves computational efficiency, and can transform graph topology reduction based on independent sets into multiple relaxation adjustments of vertex color states, which simplifies data management operations; in addition, in the iterative calculation process, By detecting the coloring changes of vertices in real time, the random disturbance intensity (that is, the size of the first threshold and the second threshold) can be dynamically and adaptively adjusted, thereby further improving the computational parallelism and coloring quality while ensuring the convergence of the algorithm.

Description of drawings

Exemplary embodiments of the present invention may be more fully understood by reference to the following drawings:

Figure 1 is a schematic diagram of colored oscillations.

Figure 2 is a frame diagram of global stride message processing.

3 is a flowchart of a distributed adaptive graph vertex shader method 300 according to an embodiment of the present invention;

FIG. 4 is a block diagram of a local message streaming visible technology according to an embodiment of the present invention;

5 is a flowchart of distributed adaptive graph vertex shading according to an embodiment of the present invention;

FIG. 6 is a schematic structural diagram of a distributed adaptive graph vertex shader system 600 according to an embodiment of the present invention.

Detailed ways

Exemplary embodiments of the present invention will now be described with reference to the accompanying drawings, however, the present invention may be embodied in many different forms and is not limited to the embodiments described herein, which are provided for the purpose of this thorough and complete disclosure invention, and fully convey the scope of the invention to those skilled in the art. The terms used in the exemplary embodiments shown in the drawings are not intended to limit the invention. In the drawings, the same elements/elements are given the same reference numerals.

Unless otherwise defined, terms (including scientific and technical terms) used herein have the commonly understood meanings to those skilled in the art. In addition, it is to be understood that terms defined in commonly used dictionaries should be construed as having meanings consistent with the context in the related art, and should not be construed as idealized or overly formal meanings.

Since the graph vertex coloring problem (GVCP, graph vertex coloring problem) requires that the colors of adjacent vertices with a common edge cannot be the same, the coloring of a vertex needs to consider the color selection of its adjacent vertices and affect each other. This means that one coloring of all vertices cannot solve GVCP; on the contrary, it is necessary to adjust multiple times according to the coloring of adjacent vertices, that is, multiple iterations and repeated color changes, so that the vertex coloring is gradually stabilized, that is, the algorithm converges. In order to design the calculation logic of a single iteration, the behavior of each vertex needs to be analyzed first. Obviously, in order for a vertex to complete the appropriate color selection, it is necessary to obtain the current color attribute value of its adjacent vertices, then select the appropriate color according to the color set of the adjacent vertices and execute the coloring, and finally send the modified result to the adjacent vertices, so that Its adjacent vertices undergo color selection in the next iteration. To sum up, given an undirected graph G(V,E), in the distributed graph vertex coloring process, the color of each vertex v _i is first initialized to c _i =0, and then v _i iteratively updates the color, Until the colors of all vertices are no longer updated. In the prior art, in each step of iterative calculation, the behavior of vertex v _i is as follows:

Step1, obtain the coloring information set of adjacent vertices in the previous iteration, namely C(v _i )={c ₁ ,c ₂ ,...,c _j },v _j ∈N(v _i ), where N(v _i ) is The set of adjacent vertices of v _i ;

Step2, if c _{i ∈} C(vi ₎ , then vi and adjacent vertices have a coloring conflict, the result is True, and you need to jump to Step 3 to modify the color;

通常可用最小选择策略，即

使v_i着上最小的可用颜色，进而优化整个算法的色数k以提高着色质量；Step3, for vertex v _i , let U(vi ₎ be the set of available colors, there should be

Usually a minimal selection strategy is available, i.e.

Make v _i the smallest available color, and then optimize the chromatic number k of the whole algorithm to improve the coloring quality;

Step4, send color information c _i to all adjacent vertices v _j along the edge in the form of message (m _ij ), that is, m _ij =<v _j , _ci >, so that the adjacent vertices continue to judge the coloring conflict in the next iteration ( i.e. Step2) and possible color choices (i.e. Step3).

In the distributed synchronous computing environment, the above process is very prone to the phenomenon of "shading oscillation", that is, when two or more adjacent vertices scattered on different tasks execute the shading conflict judgment (Step 2) in parallel and the result is True, if they The coloring information C of adjacent vertices is exactly the same, then under the minimum color selection strategy, these vertices will be changed to the same color; and due to the constraints of synchronous control, these vertices do not know each other's coloring choices, resulting in the next iteration due to the generation of Coloring conflict and need to continue to change the color. This situation may continue for several rounds of iterations, and even shading oscillations occur due to repeated color transformations, making the algorithm fall into an infinite loop and fail to converge. Figure 1 illustrates this coloring oscillation phenomenon. In the left figure, the adjacent vertices v ₁ and v ₃ on different tasks are set to red at the same time (c ₁ =c ₃ =1), so the color needs to be changed. Since their adjacent vertices v ₂ and v ₄ have already used blue (c ₂ =c ₄ =2), under the minimum color selection strategy, yellow with a value of 3 naturally becomes the currently selected optimal color (3 = min {3,4,5,…}). So as shown on the right, during parallel shading, v ₁ and v ₃ will be set to yellow at the same time again. However, they still have coloring conflicts at this time, so in the next iteration, they will change to the optimal choice of red, and they will fall into infinite oscillation and cannot converge.

The essence of GVCP is to search the huge solution space formed by the color selection of different vertices under the constraint of "different coloring of adjacent vertices" to filter out the solutions that meet the requirements. In a single-machine centralized environment, all vertices are shaded serially, and the shading vertices can obtain the latest color information of their adjacent vertices in real time during the process of color selection, so as to avoid shading conflicts between adjacent vertices and prevent shading oscillations. However, because the solution space is too large, the existing exhaustive methods, backtracking methods, greedy methods, etc. are inefficient. Therefore, researchers have proposed optimization schemes such as ant colony algorithm and genetic algorithm, in order to reduce the blindness of the search process and maximize the efficiency of the search process. Avoid getting stuck in a local optimum.

Ant colony algorithm simulates ants searching for the shortest path from ant nest to food through pheromone in the process of searching for food. In specific applications, multiple ants can be placed on the same vertex or multiple random vertices for graph traversal. Specific pheromones are released when ants color vertices, and other ants choose traversal routes based on pheromone strength. On this basis, the maximum and minimum ant colony search algorithm sets the initial value of pheromone strength to the maximum, and limits the range of strength values during the search process to reduce the probability of falling into a local minimum.

Genetic search simulates the natural evolution process based on the principle of survival of the fittest and survival of the fittest. It gradually converges to the optimal individual by generating initial populations, selection, hybridization and mutation. It has good global search ability and is not easy to fall into local optimal solutions. of parallelism. The subsequent improved version optimizes the computational efficiency and the optimality of the solution by redesigning the hybridization operator, the local search operator and the fitness function.

In distributed shading, the distributed shading scheme is dedicated to improving shading efficiency by strengthening the configuration of computing power. However, according to the above analysis, it is very likely that adjacent vertices have coloring conflicts and cause the colors to change repeatedly, resulting in oscillation, which makes the algorithm unable to converge. In order to solve this problem, the distributed asynchronous computing framework of the GraphLab system removes the global synchronization control, which can randomize the coloring timing of vertices on different tasks, thereby reducing the probability of adjacent vertices coloring and selecting the same color at the same time; while distributed synchronization In terms of computing framework, the current mainstream idea is to gradually find independent sets and then use independent sets as a unit to color to avoid coloring conflicts, then delete vertices and edges from the independent set, and repeat the above process until all vertices and edges are deleted. , which can prioritize shading for each independent set according to the vertex degree size to improve shading quality.

Regarding the real-time aspect of shading information, GraphLab's asynchronous computing framework allows vertices to start shading operations at any time and utilize all currently received, latest adjacent vertex shading messages, with the best real-time performance. In terms of synchronous computing, due to the existence of global roadblocks, the messages sent by the current iteration step can only be used in the next iteration step. However, inspired by the asynchronous computing mechanism, some researchers have proposed global stride message processing and block-centered local Asynchronous computing technology to prune message scale or speed up message propagation for algorithms that support message accumulation computing, such as single-source shortest path. The difference is that the former allows updating vertices, in addition to processing the messages received in the previous iteration, but also processing all messages that have been received in the current iteration, originally used for the next iteration, from the task where the vertex is located and other tasks. Message data; the latter only allows direct communication computations between vertices on the same task without the constraints of synchronization roadblocks.

Figure 2 shows the global stride message processing flow. Assuming there are 3 distributed tasks, according to the normal synchronous iterative constraint mechanism, in the iterative calculation in step l, each task can only use the message C ^{l- 1} . However, the vertex update calculation within each task is serial, and the updated vertex will immediately broadcast new messages to the adjacent vertices, and these messages may be received before the adjacent vertices are scheduled to perform the first iteration calculation. Denoted as B ^l . The global stride process allows a vertex to use C ^l-1 and B ^l at the same time when performing update calculations, if the latter has been received and available. At the same time, because the message in ^Bl has been used, it will be completely cleared. This means that in the calculation of step (l+1), these messages will not be visible, so the messages in B ^l need to be removed from C ^l , ie C ^l -B ^l .

At present, the mainstream centralized shading algorithms have been deeply optimized in terms of processing efficiency and shading quality. However, in the era of big data, in the face of large graphs with hundreds of millions of vertices, billions of edges, and the scale is still growing rapidly, limited Due to the hardware configuration of a single machine, its computing efficiency is far from meeting the needs of economic and social development; distributed computing provides an effective solution for improving computing efficiency, but to solve the oscillation problem caused by the parallel coloring of adjacent vertices, asynchronous computing is required. Or the batch shading strategy based on independent sets. The former destroys the global synchronization and the update timing of the vertices is completely random, which makes the calculation process difficult to reproduce, which poses a great challenge to program debugging and fault-tolerant control; while the latter requires the independent set calculation stage. The introduction of additional iterative processing and maintenance of its computational results and the resulting dynamic pruning of the graph structure makes the processing complex and time-consuming. In particular, existing stride computation techniques (including block-centric computations) only support algorithms for accumulatively combining messages, such as single-source shortest paths, connected domain computations, and incremental PageRank computations, that is, if a vertex The value of is unchanged between two adjacent iterations, so it does not have to repeatedly send vertex values to adjacent vertices. However, in the vertex coloring algorithm, even if the color of a vertex does not change in two adjacent iterations, the colors of other neighbors of its adjacent vertices may change, so it still needs to send its own color value to the adjacent vertices. , so that the latter makes the correct shading selection. Therefore, existing stride calculations are not suitable for vertex shading problems. In addition, under the existing stride technology, all received messages are involved in the calculation, but the arrival time of remote messages from other tasks is random due to network reasons, which makes the calculation process difficult to reproduce and greatly increases the number of programs. Difficulty of debugging and fault tolerance control.

Aiming at the deficiencies of the prior art in solving the problems of coloring information propagation delay and parallel coloring conflict, the present invention directly performs coloring through cooperative processing between vertices in a distributed synchronous computing environment. Among them, in view of the propagation delay of coloring information, considering the applicability of stride computing technology and the randomness of stride processing remote task messages, a local message streaming visibility technology is proposed, which allows vertices to be in the same task and have The shading information (ie B ^t (v _i )) of the local vertices that have completed shading is visible in real time to speed up information propagation and ensure correctness, and to ensure the reproducibility of the calculation process by globally synchronizing and recording the update order of local vertices; Aiming at the problem of parallel coloring conflicts, two different coloring techniques are proposed, which inject reproducible random disturbances (ie, the first threshold and the second threshold) from the perspectives of coloring timing and color selection to alleviate the coloring conflicts of adjacent vertices, Accelerates convergence. Corresponding technology can directly color vertices without calculating independent sets, which improves computing efficiency, and can convert graph topology deletion based on independent sets into multiple relaxation adjustments of vertex color states, simplifying data management operations; In addition, in the iterative calculation process, by detecting the coloring changes of vertices in real time, the random disturbance intensity (that is, the size of the first threshold and the second threshold) can be dynamically and adaptively adjusted, so as to further improve the calculation on the premise of ensuring the convergence of the algorithm. Parallelism and shading quality.

FIG. 3 is a flowchart of a distributed adaptive graph vertex shading method 300 according to an embodiment of the present invention. As shown in FIG. 3 , the distributed adaptive graph vertex coloring method 300 provided by the embodiment of the present invention starts from step 301, and in step 301, respectively obtains all adjacent vertices of each vertex v _i The coloring information set C ^t-1 ( _vi ) in the iterative process; wherein, t is the current number of iterations.

In step 302, coloring conflict judgment is performed on each vertex vi; wherein, for any vertex vi, if the current value _rs of the probability generator is less than or equal to the first threshold α and the coloring information c _i of the vertex _vi is _satisfied ∈C ^t-1 (v _i ) and c _i ∈ B ^t (v _i ), then it is determined that the vertex vi and its adjacent vertices have a color conflict _{, and the state accumulation monitoring variable si corresponding} to the vertex vi is updated to be the initial threshold; , s _i is used to record the number of iterations that the coloring information of the vertex v _i has not changed continuously; B ^t (vi _{) is the current iteration step that the vertex v i has} received at the update time and is located at the vertex v The shading information of the part of the adjacent vertices of the task where _i is located.

Preferably, wherein the method further comprises:

When judging coloring conflict for each vertex v _i , if the current value rs of the probability generator is not satisfied, the value _rs is less than or equal to the first threshold α and the coloring information of the vertex v _i is c _i ∈ C ^t-1 (vi ₎ And c _i ∈ B ^t (vi ), it is determined that the vertex v _i and its adjacent vertex v _j have no coloring conflict, update s _{i =s i +1} , and go to step 304 directly.

In the embodiment of the present invention, the real-time propagation of shading information is realized based on the shading propagation acceleration technology with visible local message flow. The core point of this technology is to remove the strict constraints on message visibility imposed by the existing synchronous iterative model, and to help this vertex select a more appropriate color by detecting the coloring information of adjacent vertices in the same task in advance, so as to speed up the speed of coloring information dissemination Effect.

In the implementation description of distributed graph vertex coloring, under the constraints of the existing global synchronization model, in the iterative calculation in the lth step, the vertex v _i is only based on the coloring information sent by its adjacent vertices in the (l-1)th step. Set C ^l-1 (vi ) for color selection, and then broadcast to its adjacent vertices; at the same time _, some adjacent vertices of v _i may have completed the coloring selection of this step before _vi and its broadcast message has been successfully Receive and put in C ^l (vi ) to be used to update the coloring of v _i in the iteration of step (l+1 ₎ . However, according to C ^l-1 (vi ), in the iterative calculation in step l, v _i may choose the same color as its adjacent vertices, that is, c _{i ∈} C ^l (vi ₎ , resulting in a coloring conflict. Obviously, if v _i is updating the shading, it can simultaneously refer to C ^l-1 (vi ) (complete shading information from all adjacent vertices) and B ^l (vi _{) (at the time of v i update} , the received , information from the current iteration step and located in the shading information of some adjacent vertices of the task where the vertex vi is located), such shading conflicts can be avoided. In other words, messages sent by local vertices belonging to the same task that are updated prior to v _i are streamed to v _i and can be referenced as they update shading. Let A be the set of all available colors, then the color selection method can be given by formula (1).

In particular, the messages in B ^l (vi _{) are read-only and cannot be deleted, ie only v i is} allowed to visibly refer to the shading information. Otherwise, in the iteration of step (l+1), the coloring information corresponding to the adjacent vertices will be missing, resulting in U( _vi ) being wrongly enlarged when vi _selects the color, resulting in a coloring error. At the time of _i update, the coloring information B ^l (vi ₎ that has been received from the current iteration step and is located at some adjacent vertices of the task where the vertex vi is located is used to judge the coloring conflict. In addition, the visible range of message flow is limited to local, not global, that is, only messages from local vertices of the same task can participate in the update calculation of v _i . This is because in a distributed environment, the vertices that each task is responsible for processing is fixed, and the processing method is serial, which is easy to control the local update order, and then reproduce the calculation process. For example, it can be sorted according to the vertex number size, degree size, etc. that the local task is responsible for processing, and then the vertex calculation is performed in the same order in each iteration. Since the update sequence between vertices is fixed, for each vertex, the messages available for the first iteration in its B ^l ( _vi ) are also fixed and can be strictly reproduced. Conversely, if messages from other tasks in B ^l (v _i ) are allowed to also participate in the update of this step, then due to the uncertainty of the vertex update order on different tasks and the uncontrollability of network delay, in two different iterations During the calculation, it is almost impossible to strictly reproduce the message in B ^l (vi ₎ when calculating v _i .

Figure 4 shows the implementation framework of the local message streaming visibility technology. Compared with the global message striding technology in Figure 2, there are two main differences: (1) The message B1 received in step ¹ is a read-only message, which is visible to the relevant destination vertex and can only be used to guide color selection, are not completely processed, so at iteration (l+1), they are still valid and do not need to be removed from C ^l , this design ensures that vertices can get full adjacency vertex coloring at iteration (l+1) information, otherwise the color selection cannot be performed correctly; (2) the range of visible messages by stride is limited to the messages generated by the local task, excluding other remote tasks, such as the visible messages of task 1 do not include the messages from task 2 and task 3 To ensure that no uncontrollable random factors are introduced in the calculation process, so as to ensure the reproducibility of the calculation.

The embodiment of the present invention adopts a parallel coloring technology based on elastic conflict determination and color selection. The core idea of the elastic coloring technology is to inject elastic random disturbances in the two stages of coloring determination and color selection (ie, Step2 and Step3), to randomize the coloring timing and color selection of adjacent vertices, thereby reducing the probability of coloring conflict and alleviating " Shading Oscillation".

For elastic conflict determination, in an iterative calculation process, the vertex will skip Step2 and Step3 with a certain probability, that is, _vi does not perform conflict determination on the received adjacent vertex coloring information C ^l-1 ( _vi ) and after the conflict occurs Color re-selection. If so, assuming that the random skipping probability generator is _rs ( _0≤rs ≤1) and the skipping threshold is α, the execution logic of Step2 is changed to:

Step2, for any vertex v _i , if r _s ≤α∧c _i ∈C(v _i )∧c _i ∈B ^t (v _i ), it is determined that the vertex v _i has a color conflict with the adjacent vertex, and the result is determined If it is True, you need to jump to Step3 to modify the color.

After adding the skip probability condition, adjacent vertices on different tasks will be colored at the same time with a low probability, thus preventing them from choosing the same color. It should be noted that Step4 is still executed normally, so that the adjacent vertices of _vi can be calculated normally in the next iteration. This also means that even if vi skips Step2 and _Step3 at step l, at step (l+1), it can still receive the complete adjacent vertex coloring information C ^l+1 ( _vi ), so that Coloring conflict determination can be correctly performed when r _s ≤ α.

Therefore, in the embodiment of the present invention, first, all tasks respectively obtain the _coloring information set C ^1-1 ( v _i ); where, l is the current number of iterations. Then, perform coloring conflict judgment on each vertex vi, wherein, for any vertex vi, if the current value of the probability generator _{rs ≤α∧ci ∈C} ^t-1 (vi ) _{∧ci ∈} is satisfied B ^t (v _i ), then determine that the vertex v _i and its adjacent vertices have a coloring conflict, update the state accumulation monitoring variable _si corresponding to the vertex vi to be the initial threshold, and perform the steps of coloring and message broadcasting in turn; wherein, s _i It is used to record the number of iterations that the coloring information of the vertex _vi has not changed continuously; B ^t ( _vi ) is the number of iterations that the vertex _vi has received at the update time from the current iteration step and is located in the task where the vertex vi is located. Coloring information of some adjacent vertices; α is the first threshold; if not satisfied, update s _i =s _i +1, and directly enter the step of message broadcasting.

In step 303, determine the available color set U(vi) corresponding to each vertex v _{i ,} select a color randomly from the available color set U(vi ₎ corresponding to each vertex v _i according to the second threshold β, and determine Shading information c _{i for each vertex v i .}

Preferably, wherein the determining the available color set U(v _i ) corresponding to each vertex v _i , randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i , and determine each vertex The coloring information _ci of _vi , including:

Determine the available color set U(vi ₎ corresponding to each vertex v _i

For any vertex v _i , if |U(vi ₎ | is less than the second threshold β, then color expansion is performed, the maximum used color value is incremented by β as a unit step, and added to the available color set in U( _vi );

Arrange the colors in the current available color set U(v _i ) corresponding to each vertex v _i in ascending order of color numbers, select the top-β colors and put them into the array, and take the value r _c modulo β according to the value of the random shader. The remainder is used as an array subscript for color selection, and the coloring information of each vertex v _i is determined as c _{i_} =arrayOfTop-β[r _c modβ].

而是从可用颜色集合U(v_i)中随机选取一种颜色，即

具体地，可先将U(v_i)中颜色按照颜色编号升序排序，然后将选择范围限定到top-β个颜色并进行随机选择。一种简单有效的随机选择方式为取余法，即将top-β个颜色放入数组中，然后将随机着色器r_c(random coloring)的值模β取余后作为数组下标进行选择，即c_i＝arrayOfTop-β[r_c modβ].特别地，当|U(v_i)|<β时，需进行颜色扩充，即将已用的最大颜色值以β为单位步长自增，然后加入集合U(v_i)中，以确保颜色选择的随机性。因此，本发明实施方式对应的Step3操作如下：In an embodiment of the present invention, a unified minimum selection strategy is no longer used when selecting elastically colored

Instead, a color is randomly selected from the set of available colors U(v _i ), namely

Specifically, the colors in U(v _i ) can be sorted in ascending order of color numbers, and then the selection range is limited to the top-β colors and selected randomly. A simple and effective random selection method is the remainder method, that is, put the top-β colors into an array, and then take the remainder of the value modulo β of the random shader _rc (random coloring) and select it as an array subscript, that is, c _i =arrayOfTop-β[r _{c modβ} ]. In particular, when |U(vi )|<β, color expansion needs to be performed, that is, the maximum color value used is incremented in steps of β, and then added set U( _vi ) to ensure the randomness of color selection. Therefore, the operation of Step 3 corresponding to the embodiment of the present invention is as follows:

若|U(v_i)|<β,则进行颜色扩充，之后按照升序选择top-β个颜色进行随机选色c_i＝arrayOfTop-β[r_c modβ]。Step3, for vertex v _i , let U(vi ₎ be the set of available colors, there should be

If |U(v _i )|<β, color expansion is performed, and then top-β colors are selected in ascending order for random color selection _{c i} =arrayOfTop-β[rc modβ].

Obviously, random disturbances, namely _rs and _rc , are injected into the conflict determination and color selection process of elastic coloring, which challenges the reproducibility of the calculation. To solve this problem, the pseudo-randomness of the random number generator provided by the computer programming language can be used, that is, if the same initialization seed is given, the random number sequence generated by the random number generator during the execution of multiple jobs is identical. Accordingly, the random number generator seed on each task can be set as the task number to ensure that the random number generation sequence on each task is not the same, so as to realize the difference of coloring timing or color selection. On the other hand, for program debugging or fault tolerance, the calculation process can be reproduced only by setting the seed of the random number generator to the same setting and performing a specified number of random operations. It should be emphasized that elastic conflict determination and elastic coloring selection can be used at the same time to further reduce the possibility of coloring conflicts.

In the embodiment of the present invention, when determining the coloring conflict of the vertex v _i , the available color set U(vi ₎ corresponding to each vertex v _i is determined. For any vertex v _i , if |U(vi ₎ | is less than The second threshold β, then color expansion is performed, and the maximum used color value is automatically incremented with β as the unit step, and added to the available color set U(vi ); the current corresponding to each vertex v _i is added _. The colors in the available color set U(v _i ) are arranged in ascending order of color numbers, and the top-β colors are selected and put into the array, and the remainder is taken as the subscript of the array according to the value of the random shader r _c modulo β. , determine the coloring information of each vertex v _i as _{c i_} =arrayOfTop-β[rc modβ].

Preferably, wherein the method further comprises:

Before the next iteration, the first threshold α is dynamically adjusted using the following formula, including:

α=p+(p-dv/maxd)×γ,

γ=|V ^x |/|V|,

Among them, p is the preset basic threshold, the value range is 0 to 1; d _v is the degree of the current vertex v _i , maxd is the maximum degree of all the vertices in the undirected graph, γ is 0 to 1 The convergence control parameter of 1; |V| is the number of all vertices in the undirected graph, and |V ^x | is the number of vertices whose color has not changed in the preset continuous x-step iterative calculation.

Preferably, wherein the method further comprises:

Before the next iteration, the second threshold β is dynamically adjusted using the following formula, including:

γ=|V ^x |/|V|,

为向上取整数运算符，γ为取值为0到1的收敛调控参数；|V|为所述无向图中的全部顶点数量，|V^x|为在预设的连续x步迭代计算中颜色均未发生变化的顶点数量。in,

is an upward integer operator, γ is a convergence control parameter with a value from 0 to 1; |V| is the total number of vertices in the undirected graph, |V ^x | is in the preset continuous x-step iterative calculation The number of vertices for which none of the colors have changed.

In the embodiment of the present invention, in the elastic parallel coloring technology, both conflict determination and color selection need to inject random disturbance, and the degree of disturbance is determined by parameters α and β. The settings of the two parameters will affect the shading parallelism and shading quality. Therefore, it is necessary to dynamically adjust and optimize according to the degree of convergence in the iterative process.

Specifically, for elastic conflict judgment, if the skip threshold α is too low, a large number of vertices will skip the conflict judgment, so that the color convergence is delayed to the subsequent iteration steps, the degree of parallel calculation is reduced, and the time required for iterative convergence is prolonged; If the threshold is too high, most of the vertices are involved in conflict determination, making it difficult to achieve the goal of differentiated coloring timing. Therefore, finding the optimal skip probability (i.e. α) is crucial. Due to the different scales and topological structures of different graph data, the optimal skip probabilities are also different, so it is difficult to measure them uniformly and accurately. In particular, for real graph data, it is considered that the distribution of vertex degrees has a power-law skew characteristic, that is, most vertices have a low degree and a few vertices have a very high degree. Obviously, because of the large number of neighbors, the height vertex has a high probability of coloring conflict. Therefore, a differentiated skip strategy can be set, that is, a higher α is set for low-degree vertices so that most vertices are quickly colored to make the algorithm converge quickly; and a lower α is set for vertices with higher degrees to prevent frequent oscillations. occur. Specifically, through experimental tests, 50% can be selected as the basic threshold p, and differentiated settings are made according to the degrees of different vertices, and the calculation method can be given by formula (2). where d _v is the current vertex degree, maxd is the maximum degree of all vertices in a given graph, and γ is a convergence control parameter ranging from 0 to 1.

α=0.5+(0.5-d _v /maxd)×γ(2)

Obviously, for low-degree vertices, α tends to 1, reducing the skip probability; while for high-degree vertices, α tends to 0, increasing the skip probability to avoid coloring conflicts, but this skip operation obviously reduces parallelism The degree of computation increases the total number of iterations required by the algorithm. In particular, for γ, its setting should be determined by the degree of iterative convergence. Intuitively, when the colors of most vertices have converged and stabilized, the possibility of coloring conflicts will decrease, and the probability threshold can be adjusted higher to reduce the skip probability. The degree of convergence can be measured by continuously monitoring whether the vertex shading state has changed. The specific calculation method is shown in formula (3):

γ=|V ^x |/|V| (3)

where |V| is the total number of vertices on a given graph, and |V ^x | is the number of vertices whose color has not changed in successive x iterations. According to the experimental test, generally taking x=5 can obtain a better control effect.

其中

为向上取整数运算符，而γ的具体值由公式(3)给出。For elastic coloring selection, the range of random color selection (ie, parameter β) is critical. If the random range is too small, the probability of selecting the same color increases, and oscillation is prone to occur, resulting in a decrease in the convergence speed of the algorithm; if the random range is too large, the vertices may be colored with larger colors, reducing the coloring quality of the algorithm results. (ie the total number of colors k used is larger). In order to balance the shading quality and convergence speed, analogous to the dynamic adjustment of α, the β value can be dynamically set according to the degree of algorithm convergence. Intuitively, when the shading state of most vertices is stable, the random color selection range can be appropriately narrowed to improve the shading quality. According to the measured results on a large number of real maps, when 10 is selected as the range base and dynamically adjusted, a better balanced effect can be achieved. So β is calculated as

in

is an upward integer operator, and the specific value of γ is given by formula (3).

At step 304, for each vertex v _i , its shading information c _i is sent to all its adjacent vertices v _j along the edge.

In step 305, it is judged whether the coloring information of each vertex v _i is different from the color of all its adjacent vertices; wherein, if it is satisfied, the coloring information of each vertex in the undirected graph is directly determined; if not, the coloring information of each vertex in the undirected graph is directly determined; Then adjust the first threshold α and the second threshold β according to the running information, and go back to step 1 to re-iterate until the coloring information of each vertex v _i and the colors of all its adjacent vertices are different. Stop, and determine that the undirected Shading information for each vertex in the graph.

As shown in Figure 5, it is the overall implementation framework of the distributed adaptive graph vertex shading technology including m tasks. Before the iterative calculation starts, each task first loads the graph data in parallel and sets the initial parameters. The latter mainly includes: setting the seeds of the random number generator _rs and _rc as the task number, and giving the initial selection thresholds α and β. .After that, in the iterative calculation, cyclic processing is carried out according to the four steps of preparing message, conflict determination, color selection and new message broadcasting. Among them, a reproducible random disturbance is injected in the conflict determination and color selection stages to alleviate the phenomenon of coloring oscillation; and in the conflict determination stage, the next local message B ^l ( _vi ) can be streamed and visible to speed up message dissemination speed. In particular, a state accumulation monitoring variable s _i is set for each vertex v _i to record the number of iteration steps in which the vertex does not continuously perform color selection (that is, it is determined that the color state has not changed), so as to calculate after the end of each step of iterative calculation. Convergence control parameter γ, and then adjust threshold parameters α and β to realize adaptive learning and adjustment of random disturbance speed, and perform dynamic optimization in solving shading oscillation and improving calculation parallelism and shading quality.

FIG. 6 is a schematic structural diagram of a distributed adaptive graph vertex shader system 600 according to an embodiment of the present invention. As shown in FIG. 6 , the distributed adaptive graph vertex shading system 600 provided by the embodiment of the present invention includes: a shading information set acquisition unit 601 , a shading conflict judgment unit 602 , a shading unit 603 , a message broadcasting unit 604 , and a shading information determination unit 601 unit 605.

Preferably, the coloring information set obtaining unit 601 is configured to obtain the coloring information set C ^t-1 (vi ₎ of all adjacent vertices of each vertex v _i in the undirected graph in the previous iteration process; wherein, t is the current iteration number.

Preferably, the coloring conflict judgment unit 602 is configured to perform coloring conflict judgment on each vertex _vi ; wherein, for any vertex vi, if the current value rs of the probability generator is satisfied, the value _rs is less than or equal to the first threshold α and The coloring information c _i ∈ C ^t-1 (vi ) and c _{i ∈} B ^t (vi ₎ of the vertex v _i are determined to have a coloring conflict between the vertex v _i and its adjacent vertices, and the state accumulation corresponding to the vertex vi is updated The monitoring variable _si is the initial threshold; among them, _si is used to record the number of iterations that the coloring information of the vertex _vi has not changed continuously; B ^t (vi ₎ is the received information from the vertex _vi at the update time Shading information of some adjacent vertices at the current iteration step and located in the task where the vertex vi is located.

Preferably, the coloring conflict judgment unit 602 further includes:

When judging coloring conflict for each vertex v _i , if the current value rs of the probability generator is not satisfied, the value _rs is less than or equal to the first threshold α and the coloring information of the vertex v _i is c _i ∈ C ^t-1 (vi ₎ And c _i ∈ B ^t (vi ), it is determined that the vertex v _i and its adjacent vertex v _j have no coloring conflict, update s _{i =s i +1} , and directly enter the message broadcasting unit 604 .

Preferably, wherein the system further comprises:

A first threshold adjustment unit, configured to dynamically adjust the first threshold α by using the following formula before performing the next iteration, including:

α=p+(p-dv/maxd)×γ,

γ=|V ^x |/|V|,

Among them, p is the preset basic threshold, the value range is 0 to 1; d _v is the degree of the current vertex v _i , maxd is the maximum degree of all the vertices in the undirected graph, γ is 0 to 1 The convergence control parameter of 1; |V| is the number of all vertices in the undirected graph, and |V ^x | is the number of vertices whose color has not changed in the preset continuous x-step iterative calculation.

Preferably, the coloring unit 603 is configured to determine the available color set U(v _i ) corresponding to each vertex v _i , and randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i respectively , determine the coloring information c _{i of each vertex v i .}

Preferably, the coloring unit 603 determines the available color set U(v _i ) corresponding to each vertex v _i , and randomly selects a color from the available color set U(vi ₎ corresponding to each vertex v _i , respectively, Determine the shading information _ci for each vertex _vi , including:

Determine the available color set U(vi ₎ corresponding to each vertex v _i

For any vertex v _i , if |U(vi ₎ | is less than the second threshold β, then color expansion is performed, the maximum used color value is incremented by β as a unit step, and added to the available color set in U( _vi );

Arrange the colors in the current available color set U(v _i ) corresponding to each vertex v _i in ascending order of color numbers, select the top-β colors and put them into the array, and take the value r _c modulo β according to the value of the random shader. The remainder is used as an array subscript for color selection, and the coloring information of each vertex v _i is determined as c _{i_} =arrayOfTop-β[r _c modβ].

Preferably, wherein the system further comprises:

The second threshold adjustment unit is configured to dynamically adjust the second threshold β by using the following formula before the next iteration, including:

γ=|V ^x |/|V|,

为向上取整数运算符，γ为取值为0到1的收敛调控参数；|V|为所述无向图中的全部顶点数量，|V^x|为在预设的连续x步迭代计算中颜色均未发生变化的顶点数量。in,

is an upward integer operator, γ is a convergence control parameter with a value from 0 to 1; |V| is the total number of vertices in the undirected graph, |V ^x | is in the preset continuous x-step iterative calculation The number of vertices for which none of the colors have changed.

Preferably, the message broadcasting unit 604 is configured to, for each vertex v _i , send its coloring information c _i to all its adjacent vertices v _j along the edge.

Preferably, the coloring information determining unit 605 is configured to determine whether the coloring information of each vertex v _i is different from the colors of all its adjacent vertices; wherein, if it is satisfied, directly determine each vertex in the undirected graph The coloring information of the vertex; if not satisfied, adjust the first threshold α and the second threshold β according to the running information, and enter the coloring information set acquisition unit to iterate again, until the coloring information of each vertex v _i and all its adjacent vertices. The colors are not stopped at the same time, and the coloring information of each vertex in the undirected graph is determined.

The distributed adaptive graph vertex shading system 600 of the embodiment of the present invention corresponds to the distributed adaptive graph vertex shading method 300 of another embodiment of the present invention, and details are not described herein again.

The present invention has been described with reference to a few embodiments. However, as is known to those skilled in the art, other embodiments than the above disclosed invention are equally within the scope of the invention, as defined by the appended patent claims.

Generally, all terms used in the claims are to be interpreted according to their ordinary meaning in the technical field, unless explicitly defined otherwise herein. All references to "a/the/the [means, component, etc.]" are open to interpretation as at least one instance of said means, component, etc., unless expressly stated otherwise. The steps of any method disclosed herein do not have to be performed in the exact order disclosed, unless explicitly stated.

As will be appreciated by those skilled in the art, the embodiments of the present application may be provided as a method, a system, or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present application is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the present application. It will be understood that each flow and/or block in the flowchart illustrations and/or block diagrams, and combinations of flows and/or blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to the processor of a general purpose computer, special purpose computer, embedded processor or other programmable data processing device to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing device produce Means for implementing the functions specified in a flow or flow of a flowchart and/or a block or blocks of a block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions The apparatus implements the functions specified in the flow or flow of the flowcharts and/or the block or blocks of the block diagrams.

These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in the flow or blocks of the flowcharts and/or the block or blocks of the block diagrams.

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention rather than to limit them. Although the present invention has been described in detail with reference to the above embodiments, those of ordinary skill in the art should understand that: the present invention can still be Modifications or equivalent replacements are made to the specific embodiments of the present invention, and any modifications or equivalent replacements that do not depart from the spirit and scope of the present invention shall be included within the protection scope of the claims of the present invention.

Claims (10)

1. A distributed adaptive graph vertex coloring method, wherein the method comprises: Step 1, respectively obtain the coloring information set C ^t-1 (vi ₎ of all adjacent vertices of each vertex v _i in the undirected graph in the previous iteration process; wherein, t is the current number of iterations; Step 2: Perform coloring conflict judgment on each vertex vi; wherein, for any vertex vi, if the current probability generator value _rs is less than or equal to the first threshold α and the coloring information c _{i ∈} of the vertex vi is _satisfied C ^t-1 (v _i ) and c _i ∈ B ^t (v _i ), then determine that the vertex vi and its adjacent vertices have a color conflict, and update the state accumulation monitoring variable _si corresponding to the vertex _vi to be the initial threshold; where, s _i is used to record the number of iterations that the coloring information of the vertex v _i has not changed continuously; B ^t (vi ₎ is the current iteration step that the vertex v _i has received at the update time and is located at the vertex v _i The coloring information of some adjacent vertices of the task; Step 3: Determine the available color set U(v _i ) corresponding to each vertex v _i , and randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i according to the second threshold β, and determine each color. coloring information c _{i of each vertex v i ;} Step 4, for each vertex v _i , send its coloring information c _i to all its adjacent vertices v _j along the edge; Step 5, determine whether the coloring information of each vertex v _i is different from the color of all its adjacent vertices; wherein, if it is satisfied, then directly determine the coloring information of each vertex in the undirected graph; if not, then Adjust the first threshold α and the second threshold β according to the running information, and return to step 1 to re-iterate until the coloring information of each vertex v _i and the colors of all its adjacent vertices are different, stop, and determine the undirected graph Shading information for each vertex in . 2. The method according to claim 1, wherein the method further comprises: When judging coloring conflict for each vertex v _i , if the current value rs of the probability generator is not satisfied, the value _rs is less than or equal to the first threshold α and the coloring information of the vertex v _i is c _i ∈ C ^t-1 (vi ₎ And c _i ∈ B ^t (vi ), then it is determined that the vertex v _i and its adjacent vertex v _j have no coloring conflict, update s _{i =s i +1} , and go to step 4 directly. 3. The method according to claim 1, wherein the method further comprises: Before the next iteration, the first threshold α is dynamically adjusted using the following formula, including: α=p+(p-dv/maxd)×γ, γ=|V ^x |/|V|, Among them, p is the preset basic threshold, the value range is 0 to 1; d _v is the degree of the current vertex v _i , maxd is the maximum degree of all the vertices in the undirected graph, γ is 0 to 1 The convergence control parameter of 1; |V| is the number of all vertices in the undirected graph, and |V ^x | is the number of vertices whose color has not changed in the preset continuous x-step iterative calculation. 4. The method according to claim 1, characterized in that, said determining the available color set U(vi) corresponding to each vertex v _i , respectively from the available color set U(vi ₎ corresponding to each vertex v _{i .} ) and randomly select a color to determine the coloring information c _i of each vertex v _i , including: Determine the available color set U(vi ₎ corresponding to each vertex v _i For any vertex v _i , if |U(vi ₎ | is less than the second threshold β, then color expansion is performed, the maximum used color value is incremented by β as a unit step, and added to the available color set in U( _vi ); Arrange the colors in the current available color set U(v _i ) corresponding to each vertex v _i in ascending order of the color numbers, select the top-β colors and put them into the array, and get them according to the value r _c modulo β of the random shader. The remainder is used as an array subscript for color selection, and the coloring information of each vertex v _i is determined as c _i _=arrayOfTop-β[rc _modβ ]. 5. The method according to claim 4, wherein the method further comprises: Before the next iteration, the second threshold β is dynamically adjusted using the following formula, including:

γ=|V ^x |/|V|, in,

is an upward integer operator, γ is a convergence control parameter with a value from 0 to 1; |V| is the total number of vertices in the undirected graph, |V ^x | is in the preset continuous x-step iterative calculation The number of vertices for which none of the colors have changed. 6. A distributed adaptive graph vertex shader system, wherein the system comprises: The coloring information set acquisition unit is used to obtain the coloring information set C ^t-1 (vi ₎ of all adjacent vertices of each vertex v _i in the undirected graph in the previous iteration process; wherein, t is the current number of iterations ; The coloring conflict judgment unit is used to judge the coloring conflict for each vertex _vi ; wherein, for any vertex vi, if the value rs of the current probability generator is satisfied that the value _rs of the current probability generator is less than or equal to the first threshold α and the coloring of the vertex _vi is Information c _i ∈ C ^t-1 (vi ) and c _{i ∈} B ^t (vi ₎ , then determine that the vertex vi and its adjacent vertices have coloring conflicts, and update the state accumulation monitoring variable _si corresponding to the vertex _vi to be the initial Threshold; wherein, s _i is used to record the number of iterations that the coloring information of the vertex v _i has not changed continuously; B ^t (vi _{) is the current iteration step that the vertex v i has} received at the update time and is located in The coloring information of some adjacent vertices of the task where the vertex v _i is located; The coloring unit is used to determine the available color set U(v _i ) corresponding to each vertex v _i , and randomly select a color from the available color set U(vi ₎ corresponding to each vertex v _i according to the second threshold β, Determine the coloring information c _{i of each vertex v i ;} a message broadcasting unit, for each vertex v _i , sending its coloring information c _i to all its adjacent vertices v _j along the edge; A coloring information determination unit, used to determine whether the coloring information of each vertex v _i is different from the color of all its adjacent vertices; wherein, if it is satisfied, the coloring information of each vertex in the undirected graph is directly determined; if If not satisfied, then adjust the first threshold α and the second threshold β according to the running information, and enter the coloring information set acquisition unit to iterate again, until the coloring information of each vertex v _i and the colors of all its adjacent vertices are different, then stop, And determine the coloring information of each vertex in the undirected graph. 7. The system according to claim 6, wherein the coloring conflict judgment unit further comprises: When judging coloring conflict for each vertex v _i , if the current value rs of the probability generator is not satisfied, the value _rs is less than or equal to the first threshold α and the coloring information of the vertex v _i is c _i ∈ C ^t-1 (vi ₎ And c _i ∈ B ^t (vi ), it is determined that the vertex v _i and its adjacent vertex v _j have no coloring conflict, update s _{i =s i +1} , and directly enter the message broadcasting unit. 8. The system of claim 6, wherein the system further comprises: A first threshold adjustment unit, configured to dynamically adjust the first threshold α by using the following formula before performing the next iteration, including: α=p+(p-dv/maxd)×γ, γ=|V ^x |/|V|, Among them, p is the preset basic threshold, the value range is 0 to 1; d _v is the degree of the current vertex v _i , maxd is the maximum degree of all vertices in the undirected graph, γ is 0 to 1 The convergence control parameter of 1; |V| is the number of all vertices in the undirected graph, and |V ^x | is the number of vertices whose color has not changed in the preset continuous x-step iterative calculation. 9. The system according to claim 6, wherein the coloring unit determines the available color set U(v _i ) corresponding to each vertex v _i , respectively, from the available color set U corresponding to each vertex v _i (v _i ) randomly select a color to determine the coloring information c _i of each vertex v _i , including: Determine the available color set U(vi ₎ corresponding to each vertex v _i For any vertex v _i , if |U(vi ₎ | is less than the second threshold β, then color expansion is performed, the maximum used color value is incremented by β as a unit step, and added to the available color set in U( _vi ); Arrange the colors in the current available color set U(v _i ) corresponding to each vertex v _i in ascending order of the color numbers, select the top-β colors and put them into the array, and get them according to the value r _c modulo β of the random shader. The remainder is used as an array subscript for color selection, and the coloring information of each vertex v _i is determined as c _i _=arrayOfTop-β[rc _modβ ]. 10. The system of claim 9, wherein the system further comprises: The second threshold adjustment unit is configured to dynamically adjust the second threshold β by using the following formula before the next iteration, including:

γ=|V ^x |/|V|, in,

is an upward integer operator, γ is a convergence control parameter with a value from 0 to 1; |V| is the total number of vertices in the undirected graph, |V ^x | is in the preset continuous x-step iterative calculation The number of vertices for which none of the colors have changed.

Images