Skip to content

components

Algorithms to calculate connected components.

connected_components

Compute the connected components of a graph.

Parameters:

Name Type Description Default
graph pathpyG.core.graph.Graph

The input graph.

 required
connection str

Type of connection to consider. Options are "weak" or "strong". Defaults to "weak".

 'weak'

Returns:

Type Description
typing.Tuple[int, numpy.ndarray]

Tuple[int, np.ndarray]: A tuple containing the number of connected components and an array with component labels for each node.
Source code in src/pathpyG/algorithms/components.py 
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def connected_components(graph: Graph, connection="weak") -> Tuple[int, _np.ndarray]:
    """Compute the connected components of a graph.

    Args:
        graph (Graph): The input graph.
        connection (str, optional): Type of connection to consider. 
            Options are "weak" or "strong". Defaults to "weak".

    Returns:
        Tuple[int, np.ndarray]: A tuple containing the number of connected components and
            an array with component labels for each node.
    """
    m = graph.sparse_adj_matrix()
    n, labels = _cc(m, directed=graph.is_directed(), connection=connection, return_labels=True)
    return n, labels

largest_connected_component

Extract the largest connected component from a graph.

Parameters:

Name Type Description Default
graph pathpyG.core.graph.Graph

The input graph.

 required
connection str

Type of connection to consider. Options are "weak" or "strong". Defaults to "weak".

 'weak'

Returns:

Name Type Description
Graph pathpyG.core.graph.Graph

A new graph instance containing only the largest connected component.
Source code in src/pathpyG/algorithms/components.py 
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def largest_connected_component(graph: Graph, connection="weak") -> Graph:
    """Extract the largest connected component from a graph.

    Args:
        graph (Graph): The input graph.
        connection (str, optional): Type of connection to consider. 
            Options are "weak" or "strong". Defaults to "weak".

    Returns:
        Graph: A new graph instance containing only the largest connected component.
    """
    m = graph.sparse_adj_matrix()
    _, labels = _cc(m, directed=graph.is_directed(), connection=connection, return_labels=True)

    # find largest component C
    ctr = Counter(labels.tolist())
    x, _ = ctr.most_common(1)[0]
    # create graph only consisting of nodes in C
    C = []
    for v, w in graph.edges:
        if labels[graph.mapping.to_idx(v)] == x and labels[graph.mapping.to_idx(w)] == x:
            C.append((v, w))
    return Graph.from_edge_list(C, is_undirected=graph.is_undirected())