<commit_before># -*- coding: utf-8 -*-
"""
Edmonds-Karp algorithm for maximum flow problems.
"""

__author__ = """ysitu <<EMAIL>>"""
# Copyright (C) 2014 ysitu <<EMAIL>>
# All rights reserved.
# BSD license.

import networkx as nx
from networkx.algorithms.flow.utils import *

__all__ = ['edmonds_karp', 'edmonds_karp_value', 'edmonds_karp_flow']


def edmonds_karp_core(R, s, t):
    """Implementation of the Edmonds-Karp algorithm.
    """
    inf = float('inf')
    def augment(path):
        """Augment flow along a path from s to t.
        """
        # Determine the path residual capacity.
        flow = inf
        it = iter(path)
        u = next(it)
        for v in it:
            attr = R[u][v]
            flow = min(flow, attr['capacity'] - attr['flow'])
            u = v
        # Augment flow along the path.
        it = iter(path)
        u = next(it)
        for v in it:
            R[u][v]['flow'] += flow
            R[v][u]['flow'] -= flow
            u = v
        # Accumulate the flow values.
        R.node[s]['excess'] -= flow
        R.node[t]['excess'] += flow

    R_pred = R.pred
    R_succ = R.succ
    def bidirectional_bfs():
        """Bidirectional breadth-first search for an augmenting path.
        """
        pred = {s: None}
        q_s = [s]
        succ = {t: None}
        q_t = [t]
        while True:
            q = []
            if len(q_s) <= len(q_t):
                for u in q_s:
                    for v, attr in R_succ[u].items():
                        if v not in pred and attr['flow'] < attr['capacity']:
                            pred[v] = u
                            if v in succ:
                                return v, pred, succ
                            q.append(v)
                if not q:
                    return None, None, None
                q_s = q<commit_msg>Reduce constant factor of maxflow algorithms (cont'd)<commit_after># -*- coding: utf-8 -*-
"""
Edmonds-Karp algorithm for maximum flow problems.
"""

__author__ = """ysitu <<EMAIL>>"""
# Copyright (C) 2014 ysitu <<EMAIL>>
# All rights reserved.
# BSD license.

import networkx as nx
from networkx.algorithms.flow.utils import *

__all__ = ['edmonds_karp', 'edmonds_karp_value', 'edmonds_karp_flow']


def edmonds_karp_core(R, s, t):
    """Implementation of the Edmonds-Karp algorithm.
    """
    R_node = R.node
    R_pred = R.pred
    R_succ = R.succ

    inf = float('inf')
    def augment(path):
        """Augment flow along a path from s to t.
        """
        # Determine the path residual capacity.
        flow = inf
        it = iter(path)
        u = next(it)
        for v in it:
            attr = R_succ[u][v]
            flow = min(flow, attr['capacity'] - attr['flow'])
            u = v
        # Augment flow along the path.
        it = iter(path)
        u = next(it)
        for v in it:
            R_succ[u][v]['flow'] += flow
            R_succ[v][u]['flow'] -= flow
            u = v
        # Accumulate the flow values.
        R_node[s]['excess'] -= flow
        R_node[t]['excess'] += flow

    def bidirectional_bfs():
        """Bidirectional breadth-first search for an augmenting path.
        """
        pred = {s: None}
        q_s = [s]
        succ = {t: None}
        q_t = [t]
        while True:
            q = []
            if len(q_s) <= len(q_t):
                for u in q_s:
                    for v, attr in R_succ[u].items():
                        if v not in pred and attr['flow'] < attr['capacity']:
                            pred[v] = u
                            if v in succ:
                                return v, pred, succ
                            q.append(v)
                if not q:
                    return None, None, None
                q_s = q
{'fraction_non_alphanumeric': 0.12519851773425092, 'fraction_numerical': 0.0026469031233456856, 'mean_word_length': 1.4380645161290322, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6426042', 'n_tokens_mistral': 1210, 'n_tokens_neox': 1163, 'n_words': 349}