<commit_before>"""Bipartite.py

Two-color graphs and find related structures.
<NAME>, May 2004.
"""

from sets import Set

class NonBipartite(Exception):
    pass

def TwoColor(G):
    """
    Find a bipartition of G, if one exists.
    Raises NonBipartite or returns dict mapping vertices
    to two colors (True and False).
    """   
    def traverse(v,parity):
        """Perform depth-first traversal from v and color it."""
        color[v] = parity
        parity = not parity
        for w in G[v]:
            if w in color:
                if color[w] != parity:
                    raise NonBipartite
            else:
                traverse(w,parity)

    color = {}
    for v in G:
        if v not in color:
            traverse(v,True)
    return color

def Bipartition(G):
    """
    Find a bipartition of G, if one exists.
    Raises NonBipartite or returns sequence of vertices
    on one side of the bipartition.
    """
    color = TwoColor(G)
    for v in color:
        if color[v]:
            yield v

def isBipartite(G):
    """
    Return True if G is bipartite, False otherwise.
    """
    try:
        TwoColor(G)
        return True
    except NonBipartite:
        return False

def BipartiteOrientation(G,adjacency_list_type=Set):
    """
    Given an undirected bipartite graph G, return a directed graph in which
    the edges are oriented from one side of the bipartition to the other.
    The second argument has the same meaning as in Graphs.copyGraph.
    """
    B = Bipartition(G)
    return dict([(v,adjacency_list_type(iter(G[v]))) for v in B])
<commit_msg>Odd core of nonbipartite graph.<commit_after>"""Bipartite.py

Two-color graphs and find related structures.
<NAME>, May 2004.
"""

from sets import Set
from Biconnectivity import BiconnectedComponents

class NonBipartite(Exception):
    pass

def TwoColor(G):
    """
    Find a bipartition of G, if one exists.
    Raises NonBipartite or returns dict mapping vertices
    to two colors (True and False).
    """   
    def traverse(v,parity):
        """Perform depth-first traversal from v and color it."""
        color[v] = parity
        parity = not parity
        for w in G[v]:
            if w in color:
                if color[w] != parity:
                    raise NonBipartite
            else:
                traverse(w,parity)

    color = {}
    for v in G:
        if v not in color:
            traverse(v,True)
    return color

def Bipartition(G):
    """
    Find a bipartition of G, if one exists.
    Raises NonBipartite or returns sequence of vertices
    on one side of the bipartition.
    """
    color = TwoColor(G)
    for v in color:
        if color[v]:
            yield v

def isBipartite(G):
    """
    Return True if G is bipartite, False otherwise.
    """
    try:
        TwoColor(G)
        return True
    except NonBipartite:
        return False

def BipartiteOrientation(G,adjacency_list_type=Set):
    """
    Given an undirected bipartite graph G, return a directed graph in which
    the edges are oriented from one side of the bipartition to the other.
    The second argument has the same meaning as in Graphs.copyGraph.
    """
    B = Bipartition(G)
    return dict([(v,adjacency_list_type(iter(G[v]))) for v in B])

def OddCore(G):
    """
    Set of vertices that participate in odd cycles.
    Aka, vertices that are part of a nonbipartite biconnected component.
    """
    core = Set()
    for C in BiconnectedComponents(G):
        if not isBipartite(C):
            core.update(C)
    return core

{'fraction_non_alphanumeric': 0.08288845181230682, 'fraction_numerical': 0.00224782242202866, 'mean_word_length': 2.1985624438454625, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, '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': '4252195', 'n_tokens_mistral': 1103, 'n_tokens_neox': 1051, 'n_words': 398}