<commit_before>"""
Topological Anomaly Detection per Gartley and Basener (2009):

    http://www.cis.rit.edu/~mxgpci/pubs/gartley-7334-1.pdf
    
Author: <NAME>
Date: 8/3/2014
Version: 0.1
License: BSD-3
"""

from __future__ import division
import numpy as np
from scipy.spatial.distance import pdist
from itertools import combinations
import networkx as nx
import pandas as pd

def trim_adjacency_matrix(adj, r=None, rq=.1):
    """
    Given a condensed distance matrix (i.e. of the kind outputted by pdist), 
    returns a copy of the distance matrix where all entries greater than 'r'
    are set to zero. If 'r' is not provided, evaluates the 'rq' quantile of the
    input distances and uses that as a heuristic for 'r'. Default behavior is
    to use the 10th percentile of distances as 'r'.
    """
    if r is None:
        # This is really just a lazy quantile function.
        q = int(np.floor(len(adj)*rq))
        print "q:", q
        r = np.sort(adj)[q]
    print "r:", r
    adj2 = adj.copy()
    adj2[adj>r] = 0 
    return adj2, r

def construct_graph(edges, n):
    """
    Constructs a networkx.Graph from a condensed distance matrix (as an
    adjacency matrix).
    """
    g = nx.Graph()
    for z, ij in enumerate(combinations(range(n),2)):
        d = edges[z]
        if d:
            i,j = ij
            g.add_edge(i,j, weight=d)
    return g
    
def flag_anomalies(g, min_pts_bgnd, node_colors={'anomalies':'r', 'background':'b'}):
    """
    Given an input graph, extracts the connected components of the graph and 
    flags all observations in components with fewer than a threshold number of 
    nodes (min_pts_bgnd) as anomalies. A "class" attribute is added to the 
    graph to indicate if an observation is background or anomalous, and a dict
    is also returned whose keys are the class labels "anomalies" and 
    "background" and whose values are lists of observation indices. 
    
    Inputs:
        g: a graph
        min_pts_bgnd: min number of points for a component to be considered 
                      background
     
    Returns:
        res: a dict keyed to two lists, one for anomalies and one for 
             background.
        g:   The input graph with a "class" attribute added to nodes to indicate
             whether or not they are anomalous<commit_msg>Fixed bug that was dropping 'island' observations.<commit_after>"""
Topological Anomaly Detection per Gartley and Basener (2009):

    http://www.cis.rit.edu/~mxgpci/pubs/gartley-7334-1.pdf
    
Author: <NAME>
Date: 8/3/2014
Version: 0.1
License: BSD-3
"""

from __future__ import division
import numpy as np
from scipy.spatial.distance import pdist
from itertools import combinations
import networkx as nx
import pandas as pd

def trim_adjacency_matrix(adj, r=None, rq=.1):
    """
    Given a condensed distance matrix (i.e. of the kind outputted by pdist), 
    returns a copy of the distance matrix where all entries greater than 'r'
    are set to zero. If 'r' is not provided, evaluates the 'rq' quantile of the
    input distances and uses that as a heuristic for 'r'. Default behavior is
    to use the 10th percentile of distances as 'r'.
    """
    if r is None:
        # This is really just a lazy quantile function.
        q = int(np.floor(len(adj)*rq))
        print "q:", q
        r = np.sort(adj)[q]
    print "r:", r
    adj2 = adj.copy()
    adj2[adj>r] = 0 
    return adj2, r

def construct_graph(edges, n):
    """
    Constructs a networkx.Graph from a condensed distance matrix (as an
    adjacency matrix).
    """
    g = nx.Graph()
    g.add_nodes_from(range(n))
    for z, ij in enumerate(combinations(range(n),2)):
        d = edges[z]
        if d:
            i,j = ij
            g.add_edge(i,j, weight=d)
    return g
    
def flag_anomalies(g, min_pts_bgnd, node_colors={'anomalies':'r', 'background':'b'}):
    """
    Given an input graph, extracts the connected components of the graph and 
    flags all observations in components with fewer than a threshold number of 
    nodes (min_pts_bgnd) as anomalies. A "class" attribute is added to the 
    graph to indicate if an observation is background or anomalous, and a dict
    is also returned whose keys are the class labels "anomalies" and 
    "background" and whose values are lists of observation indices. 
    
    Inputs:
        g: a graph
        min_pts_bgnd: min number of points for a component to be considered 
                      background
     
    Returns:
        res: a dict keyed to two lists, one for anomalies and one for 
             background.
        g:   The input graph with a "class" attribute added to nodes to indicate
             whether or not they are anomalous
{'fraction_non_alphanumeric': 0.08142493638676845, 'fraction_numerical': 0.01102629346904156, 'mean_word_length': 2.6284615384615386, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, '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': '2099381', 'n_tokens_mistral': 1474, 'n_tokens_neox': 1371, 'n_words': 590}