Returns the k-core of G. A k-core is a maximal subgraph that contains nodes of degree k or more. Parameters ---------- G : EasyGraph graph A graph or directed graph k : int, optional The order of the core. If not specified return the main core. return_grap
(G: "Graph", k: int = 1, return_graph: bool = False)
| 17 | |
| 18 | @hybrid("cpp_k_core") |
| 19 | def k_core(G: "Graph", k: int = 1, return_graph: bool = False) -> Union["Graph", List]: |
| 20 | """ |
| 21 | Returns the k-core of G. |
| 22 | |
| 23 | A k-core is a maximal subgraph that contains nodes of degree k or more. |
| 24 | |
| 25 | Parameters |
| 26 | ---------- |
| 27 | G : EasyGraph graph |
| 28 | A graph or directed graph |
| 29 | k : int, optional |
| 30 | The order of the core. If not specified return the main core. |
| 31 | return_graph : bool, optional |
| 32 | If True, return the k-core as a graph. If False, return a list of nodes. |
| 33 | |
| 34 | Returns |
| 35 | ------- |
| 36 | G : EasyGraph graph, if return_graph is True, else a list of nodes |
| 37 | The k-core subgraph |
| 38 | """ |
| 39 | # Create a shallow copy of the input graph |
| 40 | H = G.copy() |
| 41 | |
| 42 | # Initialize a dictionary to store the degrees of the nodes |
| 43 | degrees = dict(H.degree()) |
| 44 | |
| 45 | # Repeat until all nodes have degree < k |
| 46 | while True: |
| 47 | # Find the nodes with degree < k |
| 48 | to_remove = [n for n in H.nodes if degrees[n] < k] |
| 49 | |
| 50 | # If there are no such nodes, we're done |
| 51 | if not to_remove: |
| 52 | break |
| 53 | |
| 54 | # Remove the nodes and their incident edges |
| 55 | for n in to_remove: |
| 56 | neighbors = list(H.neighbors(n)) # type: ignore |
| 57 | H.remove_node(n) |
| 58 | |
| 59 | # Update the degrees of the remaining nodes |
| 60 | for neighbor in neighbors: |
| 61 | if neighbor in degrees: |
| 62 | degrees[neighbor] -= 1 |
| 63 | |
| 64 | if return_graph: |
| 65 | return H |
| 66 | else: |
| 67 | return list(H.nodes.keys()) |