<commit_before>import re
import sys
import igraph
from termcolor import colored

from . import tuples, pw, homopolymeric

class OverlapGraph(object):
    """Wraps an :class:`igraph.Graph` object with additional methods to build
    and process an overlap graph.

    Attributes:
        iG (igraph.Graph): The graph object.

    Args:
        G (Optional[igraph.Graph]): The graph object to initialize with; no
            processing is done and if the object is ``None`` a new directed
            graph is instantiated.
    """
    def __init__(self, G=None):
        self.iG = G if G else igraph.Graph(directed=True)
        assert(isinstance(self.iG, igraph.Graph))
        self.v_highlight = '#b5ffb5'
        self.e_highlight = '#00b400'

    def _endpoint_names(self, eid):
        """Internal helper: igraph is not too happy when we munge vertex IDs
        since it keeps renumbering them according to its memory allocation
        scheme. Instead convert everything to "name"s which are the original
        sequence IDs.

        See https://lists.nongnu.org/archive/html/igraph-help/2010-03/msg00078.html
        """
        if isinstance(eid, igraph.Edge):
            eid = eid.index
        uid, vid = self.iG.es[eid].tuple
        return self.iG.vs[uid]['name'], self.iG.vs[vid]['name']

    def _vids_to_names(self, vids):
        return [self.iG.vs[vid]['name'] for vid in vids]

    def _edge_weight(self, u, v):
        """Internal helper; given to vertex names returns the weight of the edge
        connecting them.
        """
        return self.iG.es['weight'][self.iG.get_eid(u, v)]

    def eid_to_str(self, eid, maxlen=20):
        """Prepares an edge for pretty printing. Truncates and paths the end
        point labels (``name`` is used as label) to ensure they both have
        length ``maxlen``.
        """
        u, v = self._endpoint_names(eid)
        u, v = u[:maxlen].ljust(maxlen), v[:maxlen].rjust(maxlen)
        w = self.iG.es[eid]['weight']
        w = ('+--[%.2f]-->' % w).ljust(20)
        return '%s %s %s\n' % (u, w, v)

    def break_cycles(self, method='ip'):
        """Removes a `feedback arc set <https://en.wikipedia.org/wiki/Feedback_arc_set>`__
        from the graph. Depending on the ``method`` the result may not be optimal.

        Keyword Args:
            method (str): The FAS discovery algorithm; passed to
                :func:`igraph.Graph.feedback_arc_set`. Default uses an
                integer programming formulation which is guaranteed to be
                optimal but is slow on large graphs. The alternative is
                ``eades`` which uses a suboptimal `heuristic
                <http://www.sciencedirect.com/science/article/pii/002001909390079O>`__.
        """
        rm = self.iG.feedback_arc_set(weights=self.iG.es['weight'], method=method)
        for e in rm:
            sys.stderr.write('removed edge: %s' % self.eid_to_str(e))
        self.iG.delete_edges(rm)

    def longest_path(self, exclude=[]):
        """Finds the longest path (i.e heaviest path) of the graph, excluding
        vertices with names specified in ``exclude``. This, naturally requires
        that the graph is acyclic. Assuming the graph is a DAG, we can find the
        longest path in two steps:
            - Find a topological ordering of the graph in :math:`O(|V|+|E|)`
              time,
            - Find a heaviest path using the sorting in :math:`O(|V|)` time.

        Keyword Arguments:
            exclude (Optional[List[str]]): A list of vertex names to be excluded
                from the graph when finding the longest path. This is only of
                use to :func:`all_longest_paths`.

        Returns:<commit_msg>don't try to break non-existing cycles<commit_after>import re
import sys
import igraph
from termcolor import colored

from . import tuples, pw, homopolymeric

class OverlapGraph(object):
    """Wraps an :class:`igraph.Graph` object with additional methods to build
    and process an overlap graph.

    Attributes:
        iG (igraph.Graph): The graph object.

    Args:
        G (Optional[igraph.Graph]): The graph object to initialize with; no
            processing is done and if the object is ``None`` a new directed
            graph is instantiated.
    """
    def __init__(self, G=None):
        self.iG = G if G else igraph.Graph(directed=True)
        assert(isinstance(self.iG, igraph.Graph))
        self.v_highlight = '#b5ffb5'
        self.e_highlight = '#00b400'

    def _endpoint_names(self, eid):
        """Internal helper: igraph is not too happy when we munge vertex IDs
        since it keeps renumbering them according to its memory allocation
        scheme. Instead convert everything to "name"s which are the original
        sequence IDs.

        See https://lists.nongnu.org/archive/html/igraph-help/2010-03/msg00078.html
        """
        if isinstance(eid, igraph.Edge):
            eid = eid.index
        uid, vid = self.iG.es[eid].tuple
        return self.iG.vs[uid]['name'], self.iG.vs[vid]['name']

    def _vids_to_names(self, vids):
        return [self.iG.vs[vid]['name'] for vid in vids]

    def _edge_weight(self, u, v):
        """Internal helper; given to vertex names returns the weight of the edge
        connecting them.
        """
        return self.iG.es['weight'][self.iG.get_eid(u, v)]

    def eid_to_str(self, eid, maxlen=20):
        """Prepares an edge for pretty printing. Truncates and paths the end
        point labels (``name`` is used as label) to ensure they both have
        length ``maxlen``.
        """
        u, v = self._endpoint_names(eid)
        u, v = u[:maxlen].ljust(maxlen), v[:maxlen].rjust(maxlen)
        w = self.iG.es[eid]['weight']
        w = ('+--[%.2f]-->' % w).ljust(20)
        return '%s %s %s\n' % (u, w, v)

    def break_cycles(self, method='ip'):
        """Removes a `feedback arc set <https://en.wikipedia.org/wiki/Feedback_arc_set>`__
        from the graph. Depending on the ``method`` the result may not be optimal.

        Keyword Args:
            method (str): The FAS discovery algorithm; passed to
                :func:`igraph.Graph.feedback_arc_set`. Default uses an
                integer programming formulation which is guaranteed to be
                optimal but is slow on large graphs. The alternative is
                ``eades`` which uses a suboptimal `heuristic
                <http://www.sciencedirect.com/science/article/pii/002001909390079O>`__.
        """
        if self.iG.is_dag():
            return
        rm = self.iG.feedback_arc_set(weights=self.iG.es['weight'], method=method)
        for e in rm:
            sys.stderr.write('removed edge: %s' % self.eid_to_str(e))
        self.iG.delete_edges(rm)

    def longest_path(self, exclude=[]):
        """Finds the longest path (i.e heaviest path) of the graph, excluding
        vertices with names specified in ``exclude``. This, naturally requires
        that the graph is acyclic. Assuming the graph is a DAG, we can find the
        longest path in two steps:
            - Find a topological ordering of the graph in :math:`O(|V|+|E|)`
              time,
            - Find a heaviest path using the sorting in :math:`O(|V|)` time.

        Keyword Arguments:
            exclude (Optional[List[str]]): A list of vertex names to be excluded
                from the graph when finding the longest path. This is only of
                use to :func:`all_longest_paths`.

        Returns:
{'fraction_non_alphanumeric': 0.10844337735094038, 'fraction_numerical': 0.010137388288648793, 'mean_word_length': 2.3473214285714286, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 4, 'lorem ipsum': 0, 'www.': 2, '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': '718277', 'n_tokens_mistral': 2327, 'n_tokens_neox': 2193, 'n_words': 745}