<commit_before># -*- coding: utf-8 -*-
"""
    pathpy is an OpenSource python package for the analysis of sequential data on pathways and temporal networks using higher- and multi order graphical models

    Copyright (C) 2016-2017 <NAME>, ETH Zürich

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as published
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

    Contact the developer:
    
    E-mail: <EMAIL>
    Web:    http://www.ingoscholtes.net
"""

import collections as _co
import bisect as _bs
import itertools as _iter

import numpy as _np 

import scipy.sparse as _sparse
import scipy.sparse.linalg as _sla
import scipy.linalg as _la
import scipy as _sp

from pathpy.Log import Log
from pathpy.Log import Severity


class EmptySCCError(Exception):
    """
    This exception is thrown whenever a non-empty strongly 
    connected component is needed, but we encounter an empty one
    """
    pass


class HigherOrderNetwork:
    """
    Instances of this class capture a k-th-order representation of path statistics. Path statistics 
    can originate from pathway data, temporal networks, or from processes observed on top of a network topology.
    """


    def __init__(self, paths, k=1, separator='-', nullModel=False, method='FirstOrderTransitions', lanczosVecs=15, maxiter=1000):
        """
        Generates a k-th-order representation based on the given path statistics.

        @param paths: An instance of class Paths, which contains the path statistics to be 
            used in the generation of the k-th order representation 

        @param k: The order of the network representation to generate. For the default case of 
            k=1, the resulting representation corresponds to the usual (first-order) aggregate network, 
            i.e. links connect nodes and link weights are given by the frequency of each interaction. For 
            k>1, a k-th order node corresponds to a sequence of k nodes. The weight of a k-th order link 
            captures the frequency of a path of length k.

        @param separator: The separator character to be used in higher-order node names.

        @param nullModel: For the default value False, link weights are generated based on the statistics of 
            paths of length k in the underlying path statistics instance. If True, link weights are generated 
            from the first-order model (k=1) based on the assumption of independent links (i.e. corresponding) 
            to a first-order Markov model.

        @param method: specifies how the null model link weights in the k-th order model are calculated. 
            For the default method='FirstOrderTransitions', the weight w('v_1-v_2-...v_k', 'v_2-...-v_k-v_k+1') of 
            a k-order edge is set to the transition probability T['v_k', 'v_k+1'] in the first order network.
            For method='KOrderPi' the entry pi['v1-...-v_k'] in the stationary distribution of the 
            k-order network is used instead.
        """

        assert nullModel == False or (nullModel and k>1)

        assert method == 'FirstOrderTransitions' or method == 'KOrderPi', 'Error: unknown method to build null model'

        assert len(paths.paths.keys())>0 and max(paths.paths.keys())>=k, 'Error: constructing a model of order k requires paths of at least length k'
        
        ## The order of this HigherOrderNetwork
        self.order = k

        ## The paths object used to generate this instance
        self.paths = paths

        ## The nodes in this HigherOrderNetwork 
        self.nodes = []

        ## The separator character used to label higher-order nodes. 
        ## For separator '-', a second-order node will be 'a-b'.
        self.separator = separator

        ## A dictionary containing edges as well as edge weights
        self.edges = _co.defaultdict( lambda: _np.array([0,0]) )

        ## A dictionary containing the sets of successors of all nodes
        self.successors = _co.defaultdict( lambda: set() )

        ## A dictionary containing the sets of predecessors of all nodes
        self.predecessors = _co.defaultdict( lambda: set() )

        if k>1: 
            # For k>1 we need the first-order network to generate the null model
            # and calculate the degrees of freedom

            # For a multi-order model, the first-order network is generated multiple times!
            # TODO: Make this more efficient
            g1 = HigherOrderNetwork(paths, k=1)
            A = g1.getAdjacencyMatrix(includeSubPaths = True, weighted=False, transposed=True)

        if not nullModel:
            # Calculate the frequency of all paths of
            # length k, generate k-order nodes and set
            # edge weights accordingly
            for p in paths.paths[k]:
                # For a 0-order model, we generate a dummy start node
                if k==0: 
                    v = 'start'
                    w = p[0]
                else:
                    # Generate names of k-order nodes v and w
                    v = p[0]
                    w = p[1]
                    for l in range(1, k):
                        v = v + separator + p[l]
                        w = w + separator + p[l+1]
                    self.nodes.append(v)
                    self.nodes.append(w)
                """
                if v not in self.nodes:
                    self.nodes.append(v)
                if w not in self.nodes:
                    self.nodes.append(w)
                """
                # as edge weights of the k-th order model, we sum the
                # occurrence of paths of length k as subpath and longest path
                self.edges[(v,w)] += paths.paths[k][p]<commit_msg>corrected the mistakes due to bad commenting<commit_after># -*- coding: utf-8 -*-
"""
    pathpy is an OpenSource python package for the analysis of sequential data on pathways and temporal networks using higher- and multi order graphical models

    Copyright (C) 2016-2017 <NAME>, ETH Zürich

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as published
    by the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

    Contact the developer:
    
    E-mail: <EMAIL>
    Web:    http://www.ingoscholtes.net
"""

import collections as _co
import bisect as _bs
import itertools as _iter

import numpy as _np 

import scipy.sparse as _sparse
import scipy.sparse.linalg as _sla
import scipy.linalg as _la
import scipy as _sp

from pathpy.Log import Log
from pathpy.Log import Severity


class EmptySCCError(Exception):
    """
    This exception is thrown whenever a non-empty strongly 
    connected component is needed, but we encounter an empty one
    """
    pass


class HigherOrderNetwork:
    """
    Instances of this class capture a k-th-order representation of path statistics. Path statistics 
    can originate from pathway data, temporal networks, or from processes observed on top of a network topology.
    """


    def __init__(self, paths, k=1, separator='-', nullModel=False, method='FirstOrderTransitions', lanczosVecs=15, maxiter=1000):
        """
        Generates a k-th-order representation based on the given path statistics.

        @param paths: An instance of class Paths, which contains the path statistics to be 
            used in the generation of the k-th order representation 

        @param k: The order of the network representation to generate. For the default case of 
            k=1, the resulting representation corresponds to the usual (first-order) aggregate network, 
            i.e. links connect nodes and link weights are given by the frequency of each interaction. For 
            k>1, a k-th order node corresponds to a sequence of k nodes. The weight of a k-th order link 
            captures the frequency of a path of length k.

        @param separator: The separator character to be used in higher-order node names.

        @param nullModel: For the default value False, link weights are generated based on the statistics of 
            paths of length k in the underlying path statistics instance. If True, link weights are generated 
            from the first-order model (k=1) based on the assumption of independent links (i.e. corresponding) 
            to a first-order Markov model.

        @param method: specifies how the null model link weights in the k-th order model are calculated. 
            For the default method='FirstOrderTransitions', the weight w('v_1-v_2-...v_k', 'v_2-...-v_k-v_k+1') of 
            a k-order edge is set to the transition probability T['v_k', 'v_k+1'] in the first order network.
            For method='KOrderPi' the entry pi['v1-...-v_k'] in the stationary distribution of the 
            k-order network is used instead.
        """

        assert nullModel == False or (nullModel and k>1)

        assert method == 'FirstOrderTransitions' or method == 'KOrderPi', 'Error: unknown method to build null model'

        assert len(paths.paths.keys())>0 and max(paths.paths.keys())>=k, 'Error: constructing a model of order k requires paths of at least length k'
        
        ## The order of this HigherOrderNetwork
        self.order = k

        ## The paths object used to generate this instance
        self.paths = paths

        ## The nodes in this HigherOrderNetwork 
        self.nodes = []

        ## The separator character used to label higher-order nodes. 
        ## For separator '-', a second-order node will be 'a-b'.
        self.separator = separator

        ## A dictionary containing edges as well as edge weights
        self.edges = _co.defaultdict( lambda: _np.array([0,0]) )

        ## A dictionary containing the sets of successors of all nodes
        self.successors = _co.defaultdict( lambda: set() )

        ## A dictionary containing the sets of predecessors of all nodes
        self.predecessors = _co.defaultdict( lambda: set() )

        if k>1: 
            # For k>1 we need the first-order network to generate the null model
            # and calculate the degrees of freedom

            # For a multi-order model, the first-order network is generated multiple times!
            # TODO: Make this more efficient
            g1 = HigherOrderNetwork(paths, k=1)
            A = g1.getAdjacencyMatrix(includeSubPaths = True, weighted=False, transposed=True)

        if not nullModel:
            # Calculate the frequency of all paths of
            # length k, generate k-order nodes and set
            # edge weights accordingly
            for p in paths.paths[k]:
                # For a 0-order model, we generate a dummy start node
                if k==0: 
                    v = 'start'
                    w = p[0]
                else:
                    # Generate names of k-order nodes v and w
                    v = p[0]
                    w = p[1]
                    for l in range(1, k):
                        v = v + separator + p[l]
                        w = w + separator + p[l+1]
                self.nodes.append(v)
                self.nodes.append(w)
                """
                if v not in self.nodes:
                    self.nodes.append(v)
                if w not in self.nodes:
                    self.nodes.append(w)
                """
                # as edge weights of the k-th order model, we sum the
                # occurrence of paths of length k as subpath and longest path
                self.edges[(v,w)] += paths.paths[k][p]
{'fraction_non_alphanumeric': 0.06812574612017509, 'fraction_numerical': 0.006685236768802228, 'mean_word_length': 2.172431204241353, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 21, 'https://': 0, 'lorem ipsum': 0, 'www.': 4, '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': '5872934', 'n_tokens_mistral': 3329, 'n_tokens_neox': 3103, 'n_words': 1475}