CN118839036B - Method, device and equipment for calculating connected components facing long-diameter dense chart - Google Patents
Method, device and equipment for calculating connected components facing long-diameter dense chart Download PDFInfo
- Publication number
- CN118839036B CN118839036B CN202411327354.7A CN202411327354A CN118839036B CN 118839036 B CN118839036 B CN 118839036B CN 202411327354 A CN202411327354 A CN 202411327354A CN 118839036 B CN118839036 B CN 118839036B
- Authority
- CN
- China
- Prior art keywords
- dense
- vertices
- long
- graph
- vertex
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/90—Details of database functions independent of the retrieved data types
- G06F16/901—Indexing; Data structures therefor; Storage structures
- G06F16/9024—Graphs; Linked lists
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Software Systems (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Traffic Control Systems (AREA)
Abstract
According to the characteristics of a long-diameter dense chart, after the long-diameter dense chart to be processed is obtained, dense vertexes and sparse vertexes in the long-diameter dense chart are marked firstly, then starting from the identity of the vertex with the highest second-order neighbor number, the other vertexes in the long-diameter dense chart are iteratively visited by adopting a BFS algorithm to obtain the connected components of the dense vertexes, then the other non-visited vertexes in the long-diameter dense chart are visited by adopting a UF algorithm, and finally all the connected components in the long-diameter dense chart are obtained. The advantages of the BFS algorithm and the UF algorithm are effectively utilized by combining the BFS algorithm and the UF algorithm in different stages of the calculation process of the connected components of the diameter dense chart, the calculation cost of the connected components of the long diameter dense chart is greatly reduced, and the calculation performance of the connected components of the long diameter dense chart is remarkably improved.
Description
Technical Field
The invention belongs to the technical field of graph calculation, and relates to a connected component calculation method, device and equipment for a long-diameter dense graph.
Background
A Graph (Graph) is an abstract data structure for representing the association between objects, and is described using vertices (Vertex) representing objects and edges (Edge) representing the relationship between objects. The data that can be abstracted into the graphic description is the graphic data. Graph calculation is a process of expressing and solving a problem by using a graph as a data model. A sub-graph is a subset of the graph, consisting of partial vertices and edges in the graph. The connected component is actually a sub-graph, each vertex of which can be directly or indirectly connected to other vertices within the sub-graph. Therefore, for different connected components, there is no possibility of a connection relationship between them. The connected component algorithm (CC) aims to find all connected components in the graph. The diameter of a graph is defined as the maximum of the shortest distance from any vertex to other vertices in the graph, while a dense graph refers to the presence of a sub-graph in the graph with a higher average degree of sub-graph, i.e. complex connections between vertices. In order to calculate the connected components of the graph, a connected component calculation method based on BFS (Briath FIRST SEARCH, breadth-first traversal), a UF (Union-Find, search) method, a variant of the UF (Union-Find), and the like are presented, however, the traditional connected component calculation method still has the technical problem of higher calculation cost when facing to the calculation of a long-diameter dense graph.
Disclosure of Invention
Aiming at the problems in the traditional method, the invention provides a connected component calculation method facing a long-diameter dense chart, a connected component calculation device facing the long-diameter dense chart and a computer device, which can greatly reduce the calculation cost when the connected component facing the long-diameter dense chart is calculated.
In order to achieve the above object, the embodiment of the present invention adopts the following technical scheme:
in one aspect, a method for computing connected components of a long-diameter dense chart is provided, which includes the steps of:
Acquiring a long-diameter dense chart to be processed, wherein the long-diameter dense chart is a traffic road network or a communication network;
preprocessing is carried out on the long-diameter dense chart, and dense vertexes and sparse vertexes in the long-diameter dense chart are marked;
starting from the identification of the vertex with the highest second-order neighbor number, iteratively accessing other vertices in the long-diameter dense chart by adopting a BFS algorithm until all dense vertices are accessed;
accessing the non-accessed vertexes in the long-diameter dense chart by adopting a UF algorithm;
And outputting the connected components obtained after the BFS algorithm and the UF algorithm access to the vertexes in the long-diameter dense chart as all connected components in the long-diameter dense chart, wherein the connected components are used for node identification of a traffic network or are used for connectivity and redundancy analysis of the traffic network.
In one embodiment, in the process of marking dense vertexes and sparse vertexes in the long-diameter dense chart, the square of the average degree of the chart of the long-diameter dense chart is used as a set threshold value, and the set threshold value is used for judging whether the vertexes in the long-diameter dense chart are dense vertexes or sparse vertexes.
In another aspect, there is also provided a connected component calculation apparatus for a long-diameter dense chart, including:
the image acquisition module is used for acquiring a long-diameter dense image to be processed; the long diameter dense chart is a traffic road network or a communication network;
the preprocessing module is used for preprocessing the long-diameter dense chart and marking dense vertexes and sparse vertexes in the long-diameter dense chart;
The first access module is used for iteratively accessing other vertexes in the long-diameter dense chart by adopting a BFS algorithm from the identification mark of the vertex with the highest second-order neighbor number until all dense vertexes are accessed;
the second access module is used for accessing the non-accessed vertexes in the long-diameter dense chart by adopting a UF algorithm;
And the component output module is used for outputting the connected components obtained after the BFS algorithm and the UF algorithm access to the vertexes in the long-diameter dense chart as all connected components in the long-diameter dense chart, wherein the connected components are used for node identification of a traffic network or are used for connectivity and redundancy analysis of the communication network.
In one embodiment, the preprocessing module uses the square of the average degree of the long-diameter dense chart as a set threshold value in the process of marking dense vertexes and sparse vertexes in the long-diameter dense chart, and the set threshold value is used for judging whether the vertexes in the long-diameter dense chart are dense vertexes or sparse vertexes.
In yet another aspect, a computer device is provided, including a memory storing a computer program and a processor implementing the steps of the above-described connected component calculation method for long diameter dense maps when the computer program is executed.
One of the above technical solutions has the following advantages and beneficial effects:
According to the method, the device and the equipment for calculating the connected components of the long-diameter dense chart, according to the characteristics of the long-diameter dense chart, after the long-diameter dense chart to be processed is obtained, firstly, dense vertexes and sparse vertexes in the long-diameter dense chart are marked, then, starting from the identity of the vertex with the highest second-order neighbor number, the BFS algorithm is adopted to iteratively access other vertexes in the long-diameter dense chart, after the connected components of the dense vertexes are obtained, the UF algorithm is adopted to access other non-accessed vertexes in the long-diameter dense chart, and finally, all the connected components in the diameter dense chart are obtained. The advantages of the BFS algorithm and the UF algorithm are effectively utilized by combining the BFS algorithm and the UF algorithm in different stages of the calculation process of the connected components of the diameter dense chart, the calculation cost of the connected components of the long diameter dense chart is greatly reduced, and the calculation performance of the connected components of the long diameter dense chart is remarkably improved.
Drawings
In order to more clearly illustrate the technical solutions of the embodiments or the conventional techniques of the present invention, the drawings required for the descriptions of the embodiments or the conventional techniques will be briefly described below, and it is apparent that the drawings in the following description are only some embodiments of the present invention, and other drawings may be obtained according to the drawings without inventive effort for those skilled in the art.
FIG. 1 is a flow diagram of a connected component calculation method facing a long diameter dense chart in one embodiment;
FIG. 2 is a block diagram of a modular construction of a connected component computing device facing a long diameter dense map in one embodiment.
Detailed Description
The present invention will be described in further detail with reference to the drawings and examples, in order to make the objects, technical solutions and advantages of the present invention more apparent. It should be understood that the specific embodiments described herein are for purposes of illustration only and are not intended to limit the scope of the invention. Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this invention belongs. The terminology used in the description of the invention herein is for the purpose of describing particular embodiments only and is not intended to be limiting of the invention.
It is noted that reference herein to "an embodiment" means that a particular feature, structure, or characteristic described in connection with the embodiment may be included in at least one embodiment of the invention. The appearances of the phrase in various places in the specification are not necessarily all referring to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Those skilled in the art will appreciate that the embodiments described herein may be combined with other embodiments. The term "and/or" as used in the present specification and the appended claims refers to any and all possible combinations of one or more of the associated listed items, and includes such combinations.
Embodiments of the present invention will be described in detail below with reference to the attached drawings in the drawings of the embodiments of the present invention.
The communication component calculation method based on BFS is to traverse all the traversable vertexes according to BFS algorithm starting from a certain non-visited vertex, at this time, the visited vertexes of BFS form a communication component, and then repeat the above process until all the vertexes are visited. The method comprises the steps of carrying out a calculation mode of connected components of UF and variants thereof, initializing the calculation mode of connected components of UF and variants thereof, enabling all vertexes to set own labels as self IDs (identity marks), firstly traversing all vertexes to set own labels as labels with minimum (or set as maximum can also not influence algorithm correctness, taking minimum as an example) of neighbor vertexes, secondly traversing all vertexes from the vertex with minimum ID from small to large, carrying out a label updating operation, wherein the label updating operation is a recursion operation, if a label corresponds to a vertex, if the label does not equal to the ID of the vertex, continuing to visit the vertex corresponding to the label and continuing the recursion until finding a vertex with the label equal to the ID of the vertex, and setting the label of the vertex as the current vertex label.
Through intensive research, it was found that the BFS-based Connected Component (CC) calculation method is excellent in dense areas because vertex labels do not change frequently in the BFS algorithm. However, when the graph is long and sparse, such as in road network data, the BFS algorithm performs worse, theoretically, because each iteration of BFS can only progress one layer, when a chain-like structure exists, the BFS algorithm needs to perform multiple rounds to finish, and the calculation cost is high. The UF and its variant algorithm has high efficiency in processing sparse graphs, and even in processing chain structures, only log (N) iterations are needed to complete the calculation. In dense graphs, the IDs of the vertices themselves are frequently updated, which results in higher computation overhead. Therefore, for graphs with dense areas and long-diameter sparse areas, it is difficult to obtain higher performance by the existing CC calculation method, and new calculation methods continue to be designed to solve the aforementioned technical problems.
In one embodiment, as shown in fig. 1, a method for computing connected components for a long diameter dense chart is provided, which may include the following processing steps S10 to S18:
S10, acquiring a long-diameter dense chart to be processed, wherein the long-diameter dense chart is a traffic road network or a communication network. It will be appreciated that the system may obtain long diameter dense maps that currently require computational processing, by way of, but not limited to, direct acquisition, database pulling, or user uploading. The long diameter dense map to be processed may be, for example, traffic road networks and communication networks of large cities, people gathering areas, which are relatively dense, but city and people sparse areas with backward economic development, which traffic road networks and communication networks are relatively sparse, and the paths from the latter to the former generally conform to the characteristics of long diameters, so these networks may be represented by long diameter dense maps, and for convenience of explanation, a city/a certain place may be regarded as the vertices in the long diameter dense map, and a road may be regarded as the edges in the long diameter dense map, taking the traffic road network as an example of the long diameter dense map to be processed. Edges can be classified into classes according to the nature of roads (rural roads, highways, national roads and highways), vertices can also be classified into classes according to the nature of vehicles, e.g. a large truck may not be able to travel on a rural road, so that the problem of accessibility of a certain truck between two places can be solved using the method of the invention and can be used to identify key vertices in the graph, randomly deleting a certain vertex or vertices and its adjacent edges, and indicating that the vertices are more important if the increased connectivity components become more.
Accordingly, for a communication network, both the base stations and the terminal devices in the network can be considered vertices in the long diameter dense chart, and the communication links between the devices can be considered edges in the long diameter dense chart.
S12, preprocessing is carried out on the long-diameter dense chart, and dense vertexes and sparse vertexes in the long-diameter dense chart are marked.
Specifically, a preprocessing stage is performed on the long-diameter dense graph, wherein the number of second-order neighbors (second-order neighbors are adjacent vertexes of adjacent vertexes) of all vertexes is counted respectively, when the number of second-order neighbors of any vertex exceeds a set threshold value, the vertex is marked as a dense vertex, otherwise, the vertex is marked as a sparse vertex, meanwhile, the ID of the vertex with the highest number of second-order neighbors is recorded and can be marked as vmax, and the total number of dense vertexes is recorded and can be marked as densenum. The setting threshold value may be generally set based on historical experience, or may be set based on the average degree of the map of the long-diameter dense map of the current calculation process, as long as it can be used to accurately distinguish dense vertices from sparse vertices.
S14, starting from the identification of the vertex with the highest second-order neighbor number, iteratively accessing other vertices in the long-diameter dense chart by adopting a BFS algorithm until all dense vertices are accessed.
It can be understood that starting from the vertex corresponding to vmax, other vertices are iteratively visited in a calculation mode of the BFS algorithm, during each iteration, the newly visited vertices are stored in the active array active [ ], then the number of dense vertices stored therein is counted, and then densenum is updated (i.e. the number of dense vertices in the active [ ] is subtracted). When the number of dense vertices in densenum is 0, the transition is made to execute the UF algorithm.
S16, accessing the non-accessed vertexes in the long-diameter dense chart by adopting a UF algorithm;
And S18, outputting the connected components obtained after the BFS algorithm and the UF algorithm access to the vertexes in the long-diameter dense chart as all connected components in the long-diameter dense chart, wherein the connected components are used for node identification of a traffic network or are used for connectivity and redundancy analysis of the communication network.
Specifically, UF algorithm is executed on the non-accessed peaks in the long-diameter dense chart, all connected components in the long-diameter dense chart are obtained after calculation is completed, and the calculation process is finished. All connected components in the calculated long diameter dense map can be used to identify individual traffic subsystems in the traffic network. If a certain part of a certain dense chart is segmented (such as road closure or airport outage), communication component analysis can quickly identify which traffic nodes still remain communicated and which are separated, so that emergency traffic scheduling or resource allocation planning can be effectively formulated, and efficient operation of a traffic network can be maintained.
In a communication network, all connected components in the calculated long diameter dense map can be used to evaluate connectivity and redundancy of the communication network. By analyzing connectivity components in dense communication networks, network design/operation staff can quickly learn which parts remain connected if certain communication nodes or paths fail and which parts are split, thereby helping to optimize the communication network structure to improve its fault tolerance and reliability.
Specifically, UF algorithm is executed on the non-accessed peaks in the long-diameter dense chart, all connected components in the long-diameter dense chart are obtained after calculation is completed, and the calculation process is finished.
It can be understood that, on the basis of researching the characteristics of the long-diameter dense chart and the limitations of the traditional computing method, the embodiment combines the advantages of the two computing methods, firstly, the iteration model of the BFS algorithm is used, but the algorithm termination condition is modified, instead of accessing all accessible vertexes and stopping, accessing the dense area of the long-diameter dense chart is stopped, then, the method is converted into a UF algorithm with higher efficiency on the sparse chart, and finally, the computing cost is greatly reduced when the connected component computing of the long-diameter dense chart is finally realized.
According to the method for calculating the connected components of the long-diameter dense chart, after the long-diameter dense chart to be processed is obtained according to the characteristics of the long-diameter dense chart, firstly, dense vertexes and sparse vertexes in the long-diameter dense chart are marked, then, starting from the identity of the vertex with the highest second-order neighbor number, the other vertexes in the long-diameter dense chart are iteratively visited by adopting a BFS algorithm to obtain the connected components of the dense vertexes, then, the other non-visited vertexes in the long-diameter dense chart are visited by adopting a UF algorithm, and finally, all the connected components in the diameter dense chart are obtained. The advantages of the BFS algorithm and the UF algorithm are effectively utilized by combining the BFS algorithm and the UF algorithm in different stages of the calculation process of the connected components of the diameter dense chart, the calculation cost of the connected components of the long diameter dense chart is greatly reduced, and the calculation performance of the connected components of the long diameter dense chart is remarkably improved.
In one embodiment, regarding the above step S12, in the process of marking the dense vertices and the sparse vertices in the long-diameter dense map, the square of the average degree of the map of the long-diameter dense map is used as a set threshold, and the set threshold is used to determine whether the vertices in the long-diameter dense map are dense vertices or sparse vertices.
It can be understood that, in the present embodiment, intelligence is provided with the square of the average degree of the drawing of the long-diameter dense drawing currently calculated as a set threshold, and a vertex marking effect of higher accuracy can be achieved corresponding to the long-diameter dense drawing. The calculation of the average degree of the graph can be understood by referring to the existing calculation mode of the average degree of the graph in the prior art, and the detailed description will not be repeated in this embodiment.
It should be understood that, although the steps in the flowchart of fig. 1 are shown in sequence as indicated by the arrows, the steps are not necessarily performed in sequence as indicated by the arrows. The steps are not strictly limited to the order of execution unless explicitly recited herein, and the steps may be executed in other orders. Moreover, at least some of the steps in fig. 1 may include multiple sub-steps or stages that are not necessarily performed at the same time, but may be performed at different times, nor do the order in which the sub-steps or stages are performed necessarily performed in sequence, but may be performed alternately or alternately with at least a portion of other steps or sub-steps of other steps.
In one embodiment, as shown in fig. 2, there is further provided a connected component computing device 100 for a long diameter dense chart, including a chart acquisition module 11, a preprocessing module 13, a first access module 15, a second access module 17, and a component output module 19. The map acquisition module 11 is used for acquiring a long-diameter dense map to be processed, wherein the long-diameter dense map is a traffic road network or a communication network. The preprocessing module 13 is used for preprocessing the long-diameter dense map and marking dense vertexes and sparse vertexes in the long-diameter dense map. The first accessing module 15 is configured to iteratively access other vertices in the long-diameter dense chart by using a BFS algorithm, starting from the identity of the vertex with the highest second-order neighbor number, until all dense vertices have been accessed. The second access module 17 is configured to access the non-accessed vertices in the long diameter dense map using a UF algorithm. The component output module 19 is configured to output, as all connected components in the long-diameter dense graph, connected components obtained after the BFS algorithm and the UF algorithm have completed access to vertices in the long-diameter dense graph, where the connected components are used for node identification of the traffic network or for connectivity and redundancy analysis of the traffic network.
According to the characteristics of the long-diameter dense chart, the above connected component calculating device 100 facing the long-diameter dense chart firstly marks dense vertexes and sparse vertexes in the long-diameter dense chart, then iteratively accesses other vertexes in the long-diameter dense chart by adopting a BFS algorithm from the identity of the vertex with the highest second-order neighbor number to obtain the connected components of the dense vertexes, then accesses other non-accessed vertexes in the long-diameter dense chart by adopting a UF algorithm to finally obtain all the connected components in the diameter dense chart. The advantages of the BFS algorithm and the UF algorithm are effectively utilized by combining the BFS algorithm and the UF algorithm in different stages of the calculation process of the connected components of the diameter dense chart, the calculation cost of the connected components of the long diameter dense chart is greatly reduced, and the calculation performance of the connected components of the long diameter dense chart is remarkably improved.
In one embodiment, the preprocessing module 13 uses the square of the average degree of the long-diameter dense chart as a set threshold value in the process of marking dense vertexes and sparse vertexes in the long-diameter dense chart, and the set threshold value is used for distinguishing that the vertexes in the long-diameter dense chart are dense vertexes or sparse vertexes.
For the specific definition of the connected component calculation means 100 facing the long-diameter dense chart, reference may be made to the definition of the connected component calculation method facing the long-diameter dense chart hereinabove, and the description thereof will not be repeated. The various modules in the long diameter dense map oriented connected component computing device 100 described above may be implemented in whole or in part by software, hardware, and combinations thereof. The above modules may be embedded in hardware or may be independent of a processor in the computer device, or may be stored in software in a memory in the computer device, so that the processor may call and execute operations corresponding to the above modules.
In one embodiment, a computer device is provided, comprising a memory and a processor, wherein the memory stores a computer program, the processor realizes the following processing steps when executing the computer program, namely, acquiring a long-diameter dense chart to be processed, wherein the long-diameter dense chart is a traffic road network or a communication network, executing pretreatment on the long-diameter dense chart, marking dense vertexes and sparse vertexes in the long-diameter dense chart, iteratively accessing other vertexes in the long-diameter dense chart by adopting a BFS algorithm from the identification mark of the vertex with the highest second-order neighbor number until all the dense vertexes have been accessed, accessing the non-accessed vertexes in the long-diameter dense chart by adopting a UF algorithm, outputting communication components obtained after completing the access to the vertexes in the long-diameter dense chart by adopting the BFS algorithm and the UF algorithm as all the communication components in the long-diameter dense chart, and using the communication components for node identification of the traffic road network or for connectivity and redundancy analysis of the communication network.
It will be appreciated that the above-mentioned computer device may include other software and hardware components not listed in the specification besides the above-mentioned memory and processor, and may be specifically determined according to the model of the specific drawing computing device in different application scenarios, which will not be listed in detail in the specification.
In one embodiment, the processor may also implement the steps or sub-steps added to the embodiments of the long diameter dense chart oriented connected component calculation method described above when executing the computer program.
In one embodiment, a computer readable storage medium is provided, on which a computer program is stored, which when executed by a processor, performs the processing steps of obtaining a long diameter dense graph to be processed, the long diameter dense graph being a traffic network or a communication network, performing preprocessing on the long diameter dense graph, marking dense vertices and sparse vertices in the long diameter dense graph, iteratively accessing other vertices in the long diameter dense graph by using a BFS algorithm from an identity of a vertex with the highest number of second order neighbors until all dense vertices have been accessed, accessing vertices not accessed in the long diameter dense graph by using a UF algorithm, outputting connected components obtained after completing the access to the vertices in the long diameter dense graph by using the BFS algorithm and the UF algorithm as all connected components in the long diameter dense graph, wherein the connected components are used for node identification of the traffic network or are used for connectivity and redundancy analysis of the communication network.
Those skilled in the art will appreciate that implementing all or part of the above-described methods may be accomplished by way of a computer program, which may be stored on a non-transitory computer readable storage medium and which, when executed, may comprise the steps of the above-described embodiments of the methods. Any reference to memory, storage, database, or other medium used in embodiments provided herein may include non-volatile and/or volatile memory. The nonvolatile memory can include Read Only Memory (ROM), programmable ROM (PROM), electrically Programmable ROM (EPROM), electrically Erasable Programmable ROM (EEPROM), or flash memory. Volatile memory can include Random Access Memory (RAM) or external cache memory. By way of illustration and not limitation, RAM is available in a variety of forms such as Static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double Data Rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous link (SYNCHLINK) DRAM (SLDRAM), memory bus dynamic random access memory (Rambus DRAM, RDRAM for short), and interface dynamic random access memory (DRDRAM), among others.
The technical features of the above embodiments may be arbitrarily combined, and all possible combinations of the technical features in the above embodiments are not described for brevity of description, however, as long as there is no contradiction between the combinations of the technical features, they should be considered as the scope of the description.
The foregoing examples illustrate only a few embodiments of the invention, which are described in detail and are not to be construed as limiting the scope of the invention. It should be noted that it is possible for those skilled in the art to make several variations and modifications without departing from the spirit of the present invention, which fall within the protection scope of the present invention. The scope of the invention should therefore be pointed out in the appended claims.
Claims (5)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411327354.7A CN118839036B (en) | 2024-09-23 | 2024-09-23 | Method, device and equipment for calculating connected components facing long-diameter dense chart |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202411327354.7A CN118839036B (en) | 2024-09-23 | 2024-09-23 | Method, device and equipment for calculating connected components facing long-diameter dense chart |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN118839036A CN118839036A (en) | 2024-10-25 |
| CN118839036B true CN118839036B (en) | 2024-12-17 |
Family
ID=93145973
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202411327354.7A Active CN118839036B (en) | 2024-09-23 | 2024-09-23 | Method, device and equipment for calculating connected components facing long-diameter dense chart |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN118839036B (en) |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105955883A (en) * | 2016-04-27 | 2016-09-21 | 中国科学院软件研究所 | Single-machine multi-core parallel model checking method with high performance |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US10521473B2 (en) * | 2012-05-21 | 2019-12-31 | Kent State University | Shortest path computation in large networks |
| US8971665B2 (en) * | 2012-07-31 | 2015-03-03 | Hewlett-Packard Development Company, L.P. | Hierarchical cluster determination based on subgraph density |
| US10795672B2 (en) * | 2018-10-31 | 2020-10-06 | Oracle International Corporation | Automatic generation of multi-source breadth-first search from high-level graph language for distributed graph processing systems |
| CN112883241B (en) * | 2021-03-19 | 2022-09-09 | 中国人民解放军国防科技大学 | A Supercomputer Benchmark Acceleration Method Based on Connected Component Generation Optimization |
| CN117131231A (en) * | 2023-09-12 | 2023-11-28 | 广东电网有限责任公司 | Maximum connected subgraph dividing method and system |
-
2024
- 2024-09-23 CN CN202411327354.7A patent/CN118839036B/en active Active
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105955883A (en) * | 2016-04-27 | 2016-09-21 | 中国科学院软件研究所 | Single-machine multi-core parallel model checking method with high performance |
Non-Patent Citations (1)
| Title |
|---|
| 面向大规模图计算的连通分量算法分析与优化;白皓;甘新标;杨文祥;贾孟涵;涂旭平;张一鸣;郭敏;来乐;张意;朱春平;《计算机工程与科学》;20220215;第44卷(第2期);第191-198页 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN118839036A (en) | 2024-10-25 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN112902970B (en) | Routing inspection path planning method and routing inspection robot | |
| CN105404648A (en) | Density and closeness clustering based user moving behavior determination method | |
| CN101900565A (en) | Path determining method and device | |
| CN114281915B (en) | Method, device and equipment for generating geometric road network and storage medium | |
| CN108280463A (en) | Method and device for optimizing the double-layer path of a vehicle equipped with an unmanned aerial vehicle | |
| CN110826244B (en) | Conjugated gradient cellular automaton method for simulating influence of rail transit on urban growth | |
| CN113487869B (en) | Congestion bottleneck point determination method, device, computer equipment and storage medium | |
| CN117576569A (en) | Multi-target detection model and method for urban capacity event management | |
| CN117634704A (en) | A site selection optimization method, system, equipment and medium for tourist attractions | |
| CN113677583B (en) | Graph calculation-based vehicle driving data processing method and device and computer equipment | |
| CN115100231B (en) | Method and device for determining regional boundary | |
| CN114705180B (en) | Data correction method, device and equipment for high-precision map and storage medium | |
| CN118839036B (en) | Method, device and equipment for calculating connected components facing long-diameter dense chart | |
| CN117668004A (en) | Method for acquiring shortest path between nodes | |
| CN114238533A (en) | User commuting route planning method, device, computer equipment and storage medium | |
| CN119537652A (en) | Device execution method, apparatus and computer device based on directed graph | |
| CN119090143A (en) | A method, device, equipment and medium for assessing vulnerability of urban transportation system | |
| CN112785044B (en) | Real-time full-load rate prediction method, device, equipment and medium for public transport means | |
| CN111107162B (en) | Indoor positioning data processing method, device and system based on Internet of things | |
| CN114741621A (en) | Heterologous gate address matching method, apparatus, computer equipment and storage medium | |
| CN113804213A (en) | AStar fast path planning improvement algorithm | |
| Isalm et al. | An effective data driven approach to predict bike rental demand | |
| CN111641518A (en) | Heterogeneous network-based community division method and device, computer equipment and medium | |
| CN118052347B (en) | A travel time estimation method and system based on floating vehicle travel trajectory sequence | |
| Chen et al. | Emergence of loops in spatial networks with self-organized growth |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |