Skip to content

ragraph.analysis.heuristics

Heuristics

Heuristics are combinations of algorithms available in the other sub-packages or have an output that does not strictly fit one of the other categories. Not all heuristics have a common argument structure because of their more diverse nature.

Available heuristics

  • johnson circuit finding algorithm.
  • markov_gamma hierarchical clustering with bus detection heuristic.

johnson 

1
2
3
4
5
6
7
johnson(
    graph: Graph,
    nodes: Optional[List[Node]] = None,
    names: bool = False,
    inherit: bool = True,
    **kwargs
) -> Generator[Union[List[str], List[Node]], None, None]

Donald B. Johnson's nested circuit finding algorithm. A circuit is a cycle in a graph, circuits can overlap or contain duplicate parts.

Parameters:

Name Type Description Default
graph Graph

Graph to find circuits in.

 required
nodes Optional[List[Node]]

Nodes to consider during circuit search.

 None
inherit bool

Whether to take into account (inherit) edges between children during SCC calculations.

 True

Yields:

Type Description
Union[List[str], List[Node]]

Node circuit lists.
Note

Cannot cluster a graph directly since circuits may overlap in all sorts of ways. Therefore, it gives you cluster-related information, but no clear hierarchy.

Reference

Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph. In SIAM J. COMPUT (Vol. 4). https://doi.org/10.1137/0204007

Source code in ragraph/analysis/heuristics/_johnson.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def johnson(
    graph: Graph,
    nodes: Optional[List[Node]] = None,
    names: bool = False,
    inherit: bool = True,
    **kwargs,
) -> Generator[Union[List[str], List[Node]], None, None]:
    """Donald B. Johnson's nested circuit finding algorithm. A circuit is a cycle in a
    graph, circuits can overlap or contain duplicate parts.

    Arguments:
        graph: Graph to find circuits in.
        nodes: Nodes to consider during circuit search.
        inherit: Whether to take into account (inherit) edges between children during
            SCC calculations.

    Yields:
        Node circuit lists.

    Note:
        Cannot cluster a graph directly since circuits may overlap in all sorts of ways.
        Therefore, it gives you cluster-related information, but no clear hierarchy.

    Reference:
        Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph.
            In SIAM J. COMPUT (Vol. 4). https://doi.org/10.1137/0204007
    """
    if not nodes:
        nodes = graph.leafs

    # Keep original nodes around for node remapping, get a working copy for the algo.
    translation = {n.name: n for n in nodes}
    graph = graph.get_graph_slice(nodes, inherit=inherit)

    def _unblock(node: Node, blocked: Set[Node], B: Dict[Node, Set[Node]]):
        stack = set([node])
        while stack:
            node = stack.pop()
            if node in blocked:
                blocked.remove(node)
                stack.update(B[node])
                B[node].clear()

    # List of Lists of strongly connected nodes
    sccs = tarjans_scc_algorithm(graph, nodes=graph.roots, inherit=inherit)
    while sccs:
        scc = sccs.pop()
        startnode = scc.pop()
        path = [startnode]
        blocked = set()
        closed = set()
        blocked.add(startnode)
        B: Dict[Node, Set[Node]] = defaultdict(set)
        stack = [(startnode, list(graph.targets_of(startnode)))]
        while stack:
            node, targets = stack[-1]
            if targets:
                target = targets.pop()
                if target == startnode:
                    if names:
                        yield [translation[n.name].name for n in path]  # Original names
                    else:
                        yield [translation[n.name] for n in path]  # Original nodes
                    closed.update(path)
                elif target not in blocked:
                    path.append(target)
                    stack.append((target, list(graph.targets_of(target))))
                    closed.discard(target)
                    blocked.add(target)
                    continue
            else:
                if node in closed:
                    _unblock(node, blocked, B)
                else:
                    for target in graph.targets_of(node):
                        if node not in B[target]:
                            B[target].add(node)
                stack.pop()
                path.pop()
        graph.del_node(node)
        sccs.extend(tarjans_scc_algorithm(graph, scc, inherit))

markov_gamma 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
markov_gamma(
    graph: Graph,
    root: Optional[Union[str, Node]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    alpha: int = markov_gamma_params["alpha"].default,
    beta: float = markov_gamma_params["beta"].default,
    mu: float = markov_gamma_params["mu"].default,
    gamma: float = markov_gamma_params["gamma"].default,
    local_buses: bool = markov_gamma_params[
        "local_buses"
    ].default,
    max_iter: int = markov_gamma_params["max_iter"].default,
    symmetrize: bool = markov_gamma_params[
        "symmetrize"
    ].default,
    inplace: bool = True,
    names: bool = False,
    safe: bool = True,
    **kwargs
) -> Union[List[Node], Tuple[Graph, List[Node]]]

Cluster a given graph hierarchically with buses on a local level or globally.

Source code in ragraph/analysis/heuristics/_markov_gamma.py 
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
@markov_gamma_analysis
def markov_gamma(
    graph: Graph,
    root: Optional[Union[str, Node]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    alpha: int = markov_gamma_params["alpha"].default,  # type: ignore
    beta: float = markov_gamma_params["beta"].default,  # type: ignore
    mu: float = markov_gamma_params["mu"].default,  # type: ignore
    gamma: float = markov_gamma_params["gamma"].default,  # type: ignore
    local_buses: bool = markov_gamma_params["local_buses"].default,  # type: ignore
    max_iter: int = markov_gamma_params["max_iter"].default,  # type: ignore
    symmetrize: bool = markov_gamma_params["symmetrize"].default,  # type: ignore
    inplace: bool = True,
    names: bool = False,
    safe: bool = True,
    **kwargs,
) -> Union[List[Node], Tuple[Graph, List[Node]]]:
    """Cluster a given graph hierarchically with buses on a local level or globally."""
    assert leafs is not None
    graph, roots = hierarchical_markov(
        graph,
        root=root,
        leafs=leafs,
        inherit=inherit,
        loops=loops,
        alpha=alpha,
        beta=beta,
        mu=mu,
        edge_weights=edge_weights,
        inplace=True,
        max_iter=max_iter,
        symmetrize=symmetrize,
        names=False,
        safe=False,
    )
    check_roots = roots[:]
    checked_roots = []
    while check_roots:
        local_root = check_roots.pop()
        local_leafs = [leaf for leaf in leafs if leaf in local_root.descendants]

        # Detect bus in current root.
        bus_leafs, nonbus_leafs = gamma_bus_detection(
            graph,
            local_root,
            leafs=local_leafs,
            inherit=inherit,
            loops=loops,
            gamma=gamma,
            edge_weights=edge_weights,
            names=False,
            safe=False,
        )

        # Bus detected!
        if bus_leafs:
            # Unset local hierarchy.
            _utils.clear_local_hierarchy(graph, local_leafs, [local_root])
            local_root.children = None

            # Recalculate the nonbus hierarchy.
            graph, nonbus_roots = hierarchical_markov(
                graph,
                alpha=alpha,
                beta=beta,
                mu=mu,
                root=None,
                leafs=nonbus_leafs,
                inherit=inherit,
                loops=loops,
                edge_weights=edge_weights,
                inplace=True,
                max_iter=max_iter,
                symmetrize=symmetrize,
                names=False,
                safe=False,
            )
            _utils.set_children(graph, local_root, nonbus_roots)

            # Recalculate the bus hierarchy.
            graph, bus_roots = hierarchical_markov(
                graph,
                alpha=alpha,
                beta=beta,
                mu=mu,
                root=None,
                leafs=bus_leafs,
                inherit=inherit,
                loops=loops,
                edge_weights=edge_weights,
                inplace=True,
                max_iter=max_iter,
                symmetrize=symmetrize,
                names=False,
                safe=False,
            )
            local_root.children = bus_roots + local_root.children
            for bus in bus_roots:
                bus.is_bus = True

        # Finished this root.
        checked_roots.append(local_root)

        # If local: move down a level.
        if not check_roots and local_buses:
            check_roots = [child for local_root in checked_roots for child in local_root.children]
            checked_roots = []

    return graph, roots

_johnson

Donald B. Johnson's nested circuit finding algorithm

johnson 

1
2
3
4
5
6
7
johnson(
    graph: Graph,
    nodes: Optional[List[Node]] = None,
    names: bool = False,
    inherit: bool = True,
    **kwargs
) -> Generator[Union[List[str], List[Node]], None, None]

Donald B. Johnson's nested circuit finding algorithm. A circuit is a cycle in a graph, circuits can overlap or contain duplicate parts.

Parameters:

Name Type Description Default
graph Graph

Graph to find circuits in.

 required
nodes Optional[List[Node]]

Nodes to consider during circuit search.

 None
inherit bool

Whether to take into account (inherit) edges between children during SCC calculations.

 True

Yields:

Type Description
Union[List[str], List[Node]]

Node circuit lists.
Note

Cannot cluster a graph directly since circuits may overlap in all sorts of ways. Therefore, it gives you cluster-related information, but no clear hierarchy.

Reference

Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph. In SIAM J. COMPUT (Vol. 4). https://doi.org/10.1137/0204007

Source code in ragraph/analysis/heuristics/_johnson.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def johnson(
    graph: Graph,
    nodes: Optional[List[Node]] = None,
    names: bool = False,
    inherit: bool = True,
    **kwargs,
) -> Generator[Union[List[str], List[Node]], None, None]:
    """Donald B. Johnson's nested circuit finding algorithm. A circuit is a cycle in a
    graph, circuits can overlap or contain duplicate parts.

    Arguments:
        graph: Graph to find circuits in.
        nodes: Nodes to consider during circuit search.
        inherit: Whether to take into account (inherit) edges between children during
            SCC calculations.

    Yields:
        Node circuit lists.

    Note:
        Cannot cluster a graph directly since circuits may overlap in all sorts of ways.
        Therefore, it gives you cluster-related information, but no clear hierarchy.

    Reference:
        Johnson, D. B. (1975). Finding all the elementary circuits of a directed graph.
            In SIAM J. COMPUT (Vol. 4). https://doi.org/10.1137/0204007
    """
    if not nodes:
        nodes = graph.leafs

    # Keep original nodes around for node remapping, get a working copy for the algo.
    translation = {n.name: n for n in nodes}
    graph = graph.get_graph_slice(nodes, inherit=inherit)

    def _unblock(node: Node, blocked: Set[Node], B: Dict[Node, Set[Node]]):
        stack = set([node])
        while stack:
            node = stack.pop()
            if node in blocked:
                blocked.remove(node)
                stack.update(B[node])
                B[node].clear()

    # List of Lists of strongly connected nodes
    sccs = tarjans_scc_algorithm(graph, nodes=graph.roots, inherit=inherit)
    while sccs:
        scc = sccs.pop()
        startnode = scc.pop()
        path = [startnode]
        blocked = set()
        closed = set()
        blocked.add(startnode)
        B: Dict[Node, Set[Node]] = defaultdict(set)
        stack = [(startnode, list(graph.targets_of(startnode)))]
        while stack:
            node, targets = stack[-1]
            if targets:
                target = targets.pop()
                if target == startnode:
                    if names:
                        yield [translation[n.name].name for n in path]  # Original names
                    else:
                        yield [translation[n.name] for n in path]  # Original nodes
                    closed.update(path)
                elif target not in blocked:
                    path.append(target)
                    stack.append((target, list(graph.targets_of(target))))
                    closed.discard(target)
                    blocked.add(target)
                    continue
            else:
                if node in closed:
                    _unblock(node, blocked, B)
                else:
                    for target in graph.targets_of(node):
                        if node not in B[target]:
                            B[target].add(node)
                stack.pop()
                path.pop()
        graph.del_node(node)
        sccs.extend(tarjans_scc_algorithm(graph, scc, inherit))

_markov_gamma

Hierarchical Markov Clustering (HMC) with Gamma bus detection.

markov_gamma 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
markov_gamma(
    graph: Graph,
    root: Optional[Union[str, Node]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    alpha: int = markov_gamma_params["alpha"].default,
    beta: float = markov_gamma_params["beta"].default,
    mu: float = markov_gamma_params["mu"].default,
    gamma: float = markov_gamma_params["gamma"].default,
    local_buses: bool = markov_gamma_params[
        "local_buses"
    ].default,
    max_iter: int = markov_gamma_params["max_iter"].default,
    symmetrize: bool = markov_gamma_params[
        "symmetrize"
    ].default,
    inplace: bool = True,
    names: bool = False,
    safe: bool = True,
    **kwargs
) -> Union[List[Node], Tuple[Graph, List[Node]]]

Cluster a given graph hierarchically with buses on a local level or globally.

Source code in ragraph/analysis/heuristics/_markov_gamma.py 
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
@markov_gamma_analysis
def markov_gamma(
    graph: Graph,
    root: Optional[Union[str, Node]] = None,
    leafs: Optional[Union[List[Node], List[str]]] = None,
    inherit: bool = True,
    loops: bool = False,
    edge_weights: Optional[List[str]] = None,
    alpha: int = markov_gamma_params["alpha"].default,  # type: ignore
    beta: float = markov_gamma_params["beta"].default,  # type: ignore
    mu: float = markov_gamma_params["mu"].default,  # type: ignore
    gamma: float = markov_gamma_params["gamma"].default,  # type: ignore
    local_buses: bool = markov_gamma_params["local_buses"].default,  # type: ignore
    max_iter: int = markov_gamma_params["max_iter"].default,  # type: ignore
    symmetrize: bool = markov_gamma_params["symmetrize"].default,  # type: ignore
    inplace: bool = True,
    names: bool = False,
    safe: bool = True,
    **kwargs,
) -> Union[List[Node], Tuple[Graph, List[Node]]]:
    """Cluster a given graph hierarchically with buses on a local level or globally."""
    assert leafs is not None
    graph, roots = hierarchical_markov(
        graph,
        root=root,
        leafs=leafs,
        inherit=inherit,
        loops=loops,
        alpha=alpha,
        beta=beta,
        mu=mu,
        edge_weights=edge_weights,
        inplace=True,
        max_iter=max_iter,
        symmetrize=symmetrize,
        names=False,
        safe=False,
    )
    check_roots = roots[:]
    checked_roots = []
    while check_roots:
        local_root = check_roots.pop()
        local_leafs = [leaf for leaf in leafs if leaf in local_root.descendants]

        # Detect bus in current root.
        bus_leafs, nonbus_leafs = gamma_bus_detection(
            graph,
            local_root,
            leafs=local_leafs,
            inherit=inherit,
            loops=loops,
            gamma=gamma,
            edge_weights=edge_weights,
            names=False,
            safe=False,
        )

        # Bus detected!
        if bus_leafs:
            # Unset local hierarchy.
            _utils.clear_local_hierarchy(graph, local_leafs, [local_root])
            local_root.children = None

            # Recalculate the nonbus hierarchy.
            graph, nonbus_roots = hierarchical_markov(
                graph,
                alpha=alpha,
                beta=beta,
                mu=mu,
                root=None,
                leafs=nonbus_leafs,
                inherit=inherit,
                loops=loops,
                edge_weights=edge_weights,
                inplace=True,
                max_iter=max_iter,
                symmetrize=symmetrize,
                names=False,
                safe=False,
            )
            _utils.set_children(graph, local_root, nonbus_roots)

            # Recalculate the bus hierarchy.
            graph, bus_roots = hierarchical_markov(
                graph,
                alpha=alpha,
                beta=beta,
                mu=mu,
                root=None,
                leafs=bus_leafs,
                inherit=inherit,
                loops=loops,
                edge_weights=edge_weights,
                inplace=True,
                max_iter=max_iter,
                symmetrize=symmetrize,
                names=False,
                safe=False,
            )
            local_root.children = bus_roots + local_root.children
            for bus in bus_roots:
                bus.is_bus = True

        # Finished this root.
        checked_roots.append(local_root)

        # If local: move down a level.
        if not check_roots and local_buses:
            check_roots = [child for local_root in checked_roots for child in local_root.children]
            checked_roots = []

    return graph, roots