Source code for digraphs

#!/Usr/bin/env python3
# Python3+ implementation of digraphs
# Based on Python 2 $Revision: 1.697 $
# Copyright (C) 2006-2013  Raymond Bisdorff
#
#    This program is free software; you can redistribute it and/or modify
#    it under the terms of the GNU 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 General Public License for more details.
#
#    You should have received a copy of the GNU General Public License along
#    with this program; if not, write to the Free Software Foundation, Inc.,
#    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
#
#######################

__version__ = "Branch: 3.5 $"
# ..$ svn co http://leopold-loewenheim.uni.lu/svn/repos/Digraph3

from digraphsTools import *
from digraphs import *
from perfTabs import *
from randomPerfTabs import *

################  see digraphsTools.py module ###############
###--------- Decimal precision --------------
##from decimal import Decimal
##
###---------- general methods -----------------
### from High Performance Python M Gorelick & I Ozswald
### O'Reilly 2014 p.27
##from functools import wraps
##from time import time
##def timefn(fn):
##    """
##    A decorator for automate run time measurements
##    from "High Performance Python" by  M Gorelick & I Ozswald
##    O'Reilly 2014 p.27
##    """
##    @wraps(fn)
##    def measure_time(*args,**kwargs):
##        t1 = time()
##        result = fn(*args,**kwargs)
##        t2 = time()
##        print("@timefn:" + fn.__name__ + " took " + str(t2-t1) + " sec.")
##        return result
##    return measure_time
##
### generate all permutations from a string or a list
### From Michael Davies's recipe:
### http://snippets.dzone.com/posts/show/753
##def all_perms(str):
##    if len(str) <=1:
##        yield str
##    else:
##        for perm in all_perms(str[1:]):
##            for i in range(len(perm)+1):
##                yield perm[:i] + str[0:1] + perm[i:]
### epistemic or symmetric disjunction operator
##def omax(Med,L, Debug=False):
##    """
##    epistemic disjunction for bipolar outranking characteristics
##    computation: Med is the valuation domain median and L is a list of
##    r-valued statement characteristics. 
##    """
##    #Med = self.valuationdomain['med']
##    terms = list(L)
##    termsPlus = []
##    termsMinus = []
##    termsNuls = []
##    for i in range(len(terms)):
##        if terms[i] > Med:
##            termsPlus.append(terms[i])
##        elif terms[i] < Med:
##            termsMinus.append(terms[i])
##        else:
##            termsNuls.append(terms[i])
####    if Debug:
####        print('terms', terms)
####        print('termsPlus',termsPlus)
####        print('termsMinus', termsMinus)
####        print('termsNuls', termsNuls)
##    np = len(termsPlus)
##    nm = len(termsMinus)
##    if np > 0 and nm == 0:
##        return max(termsPlus)
##    elif nm > 0 and np == 0:
##        return min(termsMinus)
##    else:
##        return Med
### epistemic or symmetric conjunction operator
##def omin(Med,L, Debug=False):
##    """
##    epistemic conjunction of a list L of bipolar outranking characteristics.
##    Med is the given valuation domain median.
##    """
##    #Med = self.valuationdomain['med']
##    terms = list(L)
##    termsPlus = []
##    termsMinus = []
##    termsNuls = []
##    for i in range(len(terms)):
##        if terms[i] > Med:
##            termsPlus.append(terms[i])
##        elif terms[i] < Med:
##            termsMinus.append(terms[i])
##        else:
##            termsNuls.append(terms[i])
####    if Debug:
####        print('terms', terms)
####        print('termsPlus',termsPlus)
####        print('termsMinus', termsMinus)
####        print('termsNuls', termsNuls)
##    np = len(termsPlus)
##    nm = len(termsMinus)
##    if np > 0:
##        if nm > 0:
##            return Med
##        else:
##            return min(termsPlus)
##    else:
##        if nm > 0:
##            return max(termsMinus)
##        else:
##            return Med
##
### generate all subsets of a given set E
### Discrete Mathematics BINFO 1 course Lesson 2-sets
### RB October 2009 (recursive version)
##def powerset(S):
##    """
##    Power set generator iterator.
##
##    Parameter S may be any object that is accepted as input by the set class constructor.
##
##    """
##    E = set(S)
##    if len(E) == 0:
##        yield set()
##    else:
##        e = E.pop()
##        for X in powerset(E):
##            yield set([e]) | X
##            yield X
##
### transforms a ranking (list from best to worst) into
### a preorder ( a list of list from worst to best)
##def ranking2preorder(R):
##    preorder = [[x] for x in reversed(R)]
###    for x in R:
###        preorder.append([x])
###    preorder.reverse()
##    return preorder
##
### flattens a list of lists into a flat list
##import itertools as IT
##import collections
##
##def flatten(iterable, ltypes=collections.Iterable):
##    """
##    Flattens a list of lists into a flat list.
##
##    Main usage:
##    
##    >>> listOfLists = [[1,2],[3],[4]]
##    >>> [x for x in flatten(listOfLists)]
##    [1,2,3,4]
##    
##    """
##    
##    remainder = iter(iterable)
##    while True:
##        first = next(remainder)
##        if isinstance(first, ltypes) and not isinstance(first, str):
##            remainder = IT.chain(first, remainder)
##        else:
##            yield first
##
##def total_size(o, handlers={}, verbose=False):
##    """ Returns the approximate memory footprint of an object and all of its contents.
##
##    Automatically finds the contents of the following containers and
##    their subclasses:  tuple, list, deque, dict, set, frozenset, Digraph and BigDigraph.
##    To search other containers, add handlers to iterate over their contents:
##
##        handlers = {SomeContainerClass: iter,
##                    OtherContainerClass: OtherContainerClass.get_elements}
##
##    See http://code.activestate.com/recipes/577504/  
##
##    """
##    from sys import getsizeof, stderr
##    from itertools import chain
##    from collections import deque
##    from bigOutrankingDigraphs import BigDigraph
##    
##    try:
##        from reprlib import repr
##    except ImportError:
##        pass
##
##    # built-in containers and their subclasses
##    dict_handler = lambda d: chain.from_iterable(d.items())
##    all_handlers = {tuple: iter,
##                    list: iter,
##                    deque: iter,
##                    dict: dict_handler,
##                    set: iter,
##                    frozenset: iter,
##                    }
##
##    # Digraph3 objects 
##    object_handler = lambda d: chain.from_iterable(d.__dict__.items())    
##    handlers = {BigDigraph: object_handler,
##                Digraph: object_handler,
##                PerformanceTableau : object_handler,
##                }
##    
##    all_handlers.update(handlers)     # user handlers take precedence
##    seen = set()                      # track which object id's have already been seen
##    default_size = getsizeof(0)       # estimate sizeof object without __sizeof__
##
##    def sizeof(o):
##        if id(o) in seen:       # do not double count the same object
##            return 0
##        seen.add(id(o))
##        s = getsizeof(o, default_size)
##
##        if verbose:
##            print(s, type(o), repr(o), file=stderr)
##
##        for typ, handler in all_handlers.items():
##            if isinstance(o, typ):
##                s += sum(map(sizeof, handler(o)))
##                break
##        return s
##
##    return sizeof(o)
##
##### arithmetics
##def primesbelow(N):
##    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
##    #""" Input N>=6, Returns a list of primes, 2 <= p < N """
##    correction = N % 6 > 1
##    N = {0:N, 1:N-1, 2:N+4, 3:N+3, 4:N+2, 5:N+1}[N%6]
##    sieve = [True] * (N // 3)
##    sieve[0] = False
##    for i in range(int(N ** .5) // 3 + 1):
##        if sieve[i]:
##            k = (3 * i + 1) | 1
##            sieve[k*k // 3::2*k] = [False] * ((N//6 - (k*k)//6 - 1)//k + 1)
##            sieve[(k*k + 4*k - 2*k*(i%2)) // 3::2*k] = [False] * ((N // 6 - (k*k + 4*k - 2*k*(i%2))//6 - 1) // k + 1)
##    return [2, 3] + [(3 * i + 1) | 1 for i in range(1, N//3 - correction) if sieve[i]]
##
##smallprimeset = set(primesbelow(100000))
##_smallprimeset = 100000
##def isprime(n, precision=7):
##    # http://en.wikipedia.org/wiki/Miller-Rabin_primality_test#Algorithm_and_running_time
##    if n == 1 or n % 2 == 0:
##        return False
##    elif n < 1:
##        raise ValueError("Out of bounds, first argument must be > 0")
##    elif n < _smallprimeset:
##        return n in smallprimeset
##
##
##    d = n - 1
##    s = 0
##    while d % 2 == 0:
##        d //= 2
##        s += 1
##
##    for repeat in range(precision):
##        a = random.randrange(2, n - 2)
##        x = pow(a, d, n)
##
##        if x == 1 or x == n - 1: continue
##
##        for r in range(s - 1):
##            x = pow(x, 2, n)
##            if x == 1: return False
##            if x == n - 1: break
##        else: return False
##
##    return True
##
##def pollard_brent(n):
##    # https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
##    if n % 2 == 0: return 2
##    if n % 3 == 0: return 3
##
##    y, c, m = random.randint(1, n-1), random.randint(1, n-1), random.randint(1, n-1)
##    g, r, q = 1, 1, 1
##    while g == 1:
##        x = y
##        for i in range(r):
##            y = (pow(y, 2, n) + c) % n
##
##        k = 0
##        while k < r and g==1:
##            ys = y
##            for i in range(min(m, r-k)):
##                y = (pow(y, 2, n) + c) % n
##                q = q * abs(x-y) % n
##            g = gcd(q, n)
##            k += m
##        r *= 2
##    if g == n:
##        while True:
##            ys = (pow(ys, 2, n) + c) % n
##            g = gcd(abs(x - ys), n)
##            if g > 1:
##                break
##
##    return g
##
##smallprimes = primesbelow(1000) # might seem low, but 1000*1000 = 1000000, so this will fully factor every composite < 1000000
##def primefactors(n, sort=False):
##    factors = []
##
##    limit = int(n ** .5) + 1
##    for checker in smallprimes:
##        if checker > limit: break
##        while n % checker == 0:
##            factors.append(checker)
##            n //= checker
##            limit = int(n ** .5) + 1
##            if checker > limit: break
##
##    if n < 2: return factors
##
##    while n > 1:
##        if isprime(n):
##            factors.append(n)
##            break
##        factor = pollard_brent(n) # trial division did not fully factor, switch to pollard-brent
##        factors.extend(primefactors(factor)) # recurse to factor the not necessarily prime factor returned by pollard-brent
##        n //= factor
##
##    if sort: factors.sort()
##
##    return factors
##
##def factorization(n):
##    factors = {}
##    for p1 in primefactors(n):
##        try:
##            factors[p1] += 1
##        except KeyError:
##            factors[p1] = 1
##    return factors
##
##totients = {}
##def totient(n):
##    if n == 0: return 1
##
##    try: return totients[n]
##    except KeyError: pass
##
##    tot = 1
##    for p, exp in factorization(n).items():
##        tot *= (p - 1)  *  p ** (exp - 1)
##
##    totients[n] = tot
##    return tot
##
##def gcd(a, b):
##    if a == b: return a
##    while b > 0: a, b = b, a % b
##    return a
##
##def lcm(a, b):
##    return abs(a * b) // gcd(a, b)
##

#----------XML handling class -----------------
try:
    from xml.sax import *
except:
    print('XML extension will not work with this Python version!')

class _XMLDigraphHandler(ContentHandler):
    """
    A private handler to deal with digraphs stored in XML format.
    """

    inName = 0
    digraphName = ''
    inAction = 0
    actionName = ''
    actions = []
    iAction = ''
    tAction = ''
    inMin = 0
    minText = ''
    inMax = 0
    maxText = ''
    inValue = 0
    valueText = ''
    valuationdomain = {}
    relation = {}


    def startElement(self,nodeName,attrs):
        if nodeName == 'digraph':
            self.category = attrs.get("category", "")
            self.subcategory = attrs.get("subcategory", "")

        if nodeName == 'name':
            self.inName = 1

        if nodeName == 'nodes':
            self.actions = []

        if nodeName == 'node':
            self.actionName = ''
            self.inAction = 1

        if nodeName == 'min':
            self.inMin = 1

        if nodeName == 'max':
            self.inMax = 1

        if nodeName == 'relation':
            self.relation = {}
            for x in self.actions:
                self.relation[x] = {}

        if nodeName == 'i':
            self.actionName = ''
            self.inAction = 1

        if nodeName == 't':
            self.actionName = ''
            self.inAction = 1

        if nodeName == 'v':
            self.valueText = ''
            self.inValue = 1


    def endElement(self,nodeName):

        if nodeName == 'name':
            self.inName = 0
            self.name = str(self.digraphName)

        if nodeName == 'node':
            self.actions.append(str(self.actionName))
            self.inAction = 0

        if nodeName == 'min':
            self.inMin = 0
            self.valuationdomain['min'] = eval(self.minText)

        if nodeName == 'max':
            self.inMax = 0
            self.valuationdomain['max'] = eval(self.maxText)

        if nodeName == 'i':
            self.inAction = 0
            self.iAction = str(self.actionName)

        if nodeName == 't':
            self.inAction = 0
            self.tAction = str(self.actionName)

        if nodeName == 'v':
            self.inValue = 0

        if nodeName == 'arc':
            self.relation[self.iAction][self.tAction] = eval(self.valueText)

    def characters(self, ch):
        if self.inName:
            self.digraphName += ch
        if self.inAction:
            self.actionName += ch
        if self.inMin:
            self.minText += ch
        if self.inMax:
            self.maxText += ch
        if self.inValue:
            self.valueText += ch


#----------Digraph classes -----------------

[docs]class Digraph(object): """ Genuine root class of all Digraph3 modules. See `tutorial working with the digraphs module <http://leopold-loewenheim.uni.lu/docDigraph3/tutorial.html#digraph-object-structure>`_ All instances of the :py:class:`digraphs.Digraph` class contain at least the following components: 1. A collection of digraph nodes called **actions** (decision alternatives): a list, set or (ordered) dictionary of nodes with 'name' and 'shortname' attributes, 2. A logical characteristic **valuationdomain**, a dictionary with three decimal entries: the minimum (-1.0, means certainly false), the median (0.0, means missing information) and the maximum characteristic value (+1.0, means certainly true), 3. The digraph **relation** : a double dictionary indexed by an oriented pair of actions (nodes) and carrying a characteristic value in the range of the previous valuation domain, 4. Its associated **gamma function** : a dictionary containing the direct successors, respectively predecessors of each action, automatically added by the object constructor, 5. Its associated **notGamma function** : a dictionary containing the actions that are not direct successors respectively predecessors of each action, automatically added by the object constructor. A previously stored :py:class:`digraphs.Digraph` instance may be reloaded with the *file* argument:: >>> from randomDigraphs import RandomValuationDigraph >>> dg = RandomValuationDigraph(order=3,Normalized=True,seed=1) >>> dg.save('testdigraph') Saving digraph in file: <testdigraph.py> >>> from digraphs import Digraph >>> dg = Digraph(file='testdigraph') # without the .py extenseion >>> dg.__dict__ {'name': 'testdigraph', 'actions': {'a1': {'name': 'random decision action', 'shortName': 'a1'}, 'a2': {'name': 'random decision action', 'shortName': 'a2'}, 'a3': {'name': 'random decision action', 'shortName': 'a3'}}, 'valuationdomain': {'min': Decimal('-1.0'), 'med': Decimal('0.0'), 'max': Decimal('1.0'), 'hasIntegerValuation': False,}, 'relation': {'a1': {'a1': Decimal('0.0'), 'a2': Decimal('-0.66'), 'a3': Decimal('0.44')}, 'a2': {'a1': Decimal('0.94'), 'a2': Decimal('0.0'), 'a3': Decimal('-0.84')}, 'a3': {'a1': Decimal('-0.36'), 'a2': Decimal('-0.70'), 'a3': Decimal('0.0')}}, 'order': 3, 'gamma': {'a1': ({'a3'}, {'a2'}), 'a2': ({'a1'}, set()), 'a3': (set(), {'a1'})}, 'notGamma': {'a1': ({'a2'}, {'a3'}), 'a2': ({'a3'}, {'a1', 'a3'}), 'a3': ({'a1', 'a2'}, {'a2'})}} >>> """ def __init__(self,file=None,order=7): #import digraphs,sys,copy from randomDigraphs import RandomValuationDigraph from decimal import Decimal if file == None: g = RandomValuationDigraph(order=order) self.name = g.name self.actions = g.actions self.order = len(self.actions) self.valuationdomain = g.valuationdomain self.convertValuationToDecimal() self.relation = g.relation self.convertRelationToDecimal() self.gamma = self.gammaSets() self.notGamma = self.notGammaSets() else: fileName = file+'.py' argDict = {} exec(compile(open(fileName).read(), fileName, 'exec'), argDict) self.name = file self.actions = argDict['actionset'] self.order = len(self.actions) self.valuationdomain = argDict['valuationdomain'] self.convertValuationToDecimal() self.relation = argDict['relation'] self.convertRelationToDecimal() self.gamma = self.gammaSets() self.notGamma = self.notGammaSets() try: self.reflections = argDict['reflections'] self.rotations = argDict['rotations'] except: pass def __neg__(self): """ Make the negation operator -self available for Digraph instances. Returns a DualDigraph instance of self. """ new = DualDigraph(self) new.__class__ = self.__class__ return new def __invert__(self): """ Make the inverting operator ~self available for Digraph instances. Returns a ConverseDigraph instance of self. """ new = ConverseDigraph(self) new.__class__ = self.__class__ return new #-----------Dias/Castonguay/Longo/Jradi--------* def _triplets(self,Comments=False,Debug=False): """ p.15 """ Med = self.valuationdomain['med'] tG = [] self.circuitsList = [] for u in self.actions: outAsymGammaU = self.gamma[u][0] - self.gamma[u][1] inAsymGammaU = self.gamma[u][1] - self.gamma[u][0] for x in outAsymGammaU: for y in inAsymGammaU: if x != y: if str(u) < str(x) and str(u) < str(y): ## if Debug: ## print('x,u,y',x,u,y) if self.relation[y][x] <= Med and\ self.relation[x][y] <= Med: if Comments: print('Initial triplet: ',x,u,y) tG.append((x,u,y)) elif self.relation[x][y] > Med and\ self.relation[y][x] <= Med: circ = [y,u,x] if Comments: print('Circuit certificate:', circ) self.circuitsList.append((circ,frozenset(circ))) return tG #@timefn
[docs] def computeChordlessCircuitsMP(self,Odd=False,\ Threading=False,nbrOfCPUs=None,\ Comments=False,Debug=False): """ Multiprocessing version of computeChordlessCircuits(). Renders the set of all chordless odd circuits detected in a digraph. Result (possible empty list) stored in <self.circuitsList> holding a possibly empty list tuples with at position 0 the list of adjacent actions of the circuit and at position 1 the set of actions in the stored circuit. Inspired by Dias, Castonguay, Longo, Jradi, Algorithmica (2015). Returns a possibly empty list of tuples (circuit,frozenset(circuit)). If Odd == True, only circuits of odd length are retained in the result. """ tG = self._triplets(Comments=Comments) if Comments: print('There are %d starting triplets !' % len(tG) ) blocked = {} for x in self.actions: blocked[x] = 0 self.blocked = blocked if Threading: self.Odd = Odd self.Comments = Comments self.Debug = Debug from multiprocessing import Pool from os import cpu_count if nbrOfCPUs == None: nbrOfCPUs= cpu_count() with Pool(nbrOfCPUs) as proc: circuits = proc.map(self._computeChordlessPathsFromInitialTriplet,tG) #print(circuits) for i in range(len(tG)): if Debug: print(i,circuits[i]) if circuits[i] != []: for circ in circuits[i]: #print(circ) self.circuitsList.append(circ) else: for p in tG: u = p[1] ## if Debug: ## print('===>>>',p,u) gammaU = (self.gamma[u][1] | self.gamma[u][0]) for x in gammaU: #print(x) self.blocked[x] += 1 self._ccVisit(p,u,Odd=Odd,Comments=Comments) for x in gammaU: if self.blocked[x] > 0: self.blocked[x] -= 1 if Debug: print(self.circuitsList) return self.circuitsList
def _computeChordlessPathsFromInitialTriplet(self,p): if self.Comments: print('===>> thread : ',p) Debug = self.Debug u = p[1] #blocked = self.blocked blocked = {} for x in self.actions: blocked[x] = 0 circuits = [] gammaU = (self.gamma[u][1] | self.gamma[u][0]) for x in gammaU: blocked[x] += 1 circuits,blocked = self._ccVisitMP(circuits,blocked,p,u,Odd=self.Odd) for x in gammaU: if blocked[x] > 0: blocked[x] -= 1 if self.Comments: print(p,circuits) ## for x in self.actions: ## blocked[x] = 0 if Debug: print(p,'return',circuits) return circuits def _ccVisitMP(self,circuits,blocked,p,u, Odd=False): """ p.15 """ Comments = self.Comments Debug = self.Debug Med = self.valuationdomain['med'] ut = p[-1] u1 = p[0] inAsymGammaUt = self.gamma[ut][1] - self.gamma[ut][0] gammaUt = self.gamma[ut][0] | self.gamma[ut][1] if Debug: print(p,self.gamma[ut][1],ut,self.gamma[ut][0]) for x in gammaUt: blocked[x] += 1 for v in inAsymGammaUt: if str(v) > str(u) and blocked[v] == 1: p1 = p + tuple([v]) if Debug: print(p,p1) if self.relation[u1][v] > Med and\ self.relation[v][u1] <= Med: if Odd: if (len(p1) % 2) != 1: OddFlag=False else: OddFlag = True else: OddFlag = True if OddFlag: circ = list(reversed(p1)) if Comments: print(p,'circuit certificate: ',circ) circuits.append((circ,frozenset(circ))) elif self.relation[u1][v] <= Med and\ self.relation[v][u1] <= Med : if Debug: print(p,'continue with ', p1) circuits,blocked = self._ccVisitMP(circuits,blocked, p1,u,Odd=Odd) ## circuits.append(circuits1) if Debug: print(p,circuits) for x in (gammaUt): if blocked[x] > 0: blocked[x] -= 1 return circuits,blocked ################################### #@timefn def _computeChordlessCircuits(self,Odd=False,Comments=False,Debug=False): """ Renders the set of all chordless odd circuits detected in a digraph. Result (possible empty list) stored in <self.circuitsList> holding a possibly empty list tuples with at position 0 the list of adjacent actions of the circuit and at position 1 the set of actions in the stored circuit. Inspired by Dias, Castonguay, Longo, Jradi, Algorithmica (2015). Returns a possibly empty list of tuples (circuit,frozenset(circuit)). If Odd == True, only circuits of odd length are retained in the result. """ tG = self._triplets(Comments=Comments) if Comments: print('There are %d starting triplets !' % len(tG) ) self.blocked = {} for u in self.actions: self.blocked[u] = 0 for p in tG: u = p[1] ## if Debug: ## print('===>>>',p,u) gammaU = (self.gamma[u][1] | self.gamma[u][0]) for x in gammaU: #print(x) self.blocked[x] += 1 self._ccVisit(p,u,Odd=Odd,Comments=Comments) for x in gammaU: if self.blocked[x] > 0: self.blocked[x] -= 1 return self.circuitsList def _ccVisit(self,p,u,Odd=False,Comments=False,Debug=False): """ p.15 """ Med = self.valuationdomain['med'] ut = p[-1] u1 = p[0] inAsymGammaUt = self.gamma[ut][1] - self.gamma[ut][0] gammaUt = self.gamma[ut][0] | self.gamma[ut][1] ## if Debug: ## print(self.gamma[ut][1],ut,self.gamma[ut][0]) for x in gammaUt: self.blocked[x] += 1 for v in inAsymGammaUt: if str(v) > str(u) and self.blocked[v] == 1: p1 = p + tuple([v]) ## if Debug: ## print(p1) if self.relation[u1][v] > Med and\ self.relation[v][u1] <= Med: if Odd: if (len(p1) % 2) != 1: OddFlag=False else: OddFlag = True else: OddFlag = True if OddFlag: circ = list(reversed(p1)) if Comments: print('circuit certificate: ',circ) self.circuitsList.append((circ,frozenset(circ))) elif self.relation[u1][v] <= Med and\ self.relation[v][u1] <= Med : ## if Debug: ## print('continue with ', p1) self._ccVisit(p1,u,Odd=Odd,Comments=Comments) for x in (gammaUt): if self.blocked[x] > 0: self.blocked[x] -= 1 return #----------------------------------------
[docs] def relationFct(self,x,y): """ wrapper for self.relation dictionary access to ensure interoperability with the sparse and big outranking digraph implementation model. """ return self.relation[x][y]
#------------------------------------
[docs] def topologicalSort(self,Debug=False): """ If self is acyclic, adds topological sort number to each node of self and renders ordered list of nodes. Otherwise renders None. Source: M. Golumbic Algorithmic Graph heory and Perfect Graphs, Annals Of Discrete Mathematics 57 2nd Ed. , Elsevier 2004, Algorithm 2.4 p.44. """ def topSort(v,Debug=False): if Debug: print('in',self.i,v,self.gamma[v],self.dfsNbr[v],self.tsNbr[v]) self.i += 1 self.dfsNbr[v] = self.i for w in self.gamma[v][0]: if Debug: print('successer',w,'of',v) if self.dfsNbr[w] == 0: topSort(w,Debug=Debug) else: if self.tsNbr[w] == 0: self.Acyclic = False self.tsNbr[v]=self.j self.j -= 1 if Debug: print('out',v,self.dfsNbr[v],self.tsNbr[v]) self.Acyclic = True self.dfsNbr = {} self.tsNbr = {} for x in self.actions: self.dfsNbr[x]=0 self.tsNbr[x]=0 self.j = len(self.actions) self.i = 0 for x in self.actions: if Debug: print(x,self.gamma[x]) if self.dfsNbr[x] == 0: topSort(x,Debug=Debug) if self.Acyclic: tsLevels = [(x,self.tsNbr[x]) for x in self.tsNbr] ordering = [x[0] for x in sorted(tsLevels,\ key = lambda tsLevels: tsLevels[1])] if Debug: print(tsLevels,ordering) return ordering else: if Debug: print('Digraph instance %s is not acyclic!' % self.name) print(self.dfsNbr,self.tsNbr) return None
[docs] def digraph2Graph(self,valuationDomain={'min':-1,'med':0,'max':1}, Debug=False,conjunctiveConversion=True): """ Convert a Digraph instance to a Graph instance. """ from graphs import Graph from copy import copy, deepcopy g = Graph() g.name = self.name + '_graph' if type(self.actions) == list: g.vertices = {} for x in self.actions: g.vertices[x] = {'name': x, 'shortName': x} else: g.vertices = deepcopy(self.actions) g.order = len(g.vertices) g.valuationDomain = valuationDomain gMin = valuationDomain['min'] gMed = valuationDomain['med'] gMax = valuationDomain['max'] g.edges = {} verticesKeys = list(g.vertices.keys()) dgMed = self.valuationdomain['med'] for i in range(g.order): for j in range(i+1,g.order): x = verticesKeys[i] y = verticesKeys[j] vertex = frozenset([x,y]) if conjunctiveConversion: edgeValue = min(self.relation[x][y],self.relation[y][x]) else: edgeValue = max(self.relation[x][y],self.relation[y][x]) if edgeValue > dgMed: g.edges[vertex] = gMax elif edgeValue < dgMed: g.edges[vertex] = gMin else: g.edges[vertex] = gMed if Debug: print('x,y,self.relation[x][y],self.relation[y][x],vertex,g.edges[vertex]', x,y,self.relation[x][y],self.relation[y][x],vertex,g.edges[vertex]) g.gamma = g.gammaSets() return g
[docs] def computeRelationalStructure(self,Debug=False): """ Renders the counted decomposition of the valued relations into the following type of links: gt '>', eq '=', lt '<', incomp '<>', leq '<=', geq '>=', indeterm '?' """ counts = {'>':0,'=':0,'<':0,'<>':0,'<=':0,'>=':0,'?':0} actions = [x for x in self.actions] n = len(actions) relation = self.relation for x in actions: for y in actions: if Debug: print(x,y, relation[x][y],relation[y][x], end=' ') if x != y: if relation[x][y] > self.valuationdomain['med']: if relation[y][x] > self.valuationdomain['med']: counts['='] += 1 elif relation[y][x] < self.valuationdomain['med']: counts['>'] += 1 else: counts['>='] += 1 elif relation[x][y] < self.valuationdomain['med']: if relation[y][x] > self.valuationdomain['med']: counts['<'] += 1 elif relation[y][x] < self.valuationdomain['med']: counts['<>'] += 1 else: counts['<='] += 1 else: # relation[y][x] == self.valuationdomain['med'] if relation[y][x] > self.valuationdomain['med']: counts['<='] += 1 elif relation[y][x] < self.valuationdomain['med']: counts['>='] += 1 else: counts['?'] += 1 if Debug: print(counts) nd = Decimal(str(n)) if nd != Decimal('0'): counts['<'] = Decimal(str(counts['<']))/(nd*(nd-1)) counts['<='] = Decimal(str(counts['<=']))/(nd*(nd-1)) counts['>'] = Decimal(str(counts['>']))/(nd*(nd-1)) counts['>='] = Decimal(str(counts['>=']))/(nd*(nd-1)) counts['<>'] = Decimal(str(counts['<>']))/(nd*(nd-1)) counts['='] = Decimal(str(counts['=']))/(nd*(nd-1)) counts['?'] = Decimal(str(counts['?']))/(nd*(nd-1)) return counts
[docs] def computeRankingByLastChoosing(self,CoDual=False,CppAgrum=False,Debug=False): """ Computes a weak preordring of the self.actions by iterating worst choice elagations. Stores in self.rankingByLastChoosing['result'] a list of (P-,worstChoice) pairs where P- gives the worst choice complement outranked average valuation via the computePairwiseClusterComparison method. If self.rankingByChoosing['CoDual'] is True, the ranking-by-last-chossing was computed on the codual of self. """ from copy import copy, deepcopy currG = deepcopy(self) remainingActions = [x for x in self.actions] rankingByLastChoosing = [] worstChoice = (None,None) i = 0 while len(remainingActions) > 1 and worstChoice[1] != []: i += 1 currG.actions = remainingActions if CoDual: currGcd = CoDualDigraph(currG) else: currGcd = deepcopy(currG) currGcd.computeRubisChoice(CppAgrum=CppAgrum,Comments=False) #currGcd.computeGoodChoices(Comments=Debug) #currGcd.computeBadChoices(Comments=Debug) worstChoiceCandidates = [] j = 0 for ch in currGcd.badChoices: k1 = currGcd.flatChoice(ch[5]) if Debug: print(ch[5],k1) ck1 = list(set(currG.actions)-set(k1)) if len(ck1) > 0: j += 1 k1Outranked = currG.computePairwiseClusterComparison(k1,ck1) if Debug: print('worst', j, ch[5], k1, k1Outranked) worstChoiceCandidates.append( ( min(-k1Outranked['P+'],k1Outranked['P-']), k1 ) ) else: worstChoiceCandidates.append((self.valuationdomain['max'],k1)) worstChoiceCandidates.sort(reverse=True) try: worstChoice = worstChoiceCandidates[0] except: #print 'Error: no worst choice in currGcd' #currGcd.save('currGcd_errorWorst') worstChoice=(self.valuationdomain['med'],[]) if Debug: print('worstChoice', i, worstChoice, worstChoiceCandidates) if (worstChoice[1] != []): rankingByLastChoosing.append(worstChoice) if len(worstChoice[1]) > 0: for x in worstChoice[1]: try: remainingActions.remove(x) except: pass if Debug: print( i, worstChoice, remainingActions, rankingByLastChoosing) if (worstChoice[1] == []): #### only a singleton choice or a failure quadruple left to rank if Debug: print(worstChoice) worstChoice = (self.valuationdomain['max'],remainingActions) rankingByLastChoosing.append(worstChoice) if Debug: print(rankingByLastChoosing) elif len(remainingActions) == 1: #### only a singleton choice or a failure quadruple left to rank if Debug: print(worstChoice) worstChoice = (self.valuationdomain['max'],remainingActions) rankingByLastChoosing.append(worstChoice) if Debug: print(rankingByLastChoosing) self.rankingByLastChoosing = {'CoDual': CoDual, 'result': rankingByLastChoosing} return {'CoDual': CoDual, 'result': rankingByLastChoosing}
[docs] def computeRankingByChoosing(self,actionsSubset=None,CppAgrum=False,Debug=False,CoDual=False): """ Computes a weak preordring of the self.actions by iterating jointly best and worst choice elagations. Stores in self.rankingByChoosing['result'] a list of ((P+,bestChoice),(P-,worstChoice)) pairs where P+ (resp. P-) gives the best (resp. worst) choice complement outranking (resp. outranked) average valuation via the computePairwiseClusterComparison method. If self.rankingByChoosing['CoDual'] is True, the ranking-by-choosing was computed on the codual of self. """ from copy import copy, deepcopy currG = deepcopy(self) if actionsSubset == None: remainingActions = [x for x in self.actions] else: remainingActions = actionsSubset rankingByChoosing = [] bestChoice = (None,None) worstChoice = (None,None) i = 0 while len(remainingActions) > 2 and (bestChoice[1] != [] or worstChoice[1] != []): i += 1 currG.actions = remainingActions if CoDual: currGcd = CoDualDigraph(currG) else: currGcd = deepcopy(currG) currGcd.computeRubisChoice(CppAgrum=CppAgrum,Comments=Debug) #currGcd.computeGoodChoices(Comments=Debug) bestChoiceCandidates = [] j = 0 for ch in currGcd.goodChoices: k1 = currGcd.flatChoice(ch[5]) if Debug: print(ch[5],k1) ck1 = list(set(currG.actions)-set(k1)) if len(ck1) > 0: j += 1 k1Outranking = currG.computePairwiseClusterComparison(k1,ck1) if Debug: print('good', j, ch[5], k1, k1Outranking) #bestChoiceCandidates.append((k1Outranking['P+'],k1)) bestChoiceCandidates.append( ( min(k1Outranking['P+'],-k1Outranking['P-']), k1 ) ) else: bestChoiceCandidates.append((self.valuationdomain['max'],k1)) #bestChoiceCandidates.sort(reverse=True) bestChoiceCandidates = sorted(bestChoiceCandidates, key=lambda choice: str(choice[1]) ) # lexigr choices bestChoiceCandidates = sorted(bestChoiceCandidates, key=lambda choice: -choice[0]) # sort by outranking power try: bestChoice = bestChoiceCandidates[0] except: #print 'Error: no best choice in currGcd!' #currGcd.save('currGcd_errorBest') bestChoice = (self.valuationdomain['med'],[]) if Debug: print('bestChoice', i, bestChoice, bestChoiceCandidates) #currGcd.computeBadChoices(Comments=Debug) worstChoiceCandidates = [] j = 0 for ch in currGcd.badChoices: k1 = currGcd.flatChoice(ch[5]) if Debug: print(ch[5],k1) ck1 = list(set(currG.actions)-set(k1)) if len(ck1) > 0: j += 1 k1Outranked = currG.computePairwiseClusterComparison(k1,ck1) if Debug: print('worst', j, ch[5], k1, k1Outranked) worstChoiceCandidates.append( ( min(-k1Outranked['P+'],k1Outranked['P-']), k1 ) ) else: worstChoiceCandidates.append((self.valuationdomain['max'],k1)) worstChoiceCandidates.sort(reverse=True) try: worstChoice = worstChoiceCandidates[0] except: #print 'Error: no worst choice in currGcd' #currGcd.save('currGcd_errorWorst') worstChoice=(self.valuationdomain['med'],[]) if Debug: print('worstChoice', i, worstChoice, worstChoiceCandidates) if (bestChoice[1] != [] or worstChoice[1] != []): rankingByChoosing.append((bestChoice,worstChoice)) if len(bestChoice[1]) > 0: for x in bestChoice[1]: remainingActions.remove(x) if len(worstChoice[1]) > 0: for x in worstChoice[1]: try: remainingActions.remove(x) except: pass #print i, bestChoice, worstChoice, remainingActions, rankingByChoosing if (bestChoice[1] == [] and worstChoice[1] == []): #### only a singleton choice or a failure quadruple left to rank if Debug: print(bestChoice,worstChoice) bestChoice = (self.valuationdomain['max'],remainingActions) worstChoice = (self.valuationdomain['max'],remainingActions) rankingByChoosing.append((bestChoice,worstChoice)) if Debug: print(rankingByChoosing) elif len(remainingActions) == 2: i += 1 currG.actions = remainingActions if CoDual: currGcd = CoDualDigraph(currG) else: currGcd = deepcopy(currG) currGcd.computeRubisChoice(Comments=Debug) #currGcd.computeGoodChoices(Comments=Debug) bestChoiceCandidates = [] j = 0 for ch in currGcd.goodChoices: k1 = currGcd.flatChoice(ch[5]) if Debug: print(ch[5],k1) ck1 = list(set(currG.actions)-set(k1)) if len(ck1) > 0: j += 1 k1Outranking = currG.computePairwiseClusterComparison(k1,ck1) if Debug: print('good', j, ch[5], k1, k1Outranking) #bestChoiceCandidates.append((k1Outranking['P+'],k1)) bestChoiceCandidates.append( ( min(k1Outranking['P+'],-k1Outranking['P-']), k1 ) ) else: bestChoiceCandidates.append((self.valuationdomain['max'],k1)) bestChoiceCandidates.sort(reverse=True) try: bestChoice = bestChoiceCandidates[0] except: #print 'Error: no best choice in currGcd!' #currGcd.save('currGcd_errorBest') bestChoice = (self.valuationdomain['med'],[]) if Debug: print('bestChoice', i, bestChoice, bestChoiceCandidates) ## ### unique worst choice left k1 = list(set(currG.actions)-set(bestChoice[1])) if Debug: print('singleton worst choice left',k1) if len(k1) > 0: ck1 = list(set(currG.actions)-set(k1)) k1Outranked = currG.computePairwiseClusterComparison(k1,ck1) worstChoice = ( min(-k1Outranked['P+'],k1Outranked['P-']), k1 ) else: worstChoice = (self.valuationdomain['max'],bestChoice[1]) if Debug: print('worstChoice', i, worstChoice) rankingByChoosing.append((bestChoice,worstChoice)) elif len(remainingActions) == 1: #### only a singleton choice or a failure quadruple left to rank if Debug: print(bestChoice,worstChoice) bestChoice = (self.valuationdomain['max'],remainingActions) worstChoice = (self.valuationdomain['max'],remainingActions) rankingByChoosing.append((bestChoice,worstChoice)) if Debug: print(rankingByChoosing) self.rankingByChoosing = {'CoDual': CoDual, 'result': rankingByChoosing} return {'CoDual': CoDual, 'result': rankingByChoosing}
[docs] def computeRankingByBestChoosing(self,CoDual=False,CppAgrum=False,Debug=False,): """ Computes a weak preordering of the self.actions by recursive best choice elagations. Stores in self.rankingByBestChoosing['result'] a list of (P+,bestChoice) tuples where P+ gives the best choice complement outranking average valuation via the computePairwiseClusterComparison method. If self.rankingByBestChoosing['CoDual'] is True, the ranking-by-choosing was computed on the codual of self. """ if Debug: print("===>>>> debugging computeByBestChoosing() digraphs methods") from copy import copy, deepcopy currG = copy(self) remainingActions = [x for x in self.actions] rankingByBestChoosing = [] bestChoice = (None,None) i = 0 while len(remainingActions) > 2 and bestChoice[1] != []: i += 1 currG.actions = remainingActions if CoDual: currGcd = CoDualDigraph(currG) else: currGcd = copy(currG) currGcd.computeRubisChoice(CppAgrum=CppAgrum,Comments=Debug) #currGcd.computeGoodChoices(Comments=Debug) bestChoiceCandidates = [] j = 0 for ch in currGcd.goodChoices: k1 = currGcd.flatChoice(ch[5]) if Debug: print('flatening the choice:',ch[5],k1) ck1 = list(set(currG.actions)-set(k1)) if len(ck1) > 0: j += 1 k1Outranking = currG.computePairwiseClusterComparison(k1,ck1) if Debug: print('good', j, ch[5], k1, k1Outranking) #bestChoiceCandidates.append((k1Outranking['P+'],k1)) bestChoiceCandidates.append( ( min(k1Outranking['P+'],-k1Outranking['P-']), k1 ) ) else: bestChoiceCandidates.append((self.valuationdomain['max'],k1)) #bestChoiceCandidates.sort(reverse=True) bestChoiceCandidates = sorted(bestChoiceCandidates, key=lambda choice: str(choice[1]) ) # lexigr choices bestChoiceCandidates = sorted(bestChoiceCandidates, key=lambda choice: -choice[0]) # sort by outranking power try: bestChoice = bestChoiceCandidates[0] except: if Debug: print('Error: no best choice in currGcd!') #currGcd.save('currGcd_errorBest') bestChoice = (self.valuationdomain['med'],[]) if Debug: print('bestChoice', i, bestChoice, bestChoiceCandidates) if bestChoice[1] != []: if Debug: print('bestChoice[1] != []:', bestChoice[1]) rankingByBestChoosing.append(bestChoice) if len(bestChoice[1]) > 0: for x in bestChoice[1]: remainingActions.remove(x) if Debug: print(i, bestChoice, remainingActions, rankingByBestChoosing) if bestChoice[1] == []: #### only a singleton choice or a failure quadruple left to rank if Debug: print('bestChoice[1] == []:', bestChoice) bestChoice = (self.valuationdomain['max'],remainingActions) rankingByBestChoosing.append(bestChoice) if Debug: print(rankingByBestChoosing) elif len(remainingActions) == 2: if Debug: print('len(remainingActions) == 2:',remainingActions) i += 1 currG.actions = remainingActions if CoDual: currGcd = CoDualDigraph(currG) else: currGcd = copy(currG) currGcd.computeRubisChoice(Comments=Debug) #currGcd.computeGoodChoices(Comments=Debug) bestChoiceCandidates = [] j = 0 for ch in currGcd.goodChoices: k1 = currGcd.flatChoice(ch[5]) if Debug: print(ch[5],k1) ck1 = list(set(currG.actions)-set(k1)) if len(ck1) > 0: j += 1 k1Outranking = currG.computePairwiseClusterComparison(k1,ck1) if Debug: print('good', j, ch[5], k1, k1Outranking) #bestChoiceCandidates.append((k1Outranking['P+'],k1)) bestChoiceCandidates.append( ( min(k1Outranking['P+'],-k1Outranking['P-']), k1 ) ) else: bestChoiceCandidates.append((self.valuationdomain['max'],k1)) bestChoiceCandidates.sort(reverse=True) if Debug: print('bestChoice', i, bestChoice, bestChoiceCandidates) try: bestChoice = bestChoiceCandidates[0] except: #print 'Error: no best choice in currGcd!' #currGcd.save('currGcd_errorBest') bestChoice = (self.valuationdomain['med'],[]) rankingByBestChoosing.append(bestChoice) for x in bestChoice[1]: remainingActions.remove(x) if len(remainingActions) > 0: lastBestChoice = (self.valuationdomain['max'],remainingActions) rankingByBestChoosing.append(lastBestChoice) if Debug: print('lastBestChoice', i+1, lastBestChoice) elif len(remainingActions) == 1: #### only a singleton choice or a failure quadruple left to rank if Debug: print('!!! len(remainingActions) == 1: !!!', remainingActions) bestChoice = (self.valuationdomain['max'],remainingActions) rankingByBestChoosing.append(bestChoice) if Debug: print(rankingByBestChoosing) self.rankingByBestChoosing = {'CoDual': CoDual, 'result': rankingByBestChoosing} return {'CoDual': CoDual, 'result': rankingByBestChoosing}
[docs] def iterateRankingByChoosing(self,Odd=False,CoDual=False,Comments=True,Debug=False,Limited=None): """ Renders a ranking by choosing result when progressively eliminating all chordless (odd only) circuits with rising valuation cut levels. Parameters CoDual = False (default)/True Limited = proportion (in [0,1]) * (max - med) valuationdomain """ from copy import copy, deepcopy from time import time if Debug: Comments=True gcd = copy(self) qualmaj0 = gcd.valuationdomain['med'] if Limited != None: maxLevel = gcd.valuationdomain['med'] + (gcd.valuationdomain['max']-gcd.valuationdomain['med'])*Decimal(str(Limited)) else: maxLevel = gcd.valuationdomain['max'] if Comments: print('Ranking by choosing and rejecting after progressive cut elimination of chordless (odd = %s) circuits' % (str(Odd)) ) print('Evaluation domain: [ %.3f ; %.3f ]' % (gcd.valuationdomain['min'],gcd.valuationdomain['max'])) print('Initial determinateness of the outranking relation: %.3f' % self.computeDeterminateness()) print('Maximum level of circuits elimination: %.3f' % (maxLevel)) i = 0 qualmaj = gcd.minimalValuationLevelForCircuitsElimination(Odd=Odd,Debug=Debug,Comments=Comments) self.rankingByChoosing = None while qualmaj > qualmaj0: i += 1 if Comments: print('--> Iteration %d' % (i)) t0 = time() if Limited: if qualmaj <= maxLevel: if qualmaj < gcd.valuationdomain['max']: # strict cut only possible if < max pg = PolarisedDigraph(gcd,qualmaj,StrictCut=True) else: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=False) else: qualmaj = qualmaj0 if qualmaj < gcd.valuationdomain['max']: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=True) else: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=False) else: if qualmaj < gcd.valuationdomain['max']: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=True) else: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=False) if Comments: print('Polarised determinateness = %.3f' % pg.computeDeterminateness()) if qualmaj > gcd.valuationdomain['med']: self.rankingByChoosing = pg.computeRankingByChoosing(CoDual=CoDual,Debug=Debug) self.rankingByChoosing['PolarizationLevel'] = qualmaj elif i==1: self.rankingByChoosing = pg.computeRankingByChoosing(CoDual=CoDual,Debug=Debug) self.rankingByChoosing['PolarizationLevel'] = qualmaj if Comments: self.showRankingByChoosing() print('Execution time:', time()-t0, 'sec.') ## pgRankingByChoosingRelation = self.computeRankingByChoosingRelation() ## corr = self.computeOrdinalCorrelation(pgRankingByChoosingRelation) ## print 'Ordinal (Kendall) correlation with outranking relation: %.3f (%.3f)' % (corr['correlation'],corr['determination']) ## corr = self.computeOrdinalCorrelation(pgRankingByChoosingRelation,MedianCut=True,Debug=Debug) ## print 'Ordinal (Kendall) correlation with median cut outranking relation: %.3f (%.3f)' % (corr['correlation'],corr['determination']) qualmaj0 = qualmaj newLevel = pg.minimalValuationLevelForCircuitsElimination(Debug=Debug,Comments=Comments) if Limited != None: qualmaj = min(maxLevel,newLevel) else: qualmaj = newLevel if Comments: print(i,qualmaj0,newLevel,qualmaj) if i==0: self.rankingByChoosing = gcd.computeRankingByChoosing(CoDual=CoDual,Debug=Debug) self.rankingByChoosing['PolarizationLevel'] = qualmaj return self.rankingByChoosing
def _optimalRankingByChoosing(self,Odd=True,CoDual=False,Comments=False,Debug=False,Limited=None): """ Renders a ranking by choosing result when progressively eliminating all chordless (odd only by default) circuits with rising valuation cut levels. Parameters: * CoDual = False (default)/True * Limited = proportion (in [0,1]) * (max - med) of valuationdomain (default = None) Returns the highest correlated rankingByChoosing with self or codual of self, depending on the CoDual flagg. """ from copy import copy, deepcopy if Debug: Comments=True g = copy(self) if CoDual: gcd = ~(-g) else: gcd = copy(g) gcdcd = ~(-gcd) qualmaj0 = gcd.valuationdomain['min'] if Limited != None: maxLevel = gcd.valuationdomain['med'] + (gcd.valuationdomain['max']-gcd.valuationdomain['med'])*Decimal(str(Limited)) else: maxLevel = gcd.valuationdomain['max'] if Comments: print('Ranking by choosing and rejecting after progressive cut elimination of chordless (odd = %s) circuits' % (str(Odd)) ) print('Evaluation domain: [ %.3f ; %.3f ]' % (gcd.valuationdomain['min'],gcd.valuationdomain['max'])) print('Initial determinateness of the outranking relation: %.3f' % self.computeDeterminateness()) print('Maximum level of circuits elimination: %.3f' % (maxLevel)) i = 0 #qualmaj = gcd.minimalValuationLevelForCircuitsElimination(Odd=Odd,Debug=Debug,Comments=Comments) qualmaj = gcd.valuationdomain['med'] self.rankingByChoosing = None rankings = [] while qualmaj > qualmaj0 and qualmaj <= maxLevel: i += 1 if Comments: print('--> Iteration %d' % (i)) if Limited != None: if qualmaj <= maxLevel: if qualmaj < gcd.valuationdomain['max']: ## strict cut only possible if cut level qualmaj < max pg = PolarisedDigraph(gcd,qualmaj,StrictCut=True) else: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=False) else: qualmaj = qualmaj0 #if qualmaj < gcd.valuationdomain['max']: # pg = PolarisedDigraph(gcd,qualmaj,StrictCut=True) #else: # pg = PolarisedDigraph(gcd,qualmaj,StrictCut=False) else: if qualmaj < gcd.valuationdomain['max']: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=True) else: pg = PolarisedDigraph(gcd,qualmaj,StrictCut=False) if Comments: print('Polarised determinateness = %.3f' % pg.computeDeterminateness()) rkg = pg.computeRankingByChoosing(CoDual=False,Debug=Debug) pgr = pg.computeRankingByChoosingRelation() if CoDual: corr = g.computeOrdinalCorrelation(pgr) else: corr = gcdcd.computeOrdinalCorrelation(pgr) rankings.append((corr['correlation'],qualmaj,rkg)) #rankings.append((corr['correlation']*corr['determination'],qualmaj,rkg)) if Comments: if Debug: print(rankings) if CoDual: g.showRankingByChoosing(rkg) else: gcdcd.showRankingByChoosing(rkg) qualmaj0 = qualmaj newLevel = pg.minimalValuationLevelForCircuitsElimination(Odd=Odd,Debug=Debug,Comments=Comments) if Limited != None: if newLevel <= maxLevel: qualmaj = newLevel else: qualmaj0 = qualmaj else: qualmaj = newLevel if Debug: print('i,qualmaj0,newLevel,maxLevel,qualmaj',i,qualmaj0,newLevel,maxLevel,qualmaj) if i==0: self.rankingByChoosing = gcd.computeRankingByChoosing(CoDual=CoDual,Debug=Debug) self.rankingByChoosing['PolarizationLevel'] = qualmaj else: rankings.sort(reverse=True) self.rankingByChoosing = rankings[0][2] self.rankingByChoosing['PolarizationLevel'] = rankings[0][1] if Comments: if Debug: print(rankings) if CoDual: g.showRankingByChoosing(self.rankingByChoosing) else: gcdcd.showRankingByChoosing(self.rankingByChoosing) return self.rankingByChoosing def _computePrudentBestChoiceRecommendation(self,CoDual=False,Comments=False,Debug=False,Limited=None): """ Renders the best choice recommendation after eliminating all odd chordless circuits with a minimal cut of the valuation. """ from copy import copy as deepcopy self.optimalRankingByChoosing(CoDual=CoDual,Comments=Comments,Debug=Debug,Limited=Limited) #if Comments: # self.showRankingByChoosing() try: self.rankingByChoosing['result'][0][0][1].sort() return self.rankingByChoosing['result'][0][0][1] except: print("Error: no ranking by choosing result !!") return None
[docs] def computePreRankingRelation(self,preRanking,Normalized=True,Debug=False): """ Renders the bipolar-valued relation obtained from a given preRanking in decreasing levels (list of lists) result. """ if Normalized: Max = Decimal('1') Med = Decimal('0') Min = Decimal('-1') else: Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] actions = list(self.actions.keys()) currentActions = set(actions) preRankingRelation = {} for x in actions: preRankingRelation[x] = {} for y in actions: preRankingRelation[x][y] = Med for eqcl in preRanking: currRest = currentActions - set(eqcl) if Debug: print(currentActions, eqcl, currRest) for x in eqcl: for y in eqcl: if x != y: preRankingRelation[x][y] = Max preRankingRelation[y][x] = Max for x in eqcl: for y in currRest: preRankingRelation[x][y] = Max preRankingRelation[y][x] = Min currentActions = currentActions - set(eqcl) return preRankingRelation
[docs] def computePreorderRelation(self,preorder,Normalized=True,Debug=False): """ Renders the bipolar-valued relation obtained from a given preordering in increasing levels (list of lists) result. """ if Normalized: Max = Decimal('1') Med = Decimal('0') Min = Decimal('-1') else: Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] actions = list(self.actions.keys()) currentActions = set(actions) preorderRelation = {} for x in actions: preorderRelation[x] = {} for y in actions: preorderRelation[x][y] = Med for eqcl in preorder: currRest = currentActions - set(eqcl) if Debug: print(currentActions, eqcl, currRest) for x in eqcl: for y in eqcl: if x != y: preorderRelation[x][y] = Max preorderRelation[y][x] = Max for x in eqcl: for y in currRest: preorderRelation[x][y] = Min preorderRelation[y][x] = Max currentActions = currentActions - set(eqcl) return preorderRelation
[docs] def computeRankingByChoosingRelation(self,rankingByChoosing=None,actionsSubset=None,Debug=False): """ Renders the bipolar-valued relation obtained from the self.rankingByChoosing result. """ from copy import copy, deepcopy if rankingByChoosing==None: try: rankingByChoosing = self.rankingByChoosing['result'] except: print('Error: first run computeRankingByChoosing(CoDual=T/F) !') return None if Debug: print('actionsSubset,rankingByChoosing',actionsSubset,rankingByChoosing) Max = Decimal('1') Med = Decimal('0') Min = Decimal('-1') if actionsSubset==None: actions = [x for x in self.actions] else: actions = copy(actionsSubset) if Debug: print(actions) currActions = set(actions) relation = self.relation rankingRelation = {} for x in actions: rankingRelation[x] = {} for y in actions: rankingRelation[x][y] = Med #print(x,y,rankingRelation[x][y]) n = len(rankingByChoosing) for i in range(n): ibch = set(rankingByChoosing[i][0][1]) iwch = set(rankingByChoosing[i][1][1]) ribch = set(currActions) - ibch if Debug: print(ibch,iwch,ribch) for x in ibch: for y in ibch: if x != y: rankingRelation[x][y] = omax(Med,[rankingRelation[x][y],abs(relation[x][y])]) rankingRelation[y][x] = omax(Med,[rankingRelation[x][y],abs(relation[y][x])]) for y in ribch: #print(x,y) #print(rankingRelation[x][y]) #print(relation[x][y]) rankingRelation[x][y] = omax(Med,[rankingRelation[x][y],abs(relation[x][y])]) rankingRelation[y][x] = omax(Med,[rankingRelation[y][x],-abs(relation[y][x])]) riwch = set(currActions) - iwch for y in iwch: for x in iwch: if x != y: rankingRelation[x][y] = omax(Med,[rankingRelation[x][y],abs(relation[x][y])]) rankingRelation[y][x] = omax(Med,[rankingRelation[y][x],abs(relation[y][x])]) for x in riwch: rankingRelation[x][y] = omax(Med,[rankingRelation[x][y],abs(relation[x][y])]) rankingRelation[y][x] = omax(Med,[rankingRelation[y][x],-abs(relation[x][y])]) currActions = currActions - (ibch | iwch) return rankingRelation
[docs] def computeRankingByBestChoosingRelation(self,rankingByBestChoosing=None,Debug=False): """ Renders the bipolar-valued relation obtained from the self.rankingByBestChoosing result. """ if rankingByBestChoosing==None: try: rankingByBestChoosing = self.rankingByBestChoosing['result'] except: print('Error: first run computeRankingByBestChoosing(CoDual=T/F) !') return None Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] actions = [x for x in self.actions] currActions = set(actions) relation = self.relation rankingRelation = {} for x in actions: rankingRelation[x] = {} for y in actions: rankingRelation[x][y] = Med n = len(rankingByBestChoosing) if Debug: print('rankingByBestChoosing',rankingByBestChoosing) for i in range(n): ibch = set(rankingByBestChoosing[i][1]) ribch = set(currActions) - ibch if Debug: print('ibch,ribch',ibch,ribch) for x in ibch: for y in ibch: if x != y: rankingRelation[x][y] = min( [abs(relation[x][y]),abs(relation[y][x])] ) rankingRelation[y][x] = min( [abs(relation[y][x]),abs(relation[x][y])] ) ## rankingRelation[x][y] = self.omin( [rankingRelation[x][y],abs(relation[y][x])] ) ## rankingRelation[y][x] = self.omin( [rankingRelation[y][x],abs(relation[x][y])] ) ## if Debug and (x == 'a10' or y == 'a07') : ## print(x,y,rankingRelation[x][y],relation[x][y]) ## print(y,x,rankingRelation[y][x],relation[y][x]) for y in ribch: ## rankingRelation[x][y] = self.omin( [rankingRelation[x][y],abs(relation[y][x])] ) ## rankingRelation[y][x] = self.omin( [rankingRelation[y][x],-abs(relation[x][y])] ) rankingRelation[x][y] = min( [abs(relation[x][y]),abs(relation[y][x])] ) rankingRelation[y][x] = -min( [abs(relation[y][x]),abs(relation[x][y])] ) ## if Debug and (x == 'a10' or y == 'a07'): ## print('+',x,y,rankingRelation[x][y],relation[x][y]) ## print('-',y,x,rankingRelation[y][x],relation[y][x]) currActions = currActions - ibch return rankingRelation
[docs] def computeRankingByLastChoosingRelation(self,rankingByLastChoosing=None,Debug=False): """ Renders the bipolar-valued relation obtained from the self.rankingByLastChoosing result. """ if rankingByLastChoosing==None: try: rankingByLastChoosing = self.rankingByLastChoosing['result'] except: print('Error: first run computeRankingByLastChoosing(CoDual=T/F) !') return None Max = Decimal('1') Med = Decimal('0') Min = Decimal('-1') actions = [x for x in self.actions] currActions = set(actions) relation = self.relation rankingRelation = {} for x in actions: rankingRelation[x] = {} for y in actions: rankingRelation[x][y] = Med n = len(rankingByLastChoosing) for i in range(n): iwch = set(rankingByLastChoosing[i][1]) riwch = set(currActions) - iwch for x in iwch: for y in iwch: ## if Debug and (x == 'a10' and y == 'a08') : ## print(x,y,rankingRelation[x][y],relation[x][y]) ## print(y,x,rankingRelation[x][y],relation[y][x]) if x != y: ## rankingRelation[x][y] = self.omin( [rankingRelation[x][y],abs(relation[y][x])] ) ## rankingRelation[y][x] = self.omin( [rankingRelation[y][x],abs(relation[x][y])] ) rankingRelation[x][y] = min( [abs(relation[x][y]),abs(relation[y][x])] ) rankingRelation[y][x] = min( [abs(relation[y][x]),abs(relation[x][y])] ) for y in riwch: ## if Debug and (x == 'a10' and y == 'a08') : ## print(x,y,rankingRelation[x][y],relation[x][y]) ## print(y,x,rankingRelation[x][y],relation[y][x]) ## rankingRelation[x][y] = self.omin( [rankingRelation[x][y],-abs(relation[y][x])] ) ## rankingRelation[y][x] = self.omin( [rankingRelation[y][x],abs(relation[x][y])] ) rankingRelation[x][y] = -min( [abs(relation[x][y]),abs(relation[y][x])] ) rankingRelation[y][x] = min( [abs(relation[y][x]),abs(relation[x][y])] ) currActions = currActions - iwch return rankingRelation
[docs] def showRankingByChoosing(self,rankingByChoosing=None): """ A show method for self.rankinByChoosing result. .. warning:: The self.computeRankingByChoosing(CoDual=False/True) method instantiating the self.rankingByChoosing slot is pre-required ! """ if rankingByChoosing == None: try: rankingByChoosing = self.rankingByChoosing['result'] except: print('Error: You must first run self.computeRankingByChoosing(CoDual=True(default)|False) !') #rankingByChoosing = self.computeRankingByChoosing(Debug,CoDual) return else: rankingByChoosing = rankingByChoosing['result'] print('Ranking by Choosing and Rejecting') space = '' n = len(rankingByChoosing) for i in range(n): if i+1 == 1: nstr='st' elif i+1 == 2: nstr='nd' elif i+1 == 3: nstr='rd' else: nstr='th' ibch = set(rankingByChoosing[i][0][1]) iwch = set(rankingByChoosing[i][1][1]) iach = iwch & ibch #print 'ibch, iwch, iach', i, ibch,iwch,iach ch = list(ibch) ch.sort() print(' %s%s%s Best Choice %s (%.2f)' % (space,i+1,nstr,ch,rankingByChoosing[i][0][0])) if len(iach) > 0 and i < n-1: print(' %s Ambiguous Choice %s' % (space,list(iach))) space += ' ' space += ' ' for i in range(n): if n-i == 1: nstr='st' elif n-i == 2: nstr='nd' elif n-i == 3: nstr='rd' else: nstr='th' space = space[:-2] ibch = set(rankingByChoosing[n-i-1][0][1]) iwch = set(rankingByChoosing[n-i-1][1][1]) iach = iwch & ibch #print 'ibch, iwch, iach', i, ibch,iwch,iach ch = list(iwch) ch.sort() if len(iach) > 0 and i > 0: space = space[:-2] print(' %s Ambiguous Choice %s' % (space,list(iach))) print(' %s%s%s Worst Choice %s (%.2f)' % (space,n-i,nstr,ch,rankingByChoosing[n-i-1][1][0])) corr1 = self.computeBipolarCorrelation(self.computeRankingByChoosingRelation(rankingByChoosing)) print('Ordinal bipolar correlation with outranking relation: %.3f (%.1f%%)'% (corr1['correlation'],corr1['determination']*Decimal('100'))) corr2 = self.computeBipolarCorrelation(self.computeRankingByChoosingRelation(rankingByChoosing),MedianCut=True) print('Ordinal bipolar correlation with median cut outranking relation: %.3f (%.1f%%)'% (corr2['correlation'],corr2['determination']*Decimal('100')))
[docs] def showRankingByLastChoosing(self,rankingByLastChoosing=None,Debug=None): """ A show method for self.rankinByChoosing result. .. warning:: The self.computeRankingByLastChoosing(CoDual=False/True) method instantiating the self.rankingByChoosing slot is pre-required ! """ if rankingByLastChoosing == None: try: rankingByLastChoosing = self.rankingByLastChoosing['result'] except: print('Error: You must first run self.computeRankingByLastChoosing(CoDual=True(default)|False) !') return else: rankingByLastChoosing = rankingByLastChoosing['result'] print('Ranking by recursively rejecting') space = '' n = len(rankingByLastChoosing) for i in range(n): if i+1 == 1: nstr='st' elif i+1 == 2: nstr='nd' elif i+1 == 3: nstr='rd' else: nstr='th' iwch = set(rankingByLastChoosing[i][1]) if Debug: print( 'ibch, iwch, iach', i, ibch,iwch,iach) ch = list(iwch) ch.sort() if nstr == 'st': print(' Last Choice %s (%.2f)' % (ch,rankingByLastChoosing[i][0])) else: print(' %s%s%s Last Choice %s (%.2f)' % (space,i+1,nstr,ch,rankingByLastChoosing[i][0])) space += ' '
[docs] def showRankingByBestChoosing(self,rankingByBestChoosing=None): """ A show method for self.rankinByBestChoosing result. .. warning:: The self.computeRankingByBestChoosing(CoDual=False/True) method instantiating the self.rankingByBestChoosing slot is pre-required ! """ if rankingByBestChoosing == None: try: rankingByBestChoosing = self.rankingByBestChoosing['result'] except: print('Error: You must first run self.computeRankingByBestChoosing(CoDual=True(default)|False) !') return else: rankingByBestChoosing = rankingByBestChoosing['result'] print('Ranking by recursively best-choosing') space = '' n = len(rankingByBestChoosing) for i in range(n): if i+1 == 1: nstr='st' elif i+1 == 2: nstr='nd' elif i+1 == 3: nstr='rd' else: nstr='th' ibch = set(rankingByBestChoosing[i][1]) ch = list(ibch) ch.sort() print(' %s%s%s Best Choice %s (%.2f)' % (space,i+1,nstr,ch,rankingByBestChoosing[i][0])) space += ' '
[docs] def computeValuationStatistics(self,Sampling=False,Comments=False): """ Renders the mean and variance of the valuation of the non reflexive pairs. """ from math import sqrt mean = Decimal('0.0') squares = Decimal('0.0') #actions = self.actions #n = len(self.actions) n = self.order n2 = n * (n-1) n2d = Decimal(str(n2)) relation = self.relation for x,rx in relation.items(): for y,rxy in rx.items(): if x != y: mean += rxy squares += rxy*rxy mean = mean / n2d if Sampling: var = ( squares / (n2d-Decimal('1')) ) - (mean * mean) else: var = squares / n2d - (mean * mean) stdDev = sqrt(var) if Comments: print('mean: %.5f, std. dev.: %.5f' % (mean,stdDev)) return mean,stdDev
[docs] def computeRankingCorrelation(self, ranking, Debug=False): """ Renders the ordinal correlation K of a digraph instance when compared with a given linear ranking of its actions K = sum_{x != y} [ min( max(-self.relation(x,y)),other.relation(x,y), max(self.relation(x,y),-other.relation(x,y)) ] K /= sum_{x!=y} [ min(abs(self.relation(x,y),abs(other.relation(x,y)) ] .. note:: Renders a tuple with at position 0 the actual bipolar correlation index and in position 1 the minimal determination level D of self and the other relation. D = sum_{x != y} min(abs(self.relation(x,y)),abs(other.relation(x,y)) / n(n-1) where n is the number of actions considered. The correlation index with a completely indeterminate relation is by convention 0.0 at determination level 0.0 . """ selfMax = self.valuationdomain['max'] if selfMax != Decimal('1'): print("Error: self's valuationdomain must be normalized !") return n = len(ranking) corrSum = 0 determSum = 0 for i in range(n-1): x = ranking[i] for j in range(i+1,n): y = ranking[j] # x > y selfRelation = self.relation[x][y] otherRelation = selfMax corr = min( max(-selfRelation,otherRelation),\ max(selfRelation,-otherRelation) ) corrSum += corr determ = min( abs(selfRelation),abs(otherRelation) ) determSum += determ # y < x selfRelation = self.relation[y][x] otherRelation = -selfMax corr = min( max(-selfRelation,otherRelation),\ max(selfRelation,-otherRelation) ) corrSum += corr determ = min( abs(selfRelation),abs(otherRelation) ) determSum += determ if determSum > 0: correlation = float(corrSum) / float(determSum) n2 = (self.order*self.order) - self.order determination = (float(determSum) / n2) determination /= float(selfMax) return { 'correlation': correlation,\ 'determination': determination } else: return { 'correlation': 0.0,\ 'determination': 0.0 }
[docs] def computeOrderCorrelation(self, order, Debug=False): """ Renders the ordinal correlation K of a digraph instance when compared with a given linear order (from worst to best) of its actions K = sum_{x != y} [ min( max(-self.relation(x,y)),other.relation(x,y), max(self.relation(x,y),-other.relation(x,y)) ] K /= sum_{x!=y} [ min(abs(self.relation(x,y),abs(other.relation(x,y)) ] .. note:: Renders a dictionary with the key 'correlation' containing the actual bipolar correlation index and the key 'determination' containing the minimal determination level D of self and the other relation. D = sum_{x != y} min(abs(self.relation(x,y)),abs(other.relation(x,y)) / n(n-1) where n is the number of actions considered. The correlation index with a completely indeterminate relation is by convention 0.0 at determination level 0.0 . .. warning:: self must be a normalized outranking digraph instance ! """ selfMax = self.valuationdomain['max'] if selfMax != Decimal('1'): print("Error: self's valuationdomain must be normalized !") return n = len(order) corrSum = Decimal('0') determSum = Decimal('0') for i in range(n): x = order[i] for j in range(i+1,n): y = order[j] # x < y selfRelation = self.relation[x][y] otherRelation = -selfMax corr = min( max(-selfRelation,otherRelation),\ max(selfRelation,-otherRelation) ) corrSum += corr determ = min( abs(selfRelation),abs(otherRelation) ) determSum += determ # y > x selfRelation = self.relation[y][x] otherRelation = selfMax corr = min( max(-selfRelation,otherRelation),\ max(selfRelation,-otherRelation) ) corrSum += corr determ = min( abs(selfRelation),abs(otherRelation) ) determSum += determ if determSum > 0: correlation = corrSum / determSum n2 = (self.order*self.order) - self.order determination = determSum / Decimal(str(n2)) determination /= selfMax return { 'correlation': correlation,\ 'determination': determination } else: return { 'correlation': 0.0,\ 'determination': 0.0 }
[docs] def computeOrdinalCorrelationMP(self, other, MedianCut=False, Threading=True,nbrOfCPUs=None, Comments=False,Debug=False): """ Multi processing version of the digraphs.computeOrdinalCorrelation() method. .. note:: The relation filtering and the MedinaCut option are not implemented in the MP version. """ from multiprocessing import cpu_count from copy import copy,deepcopy from itertools import product if self.valuationdomain['min'] != Decimal('-1') or\ self.valuationdomain['max'] != Decimal('1'): print('Error: the digraph instance self must be normalized - self.recodeValuation(-1,1) -first !') return None else: g = self actionsList = [x for x in g.actions] n = g.order n2 = (n*(n-1)) Med = g.valuationdomain['med'] if not isinstance(other,(dict)): #if Debug: # print('inputting a Digraph instance') if other.valuationdomain['min'] != Decimal('-1') or\ other.valuationdomain['max'] != Decimal('1'): print('Error: the digraph instance other must be normalized - other.recodeValuation(-1,1) -first !') return None otherRelation = other.relation else: otherRelation = other #if Debug: # print(otherRelation) correlation = Decimal('0') determination = Decimal('0') if Threading and cpu_count() > 4: from pickle import Pickler,dumps, loads, load from io import BytesIO from multiprocessing import Process, Lock,\ active_children, cpu_count class myThread(Process): def __init__(self, threadID,TempDirName,Debug): Process.__init__(self) self.threadID = threadID self.workingDirectory = tempDirName self.Debug = Debug def run(self): from pickle import dumps, loads from os import chdir from decimal import Decimal chdir(self.workingDirectory) #Debug=False #if Debug: # print("Starting working in %s on %s" % (self.workingDirectory, self.name)) fi = open('dumpActions.py','rb') actionsList = loads(fi.read()) fi.close() #if Debug: # print(self.threadID,actionsList) fi = open('dumpRelation.py','rb') relation = loads(fi.read()) fi.close() #if Debug: # print(self.threadID,relation) fi = open('dumpOtherRelation.py','rb') otherRelation = loads(fi.read()) fi.close() #if Debug: # print(self.threadID,relation) fiName = 'splitActions-'+str(self.threadID)+'.py' fi = open(fiName,'rb') splitActions = loads(fi.read()) fi.close() #if Debug: # print(self.threadID,splitActions) # compute partial correlation correlation = Decimal('0') determination = Decimal('0') for x in splitActions: grx = g.relation[x] orx = otherRelation[x] for y in actionsList: if x != y: correlation += min( max(-grx[y],orx[y]),\ max(grx[y],-orx[y]) ) determination += min( abs(grx[y]),\ abs(orx[y]) ) #if Debug: # print(x,y,g.relation[x][y],otherRelation[x][y],correlation,determination) splitCorrelation = {'correlation': correlation, 'determination': determination} # write partial correlation relation foName = 'splitCorrelation-'+str(self.threadID)+'.py' fo = open(foName,'wb') fo.write(dumps(splitCorrelation,-1)) fo.close() # pre-threading operations if nbrOfCPUs == None: nbrOfCPUs = cpu_count() if Debug: print('Nbr of cpus = ',nbrOfCPUs) if Comments: print('Starting correlation computation with %d threads ...' % nbrOfCPUs) from tempfile import TemporaryDirectory with TemporaryDirectory() as tempDirName: selfFileName = tempDirName +'/dumpActions.py' #if Debug: # print('temDirName, selfFileName', tempDirName,selfFileName) fo = open(selfFileName,'wb') pd = dumps(actionsList,-1) fo.write(pd) fo.close() selfFileName = tempDirName +'/dumpRelation.py' #if Debug: # print('temDirName, selfFileName', tempDirName,selfFileName) fo = open(selfFileName,'wb') pd = dumps(self.relation,-1) fo.write(pd) fo.close() selfFileName = tempDirName +'/dumpOtherRelation.py' #if Debug: # print('temDirName, selfFileName', tempDirName,selfFileName) fo = open(selfFileName,'wb') pd = dumps(otherRelation,-1) fo.write(pd) fo.close() nit = n//nbrOfCPUs nbrOfJobs = nbrOfCPUs if nit*nbrOfCPUs < n: nit += 1 while nit*(nbrOfJobs-1) >= n: nbrOfJobs -= 1 if Comments: print('nbr of actions to split',n) print('nbr of jobs = ',nbrOfJobs) print('nbr of splitActions = ',nit) i = 0 actions2Split = actionsList actionsRemain = set(actions2Split) for jb in range(nbrOfJobs): if Comments: print('Thread = %d/%d' % (jb+1,nbrOfJobs),end=" ") splitActions=[] for k in range(nit): if jb < (nbrOfJobs -1) and i < n: splitActions.append(actions2Split[i]) else: splitActions = list(actionsRemain) i += 1 #if Debug: # print(len(splitActions)) # print(splitActions) actionsRemain = actionsRemain - set(splitActions) #if Debug: # print(actionsRemain) foName = tempDirName+'/splitActions-'+str(jb)+'.py' fo = open(foName,'wb') spa = dumps(splitActions,-1) fo.write(spa) fo.close() splitThread = myThread(jb,tempDirName,Debug) splitThread.start() while active_children() != []: pass # post threading operations if Comments: print('Exiting computing threads') for jb in range(nbrOfJobs): #if Debug: # print('Post job-%d/%d processing' % (jb+1,nbrOfJobs)) # print('job',jb) fiName = tempDirName+'/splitCorrelation-'+str(jb)+'.py' fi = open(fiName,'rb') splitCorrelation = loads(fi.read()) #if Debug: # print('splitCorrelation',splitCorrelation) fi.close() correlation += splitCorrelation['correlation'] determination += splitCorrelation['determination'] else: # no Threading if Debug: print('No threading !') ## correlation, determination = sum([ ## (min( max(-g.relation[x][y],otherRelation[x][y]),\ ## max(g.relation[x][y],-otherRelation[x][y]) ),\ ## min( abs(g.relation[x][y]),\ ## abs(otherRelation[x][y]) )) for \ ## (x,y) in product(g.actions, repeat = 2)]) ## for x,y in product(actions,repeat=1) for x in dict.keys(g.actions): grx = g.relation[x] orx = otherRelation[x] for y in dict.keys(g.actions): if x != y: corr = min( max(-grx[y],orx[y]),\ max(grx[y],-orx[y]) ) correlation += corr determination += min( abs(grx[y]),\ abs(orx[y]) ) #if Debug: # print(x,y,g.relation[x][y],otherRelation[x][y],correlation,determination) if determination > Decimal('0.0'): correlation /= determination return { 'correlation': correlation,\ 'determination': determination / Decimal(str(n2)) } else: return {'correlation': Decimal('0.0'),\ 'determination': determination}
[docs] def computeOrdinalCorrelation(self, other, MedianCut=False, filterRelation=None, Debug=False): """ Renders the bipolar correlation K of a self.relation when compared with a given compatible (same actions set)) digraph or a [-1,1] valued compatible relation (same actions set). If MedianCut=True, the correlation is computed on the median polarized relations. If filterRelation != None, the correlation is computed on the partial domain corresponding to the determined part of the filter relation. .. warning:: Notice that the 'other' relation and/or the 'filterRelation', the case given, must both be normalized, ie [-1,1]-valued ! K = sum_{x != y} [ min( max(-self.relation[x][y]),other.relation[x][y]), max(self.relation[x][y],-other.relation[x][y]) ] K /= sum_{x!=y} [ min(abs(self.relation[x][y]),abs(other.relation[x][y])) ] .. note:: Renders a tuple with at position 0 the actual bipolar correlation index and in position 1 the minimal determination level D of self and the other relation. D = sum_{x != y} min(abs(self.relation[x][y]),abs(other.relation[x][y])) / n(n-1) where n is the number of actions considered. The correlation index with a completely indeterminate relation is by convention 0.0 at determination level 0.0 . """ from copy import copy,deepcopy g = deepcopy(self) g.recodeValuation(-1,1) actions = g.actions Med = g.valuationdomain['med'] if MedianCut: g = PolarisedDigraph(g,level=Decimal('0.0'),KeepValues=False,StrictCut=True) if not isinstance(other,(dict)): if Debug: print('inputting a Digraph instance') otherg = deepcopy(other) otherg.recodeValuation(-1,1) if MedianCut: otherg = PolarisedDigraph(otherg,level=Decimal('0.0'),KeepValues=False,StrictCut=True) otherRelation = otherg.relation else: otherRelation = deepcopy(other) if MedianCut: for x in dict.keys(actions): rx = otherRelation[x] for y in dict.keys(actions): if x == y: rx[y] = Decimal('0.0') else: if rx[y] > Med: rx[y] = Decimal('1.0') elif rx[y] < Med: rx[y] = Decimal('-1.0') else: rx[y] = Decimal('0.0') correlation = Decimal('0.0') determination = Decimal('0.0') if filterRelation == None: n = len(actions) n2 = (n*(n-1)) for x in dict.keys(actions): grx = g.relation[x] orx = otherRelation[x] for y in dict.keys(actions): if x != y: corr = min( max(-grx[y],orx[y]), max(grx[y],-orx[y]) ) correlation += corr determination += min( abs(grx[y]),abs(orx[y]) ) if Debug: print(x,y,grx[y],orx[y],correlation,determination) else: n = len(actions) n2 = (n*(n-1)) for x in dict.keys(actions): for y in dict.keys(actions): if x != y: if filterRelation[x][y] != Med: corr = min( max(-g.relation[x][y],otherRelation[x][y]), max(g.relation[x][y],-otherRelation[x][y]) ) correlation += corr determination += min( abs(g.relation[x][y]),abs(otherRelation[x][y]) ) #determination += abs(corr) if Debug: print(x,y,g.relation[x][y],otherRelation[x][y],filterRelation[x][y],correlation,determination) if determination > Decimal('0.0'): correlation /= determination return { 'MedianCut':MedianCut, 'correlation': correlation,\ 'determination': determination / Decimal(str(n2)) } else: return {'MedianCut':MedianCut, 'correlation': Decimal('0.0'),\ 'determination': determination}
[docs] def computeBipolarCorrelation(self, other, MedianCut=False, filterRelation=None, Debug=False): """ obsolete: dummy replacement for Digraph.computeOrdinalCorrelation method """ return self.computeOrdinalCorrelation(other= other,MedianCut=MedianCut,\ filterRelation=filterRelation,Debug=Debug)
[docs] def computeKemenyIndex(self, otherRelation): """ renders the Kemeny index of the self.relation compared with a given crisp valued relation of a compatible other digraph (same nodes or actions). """ KemenyIndex = 0.0 actions = self.actions for x in dict.keys(actions): srx = self.relation[x] orx = otherRelation[x] for y in dict.keys(actions): if x != y: if orx[y] > Decimal('0'): KemenyIndex += float(srx[y]) elif orx[y] < Decimal('0'): KemenyIndex -= float(srx[y]) return KemenyIndex
[docs] def flatChoice(self,ch,Debug=False): """ Converts set or list ch recursively to a flat list of items. """ result = [] for x in ch: if Debug: print(x) if isinstance(x,frozenset): for y in self.flatChoice(x,Debug): result.append(y) else: result.append(x) if Debug: print(result) return result
[docs] def convertValuationToDecimal(self): """ Convert the float valuation limits to Decimals. """ self.valuationdomain['min'] = Decimal(str(self.valuationdomain['min'])) self.valuationdomain['med'] = Decimal(str(self.valuationdomain['med'])) self.valuationdomain['max'] = Decimal(str(self.valuationdomain['max']))
[docs] def convertRelationToDecimal(self): """ Converts the float valued self.relation in a decimal valued one. """ actions = self.actions relation = {} for x in actions: relation[x] = {} rx = relation[x] srx = self.relation[x] for y in actions: rx[y] = Decimal(str(srx[y])) self.relation = relation
#return relation
[docs] def bipolarKCorrelation(self, digraph,Debug=False): """ Renders the bipolar Kendall correlation between two bipolar valued digraphs computed from the average valuation of the XORDigraph(self,digraph) instance. .. warning:: Obsolete! Is replaced by the self.computeBipolarCorrelation(other) Digraph method """ xor = XORDigraph(self,digraph,Debug) if Debug: xor.showRelationTable() actions = self.actions n = len(actions) xor.recodeValuation(-1.0,1.0) kDistance = Decimal("0.0") for x in dict.keys(actions): for y in dict.keys(actions): if x != y: kDistance += xor.relation[x][y] kDistance = Decimal(str(kDistance)) / Decimal(str((n * (n-1)))) # the negation of the kDistance, i.e. -kDistance gives # the bipolar extended Kendall tau correlation return -kDistance
[docs] def crispKDistance(self, digraph,Debug=False): """ Renders the crisp Kendall distance between two bipolar valued digraphs. .. warning:: Obsolete! Is replaced by the self.computeBipolarCorrelation(other, MedianCut=True) Digraph method """ xor = XORDigraph(self,digraph,Debug) if Debug: xor.showRelationTable() actions = self.actions n = len(actions) k2Distance = xor.computeSize() k2Distance = Decimal(str(k2Distance)) / Decimal(str((n * (n-1)))) return k2Distance
[docs] def bipolarKDistance(self, digraph,Debug=False): """ Renders the bipolar crisp Kendall distance between two bipolar valued digraphs. .. warning:: Obsolete! Is replaced by the self.computeBipolarCorrelation(other, MedianCut=True) Digraph method """ xor = XORDigraph(self,digraph,Debug) if Debug: xor.showRelationTable() #actions = [x for x in self.actions] n = len(self.actions) k2Distance = xor.computeCoSize() - xor.computeSize() k2Distance = Decimal(str(k2Distance)) / Decimal(str((n * (n-1)))) return k2Distance
[docs] def computeWeakCondorcetWinners(self): """ Wrapper for weakCondorcetWinners(). """ return self.weakCondorcetWinners()
[docs] def weakCondorcetWinners(self): """ Renders the set of decision actions x such that self.relation[x][y] >= self.valuationdomain['med'] for all y != x. """ #actions = self.actions relation = self.relation Med = self.valuationdomain['med'] wCW = [] for x,rx in relation.items(): #rx = relation[x] Winner = True for y,rxy in rx.items(): if x != y: if rx[y] < Med: Winner = False break if Winner: wCW.append(x) try: wCW.sort() except: pass return wCW
[docs] def computeCondorcetWinners(self): """ Wrapper for condorcetWinners(). """ return self.condorcetWinners()
[docs] def condorcetWinners(self): """ Renders the set of decision actions x such that self.relation[x][y] > self.valuationdomain['med'] for all y != x. """ #actions = self.actions relation = self.relation Med = self.valuationdomain['med'] CW = [] for x,rx in relation.items(): #rx = relation[x] Winner = True for y,rxy in rx.items(): if x != y: if rxy <= Med: Winner = False break if Winner: CW.append(x) try: CW.sort() except: pass return CW
[docs] def forcedBestSingleChoice(self): """ Renders the set of most determined outranking singletons in self. """ actions = self.actions relation = self.relation valuationList = [] for x in dict.keys(actions): for y in dict.keys(actions): if relation[x][y] not in valuationList: valuationList.append(relation[x][y]) valuationList.sort() print('Credibility levels:', valuationList) bestSingleChoices = set( list(dict.keys(actions)) ) i=0 while bestSingleChoices != set(): current = set(bestSingleChoices) i += 1 print('i_bestSingleChoices:', i, bestSingleChoices) print('level', valuationList[i]) for x in current: #print 'x', x rx = relation[x] notBest = False for y in actions: #print 'y', y, relation[x][y] if x != y and rx[y] < valuationList[i]: notBest = True if notBest: bestSingleChoices.remove(x) print('final bestSingleChoice:', current) print('leveal of credibility:', valuationList[i-1]) return (valuationList[i-1], current)
[docs] def computeMoreOrLessUnrelatedPairs(self): """ Renders a list of more or less unrelated pairs. """ actions = self.actions relation = self.relation Min = self.valuationdomain['min'] Med = self.valuationdomain['med'] moreOrLessUnrelatedPairs = [] for x in dict.keys(actions): for y in dict.keys(actions): if x != y: if relation[x][y] < Med and relation[x][y] > Min: if relation[y][x] < Med and relation[y][x] > Min: if ((y,x),(relation[y][x],relation[x][y])) not in moreOrLessUnrelatedPairs: moreOrLessUnrelatedPairs.append(((x,y),(relation[x][y],relation[y][x]))) return moreOrLessUnrelatedPairs
[docs] def computeUnrelatedPairs(self): """ Renders a list of more or less unrelated pairs. """ actions = self.actions relation = self.relation Min = self.valuationdomain['min'] Med = self.valuationdomain['med'] unrelatedPairs = [] for x in dict.keys(actions): for y in dict.keys(actions): if x != y: if relation[x][y] < Med: if relation[y][x] < Med: if ((y,x),(relation[y][x],relation[x][y])) not in unrelatedPairs: unrelatedPairs.append(((x,y),(relation[x][y],relation[y][x]))) return unrelatedPairs
[docs] def closeSymmetric(self): """ Produces the symmetric closure of self.relation. """ actions = set(self.actions) symRelation = {} relation = self.relation for x in relation: symRelation[x] = {} for y in relation[x]: symRelation[x][y] = max(relation[x][y],relation[y][x]) self.relation = symRelation self.gamma = self.gammaSets() self.notGamma = self.notGammaSets()
[docs] def computeTransitivityDegree(self): """ Renders the transitivity degree of a digraph. """ import copy Med = self.valuationdomain['med'] #actionsList = [x for x in self.actions] actions = self.actions relationOrig = copy.deepcopy(self.relation) self.closeTransitive() relation = self.relation n0 = Decimal('0') n1 = Decimal('0') for x in actions: rox = relationOrig[x] rx = relation[x] for y in actions: if rox[y] > Med: n0 += 1 if rx[y] > Med: n1 += 1 self.relation = copy.deepcopy(relationOrig) self.gamma = self.gammaSets() self.notGamma = self.notGammaSets() if n1 > Decimal('0'): return n0/n1 else: return Decimal('0')
[docs] def computeSizeTransitiveClosure(self): """ Renders the size of the transitive closure of a digraph. """ import copy Med = self.valuationdomain['med'] #actionsList = [x for x in self.actions] relationOrig = copy.deepcopy(self.relation) self.closeTransitive() #relation = self.relation n1 = 0 for rx in self.relation.values(): for rxy in rx.values(): if rxy > Med: n1 += 1 self.relation = copy.deepcopy(relationOrig) self.gamma = self.gammaSets() self.notGamma = self.notGammaSets() return n1
[docs] def closeTransitive(self,Irreflexive=True,Reverse=False): """ Produces the transitive closure of self.relation. """ import copy actions = set(self.actions) relation = copy.deepcopy(self.relation) if Irreflexive: for x in actions: relation[x][x] = self.valuationdomain['min'] for x in actions: for y in actions: for z in actions: if Reverse: if min(relation[y][x],relation[x][z]) > self.valuationdomain['med']: relation[y][z] = self.valuationdomain['min'] else: relation[y][z] = max(relation[y][z],min(relation[y][x],relation[x][z])) self.relation = copy.deepcopy(relation) self.gamma = self.gammaSets() self.notGamma = self.notGammaSets()
[docs] def isCyclic(self, Debug=False): """ checks the cyclicity of self.relation by checking for a reflexive loop in its transitive closure !! self.relation is supposed to be irreflexive !! """ import copy Med = self.valuationdomain['med'] if Debug: print(Med) actions = set(self.actions) relation = copy.deepcopy(self.relation) isCyclic = False for x in actions: for y in actions: for z in actions: relation[y][z] = max(relation[y][z],min(relation[y][x],relation[x][z])) if Debug: for x in actions: print('x, relation[x][x]', x, relation[x][x]) for x in actions: if relation[x][x] > Med: isCyclic = True break return isCyclic
[docs] def isWeaklyComplete(self, Debug=False): """ checks the weakly completeness property of self.relation by checking for the absence of a link between two actions!! .. warning:: The reflexive links are ignored !! """ Med = self.valuationdomain['med'] if Debug: print('Med = ', Med) listActions = [x for x in self.actions] n = len(listActions) relation = self.relation isWeaklyComplete = True for i in range(n): x = listActions[i] for j in range(i+1,n): y = listActions[j] if relation[x][y] < Med and relation[y][x] < Med: isWeaklyComplete = False if Debug: print('x,y,relation[x][y],relation[y][x]',\ x, y, relation[x][y], relation[y][x]) break if not isWeaklyComplete: break return isWeaklyComplete
[docs] def isComplete(self, Debug=False): """ checks the completeness property of self.relation by checking for the absence of a link between two actions!! .. warning:: The reflexive links are ignored !! """ Med = self.valuationdomain['med'] if Debug: print('Med = ', Med) listActions = [x for x in self.actions] n = len(listActions) relation = self.relation isComplete = True for i in range(n): x = listActions[i] for j in range(i+1,n): y = listActions[j] if relation[x][y] <= Med and relation[y][x] <= Med: isComplete = False if Debug: print('x,y,relation[x][y],relation[y][x]',\ x, y, relation[x][y], relation[y][x]) break if not isComplete: break return isComplete
[docs] def automorphismGenerators(self): """ Add automorphism group generators to digraph. """ import os Name = self.name self.savedre(Name) aindex = self.aindex arevindex = {} for i in aindex: arevindex[str(aindex[i])] = i print(arevindex) File0 = Name+'.dre' File1 = Name+'.auto' print('# automorphisms extraction from dre file #') print('# Using input file: ' + File0) String2 = "echo '<"+File0+' -m p >'+File1+" x' | dreadnaut" print(String2) os.system(String2) try: f1 = open(File1,'r') noError = True except: print('The input file: ', File1,' could not be found!') print("Be sure that nauty's dreadnaut programm is available!") noError = False if noError: permutations = {} t = f1.readline() nl = 0 while t[:1] != '': nl += 1 if t[:1] == ' ': ts = f1.readline() while ts[:2] == ' ': suite = 1 t = t + ts ts = f1.readline() permutation = t.split() print('# permutation = '+ str(nl)+str(permutation)) permutations[str(nl)] = {} for i in range(len(permutation)): permutations[str(nl)][str(arevindex[str(i+1)])] = str(arevindex[str(permutation[i])]) t = ts else: #print '# ', t grpsize = '' for i in range(len(t)): #print t[i], if t[i] == '=': #print 'ok' #grpsize = '' for j in range(i+1,len(t)): if t[j] != ';': #print t[j] grpsize += t[j] else: break break #print eval(grpsize) #t = f1.readline break f1.close() self.reflections = {} self.permutations = permutations self.automorphismGroupSize = eval(grpsize)
[docs] def showAutomorphismGenerators(self): """ Renders the generators of the automorphism group. """ print('*---- Automorphism group generators ----') try: reflections = self.reflections permutations = self.permutations noError = True except: print('No permutations or reflections defined yet !!') noError = False if noError: print('Permutations') for g in permutations: print(self.permutations[g]) print('Reflections') for g in reflections: print(self.reflexions[g]) else: print('Run self.automorphismGenerators()')
[docs] def showOrbits(self,InChoices,withListing=True): """ Prints the orbits of Choices along the automorphisms of the digraph self. """ try: reflections = self.reflections permutations = self.permutations noError = True except: print('No permutations or reflections defined yet !!') print('Run self.automorphismGenerators()') noError=False if noError: Choices = InChoices.copy() print('*--- Isomorphic reduction of choices') Iso = set() v = [0 for i in range(1,self.automorphismGroupSize + 1)] print('Number of choices:', len(Choices)) while Choices != set(): sCur = Choices.pop() print() print('current representative: ',sCur) print('length : ', len(sCur)) IsosCur = set([sCur]) Isos = set() while IsosCur != Isos: Isos = IsosCur.copy() IsosRes = IsosCur.copy() for s in IsosCur: for g in reflections: cur = s for a in reflections[g]: if (a[0] in cur) and a[1] not in cur: cur = cur - set([a[0]]) cur = cur | set([a[1]]) else: if a[1] in cur and a[0] not in cur: cur = cur - set([a[1]]) cur = cur | set([a[0]]) IsosRes.add(cur) IsosCur = IsosRes.copy() for s in IsosCur: for g in permutations: cur = frozenset() for x in s: cur = cur | set([permutations[g][str(x)]]) IsosRes = IsosRes | set([cur]) IsosCur = IsosRes.copy() Iso.add(sCur) niso = len(Isos) print('number of isomorph choices', niso) v[(self.automorphismGroupSize//niso)-1] += 1 if withListing: print('isormorph choices') for ch in Isos: print(list(ch)) print('Number of choices before : ', len(Choices) + 1) Choices = Choices - Isos print('Number of choices after : ', len(Choices)) print() print('*---- Global result ----') print('Number of choices: ', len(InChoices)) print('Number of orbits : ', len(Iso)) print('Labelled representatives:') for ch in Iso: print(list(ch)) print() print(' Symmetry vector') print('stabilizer size : ', list(range(1,self.automorphismGroupSize + 1))) print('frequency : ', v) self.orbits = Iso
[docs] def showOrbitsFromFile(self,InFile,withListing=True): """ Prints the orbits of Choices along the automorphisms of the digraph self by reading in the 0-1 misset file format. """ try: reflections = self.reflections permutations = self.permutations f1 = open(InFile,'r') noError = True except: print('No permutations or reflections defined yet !!') print('Run self.automorphismGenerators()') noError = False if noError: actions = [x for x in self.actions] print('*--- Isomorphic reduction of choices') Iso = set() misset = set() v = [0 for i in range(1,self.order + 1)] while 1: line = f1.readline() if not line: break sCur = set() for i in range(len(line)): if line[i] == '1': sCur.add(actions[i]) if sCur not in misset: print('current representative: ',sCur) print('length : ', len(sCur)) IsosCur = set([frozenset(sCur)]) Isos = set() while IsosCur != Isos: Isos = IsosCur.copy() IsosRes = IsosCur.copy() for s in IsosCur: for g in reflections: cur = s for a in reflections[g]: if (a[0] in cur) and a[1] not in cur: cur = cur - set([a[0]]) cur = cur | set([a[1]]) else: if a[1] in cur and a[0] not in cur: cur = cur - set([a[1]]) cur = cur | set([a[0]]) IsosRes.add(cur) IsosCur = IsosRes.copy() for s in IsosCur: for g in permutations: cur = frozenset() for x in s: cur = cur | set([permutations[g][x]]) IsosRes = IsosRes | set([cur]) IsosCur = IsosRes.copy() Iso = Iso | set([frozenset(sCur)]) niso = len(Isos) print('number of isomorph choices', niso) v[((2*self.order)//niso)-1] += 1 if withListing: print('isormorph choices') for ch in Isos: print(list(ch)) print('Number of choices before : ', len(misset) + 1) misset = misset | Isos print('Number of choices after : ', len(misset)) print() print('*---- Global result ----') print('Labelled representatives:') for ch in Iso: print(list(ch)) print() print('Number of choices: ', len(misset)) print('Number of orbits : ', len(Iso)) print('symmetry vector : ', list(range(1,self.order + 1))) print('frequency : ', v) self.orbits = Iso
[docs] def readPerrinMisset(self,file): """ read method for 0-1-char-coded MISs from perrinMIS.c curd.dat file. """ try: f1 = open(file,'r') noError = True except: noError = False print('The input file: ', file,' could not be found ?') if noError: actions = [x for x in self.actions] nl = 0 misset = set() while 1: line = f1.readline() if not line: break nl += 1 mis = set() for i in range(len(line)): if ord(line[i]) == 1: mis.add(actions[i]) #print mis misset = misset | set([frozenset(mis)]) #print 'Reading ' + str(nl) + ' MISs.' self.misset = misset
[docs] def readPerrinMissetOpt(self,file): """ read method for 0-1-char-coded MISs from perrinMIS.c curd.dat file. """ try: f1 = open(file,'r') noError = True except: noError = False print('The input file: ', file,' could not be found ?') if noError: actions = [x for x in self.actions] nl = 0 misset = set() for line in f1.readlines(): if not line: break nl += 1 mis = set() for i in range(len(line)): if line[i] == '1': mis.add(actions[i]) #print mis misset = misset | set([frozenset(mis)]) #print 'Reading ' + str(nl) + ' MISs.' self.misset = misset
[docs] def computeOrbit(self,choice,withListing=False): """ renders the set of isomorph copies of a choice following the automorphism of the digraph self """ try: reflections = self.reflections permutations = self.permutations if withListing: print('*- ----------------"') print('Compute orbit of choice: ',choice) print('follwoing automorphisms of digraph: ', self.name) print('Automorphism group size: ', self.automorphismGroupSize) print('Generators:') print('Reflections: ', reflections) print('Permutations: ', permutations) IsosCur = set([choice]) Isos = set() while IsosCur != Isos: Isos = IsosCur.copy() IsosRes = IsosCur.copy() for s in IsosCur: for g in reflections: cur = s for a in reflections[g]: if (a[0] in cur) and a[1] not in cur: cur = cur - set([a[0]]) cur = cur | set([a[1]]) else: if a[1] in cur and a[0] not in cur: cur = cur - set([a[1]]) cur = cur | set([a[0]]) IsosRes.add(cur) IsosCur = IsosRes.copy() for s in IsosCur: for g in permutations: cur = frozenset() for x in s: cur = cur | set([permutations[g][x]]) IsosRes = IsosRes | set([cur]) IsosCur = IsosRes.copy() if withListing: print('Orbit size: ', len(Isos)) print('List of isormorph choices') for ch in Isos: print(list(ch)) return Isos except: print('No permutations or reflections defined yet !!') print('Run self.automorphismGenerators()')
[docs] def showActions(self): """ presentation methods for digraphs actions """ print('*----- show digraphs actions --------------*') actionsList = [x for x in self.actions] actionsList.sort() for x in actionsList: print('key: ',x) try: print(' short name:',self.actions[x]['shortName']) except: pass print(' name: ',self.actions[x]['name']) print(' comment: ',self.actions[x]['comment']) print()
[docs] def showShort(self): """ concise presentation method for genuine digraphs. """ print('*----- show short --------------*') print('Digraph :', self.name) print('Actions :', self.actions) print('Valuation domain :', self.valuationdomain) self.showComponents()
[docs] def showAll(self): print('*----- show detail -------------*') print('Digraph :', self.name) print('*---- Actions ----*') #actionsList = [x for x in self.actions] actionsList = [] for x in self.actions: if isinstance(x,frozenset): actionsList += [self.actions[x]['name']] else: actionsList += [str(x)] actionsList.sort() print(actionsList) print('*---- Characteristic valuation domain ----*') print(self.valuationdomain) self.showRelationTable() self.showComponents() gamma = self.gammaSets() notGamma = self.notGammaSets() print('Neighborhoods:') print(' Gamma :') for x in gamma: print('\'%s\': in => %s, out => %s' % (x,gamma[x][1],gamma[x][0])) print(' Not Gamma :') for x in notGamma: print('\'%s\': in => %s, out => %s' % (x,notGamma[x][1],notGamma[x][0]))
[docs] def showNeighborhoods(self): """ Lists the gamma and the notGamma function of self. """ gamma = self.gammaSets() notGamma = self.notGammaSets() print('Neighborhoods:') print(' Gamma :') for x in gamma: print('\'%s\': in => %s, out => %s' % (x,gamma[x][1],gamma[x][0])) print(' Not Gamma :') for x in notGamma: print('\'%s\': in => %s, out => %s' % (x,notGamma[x][1],notGamma[x][0]))
[docs] def showRelation(self): """ prints the relation valuation in ##.## format. """ print('* ---- Relation -----', end=' ') actionsList = [] for x in self.actions: if isinstance(x,frozenset): actionsList += [(self.actions[x]['name'],x)] else: actionsList += [(x,x)] #actionsList = [x for x in self.actions] actionsList.sort() try: hasIntegerValuation = self.valuationdomain['hasIntegerValuation'] except KeyError: hasIntegerValuation = False for x in actionsList: print() for y in actionsList: if hasIntegerValuation: print('('+str(x[0])+', '+str(y[0])+') = '+' % .2f ' % (self.relation[x[1]][y[1]])) else: print('('+str(x[0])+', '+str(y[0])+') = '+' %d ' % (self.relation[x[1]][y[1]])) print()
[docs] def showRelationMap(self,symbols=None,rankingRule="Copeland"): """ Prints on the console, in text map format, the location of certainly validated and certainly invalidated outranking situations. By default, symbols = {'max':'┬','positive': '+', 'median': ' ', 'negative': '-', 'min': '┴'} The default ordering of the output is following the Copeland ranking rule from best to worst actions. Further available ranking rules are net flows (rankingRule="netFlows"), Kohler's (rankingRule="kohler"), and Tideman's ranked pairs rule (rankingRule="rankedPairs"). Example:: >>> from outrankingDigraphs import * >>> t = RandomCBPerformanceTableau(numberOfActions=25,seed=1) >>> g = BipolarOutrankingDigraph(t,Normalized=True) >>> gcd = ~(-g) # strict outranking relation >>> gcd.showRelationMap(rankingRule="netFlows") - ++++++++ +++++┬+┬┬+ - - + +++++ ++┬+┬+++┬++ ┴+ ┴ + ++ ++++┬+┬┬++┬++ - ++ - ++++-++++++┬++┬+ - - - ++- ┬- + -+┬+-┬┬ ----- - -┬┬┬-+ -┬┬ ---- --+-+++++++++++++ -- --+- --++ ++ +++-┬+-┬┬ ---- - -+-- ++--+++++ + ----- ++- --- +---++++┬ + -- -- ---+ -++-+++-+ +-++ -- --┴---+ + +-++-+ - + ---- ┴---+-- ++--++++ - + --┴┴-- --- - --+ --┬┬ ---------+--+ ----- +-┬┬ -┴---┴- ---+- + ---+++┬ + -┴┴--┴---+--- ++ -++--+++ -----┴--- ---+-+- ++---+ -┴┴--------------- --++┬ --┴---------------- --+┬ ┴--┴┴ -┴--┴┴-┴ --++ ++-+ ----┴┴--------------- - ┴┴┴----+-┴+┴---┴-+---+ ┴+ ┴┴-┴┴┴-┴- - -┴┴---┴┴+ ┬ - ----┴┴-┴-----┴┴--- - -- Ranking rule: netFlows >>> """ if symbols == None: symbols = {'max':'┬','positive': '+', 'median': ' ', 'negative': '-', 'min': '┴'} if rankingRule == "Copeland": ranking = self.computeCopelandRanking() elif rankingRule == "netFlows": ranking = self.computeNetFlowsRanking() elif rankingRule == "rankedPairs": ranking = self.computeRankedPairsRanking() else: rankingRule = "Alphabetic" ranking = [x for x in self.actions] ranking.sort() relation = self.relation Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] for x in ranking: rx = relation[x] pictStr = '' for y in ranking: if rx[y] == Max: pictStr += symbols['max'] elif rx[y] == Min: pictStr += symbols['min'] elif rx[y] > Med: pictStr += symbols['positive'] elif rx[y] ==Med: pictStr += symbols['median'] elif rx[y] < Med: pictStr += symbols['negative'] print(pictStr) print('Ranking rule: %s' % rankingRule)
[docs] def showRelationTable(self,Sorted=True,\ IntegerValues=False,\ actionsSubset= None,\ relation=None,\ ndigits=2,\ ReflexiveTerms=True): """ prints the relation valuation in actions X actions table format. """ if actionsSubset == None: actions = self.actions else: actions = actionsSubset if relation == None: relation = self.relation print('* ---- Relation Table -----\n', end=' ') print(' S | ', end=' ') #actions = [x for x in actions] actionsList = [] for x in actions: if isinstance(x,frozenset): try: actionsList += [(actions[x]['shortName'],x)] except: actionsList += [(actions[x]['name'],x)] else: actionsList += [(str(x),x)] if Sorted: actionsList.sort() #print actionsList #actionsList.sort() try: hasIntegerValuation = self.valuationdomain['hasIntegerValuation'] except KeyError: hasIntegerValuation = IntegerValues for x in actionsList: print("'"+x[0]+"'\t ", end=' ') print('\n-----|------------------------------------------------------------') for x in actionsList: print("'"+x[0]+"' | ", end=' ') for y in actionsList: if x != y: if hasIntegerValuation: print('%d\t' % (relation[x[1]][y[1]]), end=' ') else: formatString = '%%2.%df\t' % ndigits print(formatString % (relation[x[1]][y[1]]), end=' ') else: if ReflexiveTerms: if hasIntegerValuation: print('%d\t' % (relation[x[1]][y[1]]), end=' ') else: formatString = '%%2.%df\t' % ndigits print(formatString % (relation[x[1]][y[1]]), end=' ') else: formatString = ' - \t' print(formatString, end=' ') print() print('\n') if hasIntegerValuation: print('Valuation domain: [%d;%+d]'% (self.valuationdomain['min'], self.valuationdomain['max'])) else: formatString = 'Valuation domain: [%%2.%df;%%2.%df]\n' % (ndigits,ndigits) print( formatString % (self.valuationdomain['min'], self.valuationdomain['max']))
[docs] def showHTMLRelationMap(self,actionsList=None,\ rankingRule='Copeland',\ Colored=True,\ tableTitle='Relation Map',\ relationName='r(x S y)',\ symbols=['+','&middot;','&nbsp;','&#150;','&#151'] ): """ Launches a browser window with the colored relation map of self. See corresponding Digraph.showRelationMap() method. Example:: >>> from outrankingDigraphs import * >>> t = RandomCBPerformanceTableau(numberOfActions=25,seed=1) >>> g = BipolarOutrankingDigraph(t,Normalized=True) >>> gcd = ~(-g) # strict outranking relation >>> gcd.showHTMLRelationMap(rankingRule="netFlows") .. image:: relationMap.png :alt: Browser view of a relation map :width: 600 px :align: center """ import webbrowser fileName = '/tmp/relationMap.html' fo = open(fileName,'w') fo.write(self.htmlRelationMap(actionsSubset=actionsList, rankingRule=rankingRule, Colored=Colored, tableTitle=tableTitle, symbols=symbols, ContentCentered=True, relationName=relationName)) fo.close() url = 'file://'+fileName webbrowser.open_new(url)
[docs] def htmlRelationMap(self,tableTitle='Relation Map',\ relationName='r(x R y)',\ actionsSubset= None,\ rankingRule='Copeland',\ symbols=['+','&middot;','&nbsp;','-','_'],\ Colored=True,\ ContentCentered=True): """ renders the relation map in actions X actions html table format. """ Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] Max = self.valuationdomain['max'] # construct ranking and actionsList if actionsSubset != None: ranking = actionsSubset else: if rankingRule == "Copeland": ranking = self.computeCopelandRanking() elif rankingRule == "netFlows": ranking = self.computeNetFlowsRanking() elif rankingRule == "rankedPairs": ranking = self.computeRankedPairsRanking() else: rankingRule = "Alphabetic" ranking = [x for x in self.actions] ranking.sort() actionsList = [] for x in ranking: if isinstance(x,frozenset): try: actionsList += [(actions[x]['shortName'],x)] except KeyError: actionsList += [(actions[x]['name'],x)] else: actionsList += [(str(x),str(x))] # construct html text s = '<!DOCTYPE html><html><head>\n' s += '<meta charset="UTF-8">\n' s += '<title>%s</title>\n' % 'Digraph3 relation map' s += '<style type="text/css">\n' if ContentCentered: s += 'td {text-align: center;}\n' s += 'td.na {color: rgb(192,192,192);}\n' s += '</style>\n' s += '</head>\n<body>\n' s += '<h1>%s</h1>' % tableTitle s += '<h2>Ranking rule: %s</h2>' % rankingRule s += '<table border="0">\n' if Colored: s += '<tr bgcolor="#9acd32"><th>%s</th>\n' % relationName else: s += '<tr><th>%s</th>' % relationName for x in actionsList: if Colored: s += '<th bgcolor="#FFF79B">%s</th>\n' % (x[0]) else: s += '<th>%s</th\n>' % (x[0]) s += '</tr>\n' for x in actionsList: s += '<tr>' if Colored: s += '<th bgcolor="#FFF79B">%s</th>\n' % (x[0]) else: s += '<th>%s</th>\n' % (x[0]) for y in actionsList: if Colored: if self.relation[x[1]][y[1]] == Max: s += '<td bgcolor="#66ff66"><b>%s</b></td>\n' % symbols[0] elif self.relation[x[1]][y[1]] > Med: s += '<td bgcolor="#ddffdd">%s</td>' % symbols[1] elif self.relation[x[1]][y[1]] == Min: s += '<td bgcolor="#ff6666"><b>%s</b></td\n>' % symbols[4] elif self.relation[x[1]][y[1]] < Med: s += '<td bgcolor="#ffdddd">%s</td>\n' % symbols[3] else: #s += '<td bgcolor="#ffffff">%s</td>\n' % symbols[2] s += '<td class="na">%s</td>\n' % symbols[2] else: if self.relation[x[1]][y[1]] == Max: s += '<td><b>%s</b></td>\n' % symbols[0] elif self.relation[x[1]][y[1]] > Med: s += '<td>%s</td>\n' % symbols[1] elif self.relation[x[1]][y[1]] == Min: s += '<td><b>%s</b></td>\n' % symbols[4] elif self.relation[x[1]][y[1]] < Med: s += '<td>%s</td>\n' % symbols[3] else: s += '<td>%s</td>\n' % symbols[2] s += '</tr>' s += '</table>\n' # legend s += '<span style="font-size: 75%">\n' s += '<table border="1"><tr><th colspan="2"><i>Semantics</i></th></tr>\n' if Colored: s += '<tr><td bgcolor="#66ff66" align="center">%s</td><td>certainly valid</td></tr>\n' % symbols[0] s += '<tr><td bgcolor="#ddffdd" align="center">%s</td><td>valid</td></tr>\n' % symbols[1] s += '<tr><td>%s</td><td>indeterminate</td></tr>\n' % symbols[2] s += '<tr><td bgcolor="#ffdddd" align="center">%s</td><td>invalid</td></tr>\n' % symbols[3] s += '<tr><td bgcolor="#ff6666" align="center">%s</td><td>certainly invalid</td></tr>\n' % symbols[4] s += '</table>\n' else: s += '<tr><td align="center">%s</td><td>certainly valid</td></tr>\n' % symbols[0] s += '<tr><td align="center">%s</td><td>valid</td></tr>\n' % symbols[1] s += '<tr><td align="center">%s</td><td>indeterminate</td></tr>\n' % symbols[2] s += '<tr><td align="center">%s</td><td>invalid</td></tr>\n' % symbols[3] s += '<tr><td align="center">%s</td><td>certainly invalid</td></tr>\n' % symbols[4] s += '</table>\n' s += '</span>\n' # html footer s += '</body>\n' s += '</html>\n' return s
[docs] def showHTMLRelationTable(self,actionsList=None, IntegerValues=False, Colored=True, tableTitle='Valued Adjacency Matrix', relationName='r(x S y)'): """ Launches a browser window with the colored relation table of self. """ import webbrowser fileName = '/tmp/relationMap.html' fo = open(fileName,'w') fo.write(self.htmlRelationTable(actionsSubset=actionsList, isColored=Colored, hasIntegerValues=IntegerValues, tableTitle=tableTitle, relationName=relationName)) fo.close() url = 'file://'+fileName webbrowser.open_new(url)
[docs] def htmlRelationTable(self,tableTitle='Valued Relation Table', relationName='r(x R y)', hasIntegerValues=False, actionsSubset= None, isColored=False): """ renders the relation valuation in actions X actions html table format. """ Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] Max = self.valuationdomain['max'] if actionsSubset == None: actions = self.actions else: actions = actionsSubset s = '' s += '<h1>%s</h1>' % tableTitle s += '<table border="1">' if isColored: s += '<tr bgcolor="#9acd32"><th>%s</th>' % relationName else: s += '<tr><th>%s</th>' % relationName #actions = [x for x in actions] actionsList = [] for x in actions: if isinstance(x,frozenset): try: actionsList += [(actions[x]['shortName'],x)] except: actionsList += [(actions[x]['name'],x)] else: actionsList += [(str(x),str(x))] if actionsSubset == None: actionsList.sort() #print actionsList #actionsList.sort() try: hasIntegerValuation = self.valuationdomain['hasIntegerValuation'] except KeyError: hasIntegerValuation = hasIntegerValues for x in actionsList: if isColored: s += '<th bgcolor="#FFF79B">%s</th>' % (x[0]) else: s += '<th>%s</th>' % (x[0]) s += '</tr>' for x in actionsList: s += '<tr>' if isColored: s += '<th bgcolor="#FFF79B">%s</th>' % (x[0]) else: s += '<th>%s</th>' % (x[0]) for y in actionsList: if hasIntegerValuation: if isColored: if self.relation[x[1]][y[1]] > Med: s += '<td bgcolor="#ddffdd" align="right">%d</td>' % (self.relation[x[1]][y[1]]) elif self.relation[x[1]][y[1]] < Med: s += '<td bgcolor="#ffddff" align="right">%d</td>' % (self.relation[x[1]][y[1]]) else: s += '<td bgcolor="#dddddd" align="right" >%d</td>' % (self.relation[x[1]][y[1]]) else: s += '<td>%d</td>' % (self.relation[x[1]][y[1]]) else: if isColored: if self.relation[x[1]][y[1]] > Med: s += '<td bgcolor="#ddffdd" align="right">%2.2f</td>' % (self.relation[x[1]][y[1]]) elif self.relation[x[1]][y[1]] < Med: s += '<td bgcolor="#ffddff" align="right">%2.2f</td>' % (self.relation[x[1]][y[1]]) else: s += '<td bgcolor="#dddddd" align="right">%2.2f</td>' % (self.relation[x[1]][y[1]]) else: s += '<td>%2.2f</td>' % (self.relation[x[1]][y[1]]) s += '</tr>' s += '</table>' if hasIntegerValuation: s += '<p>Valuation domain: [%d; %+d]</p>' % (Min,Max) else: s += '<p>Valuation domain: [%.2f; %+.2f]</p>' % (Min,Max) return s
[docs] def showdre(self): """ Shows relation in nauty format. """ print('*----- show dre -------------*') actions = [x for x in self.actions] aindex = {} i = 1 print('Actions index:') for x in actions: print(i,': ', str(x)) aindex[x] = i i += 1 Med = self.valuationdomain['med'] relation = self.relation n = len(actions) print('n='+str(n)+' $=1 d g') for x in actions: res = str(aindex[x]) + ': ' for y in actions: if relation[x][y] > Med: res = res + str(aindex[y]) + ' ' res = res + ';' print(res)
[docs] def exportPrincipalImage(self, Reduced=False,\ Colwise=False,\ plotFileName=None,\ Type="png",\ TempDir='.',Comments=False): """ Export as PNG (default) or PDF the principal projection of the valued relation using the three principal eigen vectors. .. warning:: The method, writing and reading temporary files: tempCol.r and rotationCol.csv, resp. tempRow.r and rotationRow.csv, by default in the working directory (./), is hence not safe for multiprocessing programs, unless a temporary dirctory is provided """ if Comments: print('*---- export 3dplot of type %s -----' % (Type)) if TempDir == None: TempDir = '.' import os,time if plotFileName == None: plotFileName = "%s/%s_principalImage" % (TempDir,self.name) if Colwise: plotFileName += "_Colwise" else: plotFileName += "_Rowwise" self.saveCSV('%s/exportTemp' % TempDir) if Colwise: fo = open('%s/tempCol.r' % TempDir,'w') else: fo = open('%s/tempRow.r' % TempDir,'w') fo.write("x = read.csv('%s/exportTemp.csv',row.names=1)\n" % TempDir) if Colwise: fo.write("x = t(x)\n") if Reduced: fo.write("x = (x-colMeans(x))/(sapply(x,sd)*sqrt(length(t(x))))\n") else: fo.write("x = (x-colMeans(x))\n") fo.write("X = as.matrix(x)\n") fo.write("A = X %*% t(X)\n") fo.write("E = eigen(A, symmetric=TRUE)\n") fo.write("P = E$values * t(E$vectors)\n") if Colwise: fo.write("write.csv(t(P),'%s/rotationCol.csv',row.names=F)\n" % TempDir) else: fo.write("write.csv(t(P),'%s/rotationRow.csv',row.names=F)\n" % TempDir) if Type == None: # no principal image is required fo.close() else: fo.write("valprop = E$values/sum(E$values)\n") fo.write("pcaRes = list(x=X,eig=E,a=A,P=P,val=valprop)\n") fo.write("val = pcaRes$val\n") fo.write("nval = length(val)\n") if Type == "png": fo.write('png("%s/%s.png",width=480,height=480,bg="cornsilk")\n'\ % (TempDir,plotFileName) ) elif Type == "jpeg": fo.write('jpeg("%s/%s.jpg",width=480,height=480,bg="cornsilk")\n'\ % (TempDir,plotFileName) ) elif Type == "xfig": fo.write('xfig("%s/%s.fig",width=480,height=480,bg="cornsilk")\n'\ % (TempDir,plotFileName) ) elif Type == "pdf": fo.write('pdf("%s/%s.pdf",width=6,height=6,bg="cornsilk",title="PCA of relation valuation")\n'\ % (TempDir,plotFileName) ) else: print('Error: Plotting device %s not defined !' % (Type)) return fo.write("par(mfrow=c(2,2))\n") fo.write("a1 = 1\n") fo.write("a2 = 2\n") fo.write("a3 = 3\n") fo.write('plot(pcaRes$P[a1,],pcaRes$P[a2,],"n",xlab=paste("axis 1:",val[a1]*100,"%"),ylab=paste("axis 2:",val[a2]*100,"%"),asp=1)\n') fo.write("text(pcaRes$P[a1,],pcaRes$P[a2,],rownames(pcaRes$x),cex=0.75)\n") fo.write('abline(h=0,lty=2,col="gray")\n') fo.write('abline(v=0,lty=2,col="gray")\n') fo.write('plot(pcaRes$P[a2,],pcaRes$P[a3,],"n",xlab=paste("axis 2:",val[a2]*100,"%"),ylab=paste("axis 3:",val[a3]*100,"%"),asp=1)\n') fo.write('text(pcaRes$P[a2,],pcaRes$P[a3,],rownames(pcaRes$x),cex=0.75)\n') fo.write('abline(h=0,lty=2,col="gray")\n') fo.write('abline(v=0,lty=2,col="gray")\n') fo.write('plot(pcaRes$P[a1,],pcaRes$P[a3,],"n",xlab=paste("axis 1:",val[a1]*100,"%"),ylab=paste("axis 3:",val[a3]*100,"%"),asp=1)\n') fo.write('text(pcaRes$P[a1,],pcaRes$P[a3,],rownames(pcaRes$x),cex=0.75)\n') fo.write('abline(h=0,v=0,lty=2,col="gray")\n') fo.write('barplot(val[a1:nval]*100,names.arg=a1:nval,main="Axis inertia (in %)",col="orangered")\n') fo.write('dev.off()\n') fo.close() if Comments: if Colwise: os.system('(cd %s;env R -q --vanilla --verbose < tempCol.r 2>&1)' % TempDir) else: os.system('(cd %s;env R -q --vanilla --verbose < tempRow.r 2>&1)' % TempDir ) else: if Colwise: os.system('(cd %s;env R -q --vanilla < tempCol.r > /dev/null 2> /dev/null)' % TempDir) else: os.system('(cd %s;env R -q --vanilla < tempRow.r > /dev/null 2> /dev/null)' % TempDir) time.sleep(3) if Type != None and Comments: print('See %/%s.%s ! ' % (TempDir,plotFileName,Type))
[docs] def exportGraphViz(self,fileName=None,actionsSubset=None,\ bestChoice=set(),worstChoice=set(),\ noSilent=True,graphType='png',graphSize='7,7', relation=None): """ export GraphViz dot file for graph drawing filtering. """ import os if noSilent: print('*---- exporting a dot file dor GraphViz tools ---------*') if actionsSubset == None: actionkeys = [x for x in self.actions] else: actionkeys = [x for x in actionsSubset] n = len(actionkeys) if relation == None: relation = self.relation Med = self.valuationdomain['med'] i = 0 if fileName == None: name = self.name else: name = fileName dotName = name+'.dot' if noSilent: print('Exporting to '+dotName) if bestChoice != set(): rankBestString = '{rank=max; ' if worstChoice != set(): rankWorstString = '{rank=min; ' fo = open(dotName,'w') fo.write('digraph G {\n') fo.write('graph [ bgcolor = cornsilk, fontname = "Helvetica-Oblique",\n fontsize = 12,\n label = "') fo.write('\\nRubis Python Server (graphviz), R. Bisdorff, 2008", size="') fo.write(graphSize),fo.write('"];\n') for i in range(n): try: nodeName = self.actions[actionkeys[i]]['shortName'] except: try: nodeName = self.actions[actionskeys[i]]['name'] except: nodeName = str(actionkeys[i]) node = 'n'+str(i+1)+' [shape = "circle", label = "' +nodeName+'"' if actionkeys[i] in bestChoice: node += ', style = "filled", color = gold];\n' rankBestString += 'n'+str(i+1)+' ' elif actionkeys[i] in worstChoice: node += ', style = "filled", color = lightblue];\n' rankWorstString += 'n'+str(i+1)+' ' else: node += '];\n' fo.write(node) if bestChoice != set(): rankBestString += '}\n' if worstChoice != set(): rankWorstString += '}\n' ## for i in range(n): ## edge = 'n'+str(i+1) ## for j in range(n): ## if i != j and relation[actions[i]][actions[j]] > Med: ## edge0 = edge+'-> n'+str(j+1)+';\n' ## fo.write(edge0) ## j += 1 ## i += 1 for i in range(n): for j in range(i+1, n): edge = 'n'+str(i+1) if relation[actionkeys[i]][actionkeys[j]] > Med and relation[actionkeys[j]][actionkeys[i]] > Med: edge0 = edge+'-> n'+str(j+1)+' [dir=both,style="setlinewidth(2)",color=black, arrowhead=normal, arrowtail=normal] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] > Med and relation[actionkeys[j]][actionkeys[i]] == Med: edge0 = edge+'-> n'+str(j+1)+' [dir=both, color=black, arrowhead=normal, arrowtail=empty] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] == Med and relation[actionkeys[j]][actionkeys[i]] > Med: edge0 = edge+'-> n'+str(j+1)+' [dir=both, color=black, arrowtail=normal, arrowhead=empty] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] == Med and relation[actionkeys[j]][actionkeys[i]] == Med: edge0 = edge+'-> n'+str(j+1)+' [dir=both, color=grey, arrowhead=empty, arrowtail=empty] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] > Med and relation[actionkeys[j]][actionkeys[i]] < Med: edge0 = edge+'-> n'+str(j+1)+' [dir=forward, color=black] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] == Med and relation[actionkeys[j]][actionkeys[i]] < Med: edge0 = edge+'-> n'+str(j+1)+' [dir=forward, color=grey, arrowhead=empty] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] < Med and relation[actionkeys[j]][actionkeys[i]] > Med: edge0 = edge+'-> n'+str(j+1)+' [dir=back, color=black] ;\n' fo.write(edge0) elif relation[actionkeys[i]][actionkeys[j]] < Med and relation[actionkeys[j]][actionkeys[i]] == Med: edge0 = edge+'-> n'+str(j+1)+' [dir=back, color=grey, arrowtail=empty] ;\n' fo.write(edge0) if bestChoice != set(): fo.write(rankBestString) if worstChoice != set(): fo.write(rankWorstString) fo.write('}\n') fo.close() if type(self) == CirculantDigraph: commandString = 'circo -T'+graphType+' '+dotName+' -o '+name+'.' + graphType elif type(self) == RandomTree: commandString = 'neato -T'+graphType+' '+dotName+' -o '+name+'.' + graphType else: commandString = 'dot -Grankdir=BT -T'+graphType+' ' +dotName+' -o '+name+'.'+graphType #commandString = 'dot -T'+graphType+' ' +dotName+' -o '+name+'.'+graphType if noSilent: print(commandString) try: os.system(commandString) except: if noSilent: print('graphViz tools not avalaible! Please check installation.')
[docs] def exportD3(self, fileName="index", Comments=True): """ This function was designed and implemented by Gary Cornelius, 2014 for his bachelor thesis at the University of Luxembourg. The thesis document with more explanations can be found `here <http://leopold-loewenheim.uni.lu/Digraph3/literature/>`_ . *Parameters*: * fileName, name of the generated html file, default = None (graph name as defined in python); * Comments, True = default; The idea of the project was to find a way that allows you to easily get details about certain nodes or edges of a directed graph in a dynamic format. Therefore this function allows you to export a html file together with all the needed libraries, including the D3 Library which we use for graph generation and the physics between nodes, which attracts or pushes nodes away from each other. Features of our graph include i.e. : * A way to only inspect a node and it's neighbours * Dynamic draging and freezing of the graph * Export of a newly created general graph You can find the list of fututres in the Section below which is arranged according to the graph type. *If the graph is an outrankingdigraphs*: * Nodes can be dragged and only the name and comment can be edited. * Edges can be inspected but not edited for this purpose a special json array containing all possible pairwiseComparisions is generated. *If the graph is a general graph*: * Nodes can be dragged, added, removed and edited. * Edges can be added, removed, inverted and edited. But edges cannot be inspected. * The pairwiseComparisions key leads to an empty array {}. In both cases, undefined edges can be hidden and reappear after a simple reload.(right click - reload) *The generated files*: * d3.v3.js, contains the D3 Data-driven Documents source code, containing one small addition that we made in order to be able to easyly import links with a different formatself. * digraph3lib.js, contains our library. This file contains everything that we need from import of an XMCDA2 file, visualization of the graph to export of the changed graph. * d3export.json, usually named after the python graph name followed by a ticket number if the file is already present. It is the JSON file that is exported with the format "{"xmcda2": "some xml","pairwiseComparisions":"{"a01": "some html",...}"}. *Example 1*: #. python3 session: >>> from digraphs import RandomValuationDigraph >>> dg = RandomValuationDigraph(order=5,Normalized=True) >>> dg.exportD3() or >> dg.showInteractiveGraph() #. index.html: * Main Screen: .. image:: randomvaluation_d3_main.png * Inspect function: .. image:: randomvaluation_d3_inspect.png .. note:: If you want to use the automatic load in Chrome, try using the command: "python -m SimpleHTTPServer" and then access the index.html via "http://0.0.0.0:8000/index.html". In order to load the CSS an active internet connection is needed! """ import os import json import urllib import htmlmodel,json if Comments: print('*---- exporting all needed files ---------*') if fileName == "index": fileName = self.name file=fileName+".html" dst_dir=os.getcwd() basename = os.path.basename(file) head, tail = os.path.splitext(basename) dst_file = os.path.join(dst_dir, basename) # rename if necessary count = 0 print(dst_file) while os.path.exists(dst_file): count += 1 dst_file = os.path.join(dst_dir, '%s-%d%s' % (head, count, tail)) actionkeys = [x for x in self.actions] n = len(actionkeys) relation = self.relation Med = self.valuationdomain['med'] pageName="" fw = open("digraph3lib.js",'w') fw.write(htmlmodel.javascript()) fw.close() if Comments: print("File: digraph3lib.js saved!") fw = open("d3.v3.js",'w') fw.write(htmlmodel.d3export()) fw.close() if Comments: print("File: d3.v3.js saved!") pairwise={} try: for x in self.actions: pairwise[x]={} for x in actionkeys: for y in actionkeys: if(not(x == y)): pairwise[x][y] = str(self.showPairwiseComparison(x,y,isReturningHTML=True)) except: pairwise={} d3export={} if(pairwise): temp = "outranking_"+fileName self.saveXMCDA2(fileName=temp+"-"+str(count)) else: temp = "general_"+fileName self.saveXMCDA2(fileName=temp+"-"+str(count)) with open(temp+"-"+str(count)+".xmcda2","r") as myFile: data=myFile.read().replace("\n","") try: os.remove(temp+"-"+str(count)+".xmcda2") except OSError: pass d3export["xmcda2"]= str(data) d3export["pairwiseComparisions"] = json.dumps(pairwise) if(count==0): fw = open(temp+".json","w") if Comments: print("File: "+temp+".json saved!") else: fw = open(temp+"-"+str(count)+".json","w") if Comments: print("File:"+temp+"-"+str(count)+".json saved!") fw.write(json.dumps(d3export)) fw.close() if(count==0): fw = open(fileName+".html","w") fw.write(htmlmodel.htmlmodel(jsonName=temp+".json")) pageName=fileName+".html" if Comments: print("File: "+fileName+".html generated!") else: fw = open(fileName+"-"+str(count)+".html",'w') fw.write(htmlmodel.htmlmodel(jsonName=temp+"-"+str(count)+".json")) pageName=fileName+"-"+str(count)+".html" if Comments: print("File: "+fileName+"-"+str(count)+".html generated!") fw.close() if Comments: print('*---- export done ---------*') return pageName
[docs] def showInteractiveGraph(self): ''' Save the graph and all needed files for the visualization of an interactive graph generated by the exportD3() function. For best experience make sure to use Firefox, because other browser restrict the loading of local files. ''' import os,webbrowser newTab=2 url = "file://"+os.getcwd()+"/%s" % self.exportD3() webbrowser=webbrowser.get("firefox") webbrowser.open(url,new=newTab)
[docs] def savedre(self,name='temp'): """ save digraph in nauty format. """ print('*----- saving digraph in nauty dre format -------------*') actions = [x for x in self.actions] Name = name+'.dre' aindex = {} i = 1 print('Actions index:') for x in actions: print(i,': ', str(x)) aindex[x] = i i += 1 Med = self.valuationdomain['med'] relation = self.relation n = len(actions) fo = open(Name,'w') fo.write('n='+str(n)+' $=1 d g\n') for x in actions: res = str(aindex[x]) + ': ' for y in actions: if relation[x][y] > Med: res = res + str(aindex[y]) + ' ' res = res + ';\n' fo.write(res) fo.close() self.aindex = aindex.copy()
[docs] def saveXML(self,name='temp',category='general',subcategory='general',author='digraphs Module (RB)',reference='saved from Python'): """ save digraph in XML format. """ print('*----- saving digraph in XML format -------------*') actions = [x for x in self.actions] nameExt = name+'.xml' fo = open(nameExt,'w') fo.write('<?xml version="1.0" encoding="UTF-8"?>\n') fo.write('<?xml-stylesheet type="text/xsl" href="digraphs.xsl"?>\n') fo.write('<!DOCTYPE digraph SYSTEM "digraphs.dtd">\n') fo.write('<digraph ') fo.write('category="' + category+'" subcategory="'+subcategory+'">\n') fo.write('<header>\n') fo.write('<name>') fo.write(nameExt) fo.write('</name>\n') fo.write('<author>') fo.write(author) fo.write('</author>\n') fo.write('<reference>') fo.write(reference) fo.write('</reference>\n') fo.write('</header>') actions = self.actions fo.write('<nodes>\n') for x in actions: fo.write('<node>') fo.write(str(x)) fo.write('</node>\n') fo.write('</nodes>\n') Max = self.valuationdomain['max'] Min = self.valuationdomain['min'] fo.write('<valuationdomain>\n') fo.write('<min>') fo.write(str(Min)) fo.write('</min>\n') fo.write('<max>') fo.write(str(Max)) fo.write('</max>\n') fo.write('</valuationdomain>\n') fo.write('<relation>\n') relation = self.relation for x in actions: for y in actions: fo.write('<arc>\n') fo.write('<i>') fo.write(str(x)) fo.write('</i>\n') fo.write('<t>') fo.write(str(y)) fo.write('</t>\n') fo.write('<v>') fo.write(str(relation[x][y])) fo.write('</v>\n') fo.write('</arc>\n') fo.write('</relation>\n') fo.write('</digraph>\n') fo.close() print('File: ' + nameExt + ' saved !')
[docs] def saveXMCDA(self,fileName='temp',relationName='R',category='random',subcategory='valued',author='digraphs Module (RB)',reference='saved from Python',valuationType='standard',servingD3=False): """ save digraph in XMCDA format. """ print('*----- saving digraph in XML format -------------*') actions = [x for x in self.actions] nameExt = fileName+'.xmcda' fo = open(nameExt,'w') fo.write('<?xml version="1.0" encoding="UTF-8"?>\n') if servingD3: fo.write('<!-- ?xml-stylesheet type="text/xsl" href="xmcdaDefault.xsl"? -->\n') else: fo.write('<?xml-stylesheet type="text/xsl" href="xmcdaDefault.xsl"?>\n') fo.write(str('<xmcda:XMCDA xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.decision-deck.org/2008/UMCDA-ML-1.0 umcda-ml-1.0.xsd" xmlns:xmcda="http://www.decision-deck.org/2008/UMCDA-ML-1.0">\n')) # write description fo.write('<caseReference>\n') fo.write('<title>Valued Digraph in XMCDA format</title>\n') fo.write('<id>%s</id>\n' % (fileName) ) fo.write('<name>%s</name>\n' % (self.name) ) fo.write('<type>root</type>\n') fo.write('<user>%s</user>\n' % (author) ) fo.write('<version>%s</version>\n' % (reference) ) fo.write('</caseReference>\n') # write nodes actionsList = [x for x in self.actions] actionsList.sort() na = len(actionsList) actions = self.actions fo.write('<alternatives>\n') fo.write('<description>\n') fo.write('<title>%s</title>\n' % ('List of Alternatives')) fo.write('<type>%s</type>\n' % ('alternatives')) fo.write('<comment>Potential decision actions.</comment>\n') fo.write('</description>\n') for i in range(na): fo.write('<alternative id="%s">\n' % (actionsList[i])) fo.write('<description>\n') fo.write('<name>') try: fo.write(str(actions[actionsList[i]]['name'])) except: fo.write('nameless') fo.write('</name>\n') fo.write('<comment>') try: fo.write(str(actions[actionsList[i]]['comment'])) except: fo.write('No comment') fo.write('</comment>\n') fo.write('</description>\n') fo.write('<alternativeType>potential</alternativeType>\n') fo.write('</alternative>\n') fo.write('</alternatives>\n') # write valued binary Relation fo.write('<relationOnAlternatives>\n') fo.write('<description>\n') fo.write('<title>%s</title>\n' % ('Valued Binary Relation')) fo.write('<name>%s</name>\n' % (relationName) ) fo.write('<type>%s</type>\n' % ('valuedBinaryRelation')) fo.write('<comment>%s %s Digraph</comment>\n' % (category,subcategory) ) fo.write('</description>\n') fo.write('<valuationDomain>\n') fo.write('<description>\n') fo.write('<subTitle>%s</subTitle>\n' % ('Valuation Domain')) fo.write('</description>\n') fo.write('<valuationType>%s</valuationType>\n' % (valuationType) ) Max = self.valuationdomain['max'] Min = self.valuationdomain['min'] fo.write('<minimum><real>%2.2f</real></minimum>\n' % (Min)) fo.write('<maximum><real>%2.2f</real></maximum>\n' % (Max)) fo.write('</valuationDomain>\n') fo.write('<arcs>\n') fo.write('<description>\n') fo.write('<subTitle>%s</subTitle>\n' % ('Valued Adjacency Table')) try: category = self.category subcategory = self.subcategory except: pass fo.write('<comment>%s %s Digraph</comment>\n' % (category,subcategory) ) fo.write('</description>\n') relation = self.relation for x in actions: for y in actions: fo.write('<arc>\n') fo.write('<from><alternativeID>') fo.write(str(x)) fo.write('</alternativeID></from>\n') fo.write('<to><alternativeID>') fo.write(str(y)) fo.write('</alternativeID></to>\n') fo.write('<value><real>%2.2f' % (relation[x][y]) ) fo.write('</real></value>\n') fo.write('</arc>\n') fo.write('</arcs>\n') fo.write('</relationOnAlternatives>\n') fo.write('</xmcda:XMCDA>\n') fo.close() print('File: ' + nameExt + ' saved !')
[docs] def saveXMCDA2(self,fileName='temp',fileExt='xmcda2',Comments=True,relationName='R',relationType='binary',category='random',subcategory='valued',author='digraphs Module (RB)',reference='saved from Python',valuationType='standard',digits=2,servingD3=False): """ save digraph in XMCDA format. """ if Comments: print('*----- saving digraph in XML format -------------*') actions = [x for x in self.actions] nameExt = fileName+"."+fileExt fo = open(nameExt,'w') fo.write('<?xml version="1.0" encoding="UTF-8"?>\n') if servingD3: fo.write('<!-- ?xml-stylesheet type="text/xsl" href="xmcda2Rubis.xsl"? -->\n') else: fo.write('<?xml-stylesheet type="text/xsl" href="xmcdaXSL.xsl"?>\n') fo.write(str('<xmcda:XMCDA xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.decision-deck.org/2009/UMCDA-2.0.0 file:../XMCDA-2.0.0.xsd" xmlns:xmcda="http://www.decision-deck.org/2009/XMCDA-2.0.0">\n')) # write description fo.write('<projectReference id="%s" name="%s">\n' % (fileName,self.name)) fo.write('<title>Stored Digraph in XMCDA-2.0 format</title>\n') #fo.write('<id>%s</id>\n' % (fileName) ) #fo.write('<name>%s</name>\n' % (self.name) ) #fo.write('<type>root</type>\n') fo.write('<user>%s</user>\n' % (author) ) fo.write('<version>%s</version>\n' % (reference) ) fo.write('</projectReference>\n') # write nodes actionsList = [x for x in self.actions] actionsList.sort() na = len(actionsList) actions = self.actions fo.write('<alternatives mcdaConcept="Digraph nodes">\n') fo.write('<description>\n') fo.write('<title>%s</title>\n' % ('Nodes of the digraph')) #fo.write('<type>%s</type>\n' % ('alternatives')) fo.write('<comment>Set of nodes of the digraph.</comment>\n') fo.write('</description>\n') for i in range(na): try: alternativeName = str(actions[actionsList[i]]['name']) except: alternativeName = 'nameless' fo.write('<alternative id="%s" name="%s">\n' % (actionsList[i],alternativeName)) fo.write('<description>\n') fo.write('<comment>') try: fo.write(str(actions[actionsList[i]]['comment'])) except: fo.write('No comment') fo.write('</comment>\n') fo.write('</description>\n') fo.write('<type>real</type>\n') fo.write('<active>true</active>\n') fo.write('<reference>false</reference>\n') fo.write('</alternative>\n') fo.write('</alternatives>\n') # write valued binary Relation fo.write('<alternativesComparisons id="1" name="%s">\n' % (relationName)) fo.write('<description>\n') fo.write('<title>%s</title>\n' % ('Randomly Valued Binary Relation')) #fo.write('<name>%s</name>\n' % (relationName) ) #fo.write('<type>%s</type>\n' % ('valuedBinaryRelation')) fo.write('<comment>%s %s Digraph</comment>\n' % (category,subcategory) ) fo.write('</description>\n') fo.write('<valuation name="valuationDomain">\n') fo.write('<description>\n') fo.write('<subTitle>%s</subTitle>\n' % ('Valuation Domain')) fo.write('</description>\n') fo.write('<quantitative>') Max = self.valuationdomain['max'] Min = self.valuationdomain['min'] if valuationType == 'integer': fo.write('<minimum><integer>%d</integer></minimum>\n' % (Min)) fo.write('<maximum><integer>%d</integer></maximum>\n' % (Max)) else: formatString = '%%2.%df' % (digits) fo.write('<minimum><real>') fo.write(formatString % (Min)) fo.write('</real></minimum>\n') fo.write('<maximum><real>') fo.write(formatString % (Max)) fo.write('</real></maximum>\n') fo.write('</quantitative>\n') fo.write('</valuation>\n') fo.write('<comparisonType>%s</comparisonType>\n' % (relationName)) fo.write('<pairs>\n') fo.write('<description>\n') fo.write('<subTitle>%s</subTitle>\n' % ('Valued Adjacency Table')) try: category = self.category subcategory = self.subcategory except: pass fo.write('<comment>%s %s Digraph</comment>\n' % (category,subcategory) ) fo.write('</description>\n') relation = self.relation for x in actions: for y in actions: fo.write('<pair>\n') fo.write('<initial><alternativeID>') fo.write(str(x)) fo.write('</alternativeID></initial>\n') fo.write('<terminal><alternativeID>') fo.write(str(y)) fo.write('</alternativeID></terminal>\n') if valuationType == 'bipolar': formatString = '%%+2.%df' % (digits) else: formatString = '%%2.%df' % (digits) fo.write('<value><real>') fo.write(formatString % (relation[x][y]) ) fo.write('</real></value>\n') fo.write('</pair>\n') fo.write('</pairs>\n') fo.write('</alternativesComparisons>\n') fo.write('</xmcda:XMCDA>\n') fo.close() if Comments: print('File: ' + nameExt + ' saved !')
[docs] def computeDensities(self,choice): """ parameter: choice in self renders the four densitiy parameters: arc density, double arc density, single arc density, absence arc density. """ actions = set(choice) relation = self.relation Med = self.valuationdomain['med'] order = float(len(actions)) d = 0.0 dd = 0.0 sd = 0.0 ad = 0.0 for x in actions: for y in actions: if x != y: if relation[x][y] > Med: d += 1.0 if relation[x][y] > Med and relation[y][x] > Med: dd += 1.0 if relation[x][y] > Med and relation[y][x] <= Med: sd += 1.0 if relation[x][y] <= Med and relation[y][x] <= Med: ad += 1.0 d = d / (order*(order-1)) dd / (order*(order-1)) sd = (2*sd) / (order*(order-1)) ad = ad / (order*(order-1)) return d,dd,sd,ad
[docs] def computeCutLevelDensities(self,choice,level): """ parameter: choice in self, robustness level renders three robust densitiy parameters: robust double arc density, robust single arc density, robust absence arc densitiy. """ actions = set(choice) relation = self.relation Min = self.valuationdomain['min'] Med = self.valuationdomain['med'] Max = self.valuationdomain['max'] negLevel = Max - level + Min order = float(len(actions)) rdd = 0.0 rsd = 0.0 rad = 0.0 if level < Med or level >= Max: print('Error: robustness level too low or too high !!!') else: for x in actions: for y in actions: if x != y: if relation[x][y] > level and relation[y][x] > level: rdd += 1.0 if relation[x][y] > level: if relation[y][x] < negLevel: rsd += 1.0 if relation[x][y] < negLevel and relation[y][x] < negLevel: rad += 1.0 rdd = rdd / (order*(order-1)) rsd = (2*rsd) / (order*(order-1)) rad = rad / (order*(order-1)) density = {} density['double'] = rdd density['single'] = rsd density['absence'] = rad return density
[docs] def computeAllDensities(self,choice=None): """ parameter: choice in self renders six densitiy parameters: arc density, double arc density, single arc density, strict single arc density, absence arc density, strict absence arc densitiy. """ if choice != None: actions = set(choice) else: actions = self.actions relation = self.relation Med = self.valuationdomain['med'] order = float(len(actions)) d = 0.0 dd = 0.0 sd = 0.0 ssd = 0.0 ad = 0.0 asd = 0.0 for x in actions: for y in actions: if x != y: if relation[x][y] > Med: d += 1.0 if relation[x][y] > Med and relation[y][x] > Med: dd += 1.0 if relation[x][y] > Med: if relation[y][x] < Med: ssd += 1.0 sd += 1.0 elif relation[y][x] == Med: sd += 1.0 if relation[x][y] <= Med and relation[y][x] <= Med: ad += 1.0 if relation[x][y] < Med and relation[y][x] < Med: asd += 1.0 d = d / float(order*(order-1)) dd = dd / float(order*(order-1)) sd = (2*sd) / float(order*(order-1)) ssd = (2*ssd) / float(order*(order-1)) ad = ad / float(order*(order-1)) asd = asd / float(order*(order-1)) density = {} density['arc'] = d density['double'] = dd density['single'] = sd density['strictSingle'] = ssd density['absence'] = ad density['strictAbsence'] = asd return density
[docs] def computeValuationLevels(self,choice=None, Debug=False): """ renders the symmetric closure of the apparent valuations levels of self in an increasingly ordered list. If parameter choice is given, the computation is limited to the actions of the choice. """ Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] Min = self.valuationdomain['min'] if choice == None: actions = [x for x in self.actions] else: actions = [x for x in choice] relation = self.relation levels = set([Max,Min]) for x in actions: for y in actions: levels.add(relation[x][y]) levels.add(Max - relation[x][y] + Min) ## if Debug: ## print levels levelsList = list(levels) levelsList.sort() if Debug: print('levelsList', levelsList) return levelsList
[docs] def computePrudentBetaLevel(self, Debug=False): """ computes alpha, ie the lowest valuation level, for which the bipolarly polarised digraph doesn't contain a chordless circuit. """ Med = self.valuationdomain['med'] valuationLevels= self.computeValuationLevels(Debug=Debug) if Debug: print('number of levels; %d' % len(valuationLevels)) valuationLevels.reverse() for i in range(len([x for x in valuationLevels if x > Med])): level = valuationLevels[i+1] if Debug: print('checking level: ', level) gp = PolarisedDigraph(self,level=level) if len(gp.computeChordlessCircuits()) > 0: if Debug: gp.showChordlessCircuits() print('prudent order level = %s (med = %.2f)' % (str(valuationLevels[i-1]),Med)) self.prudentBetaLevel = valuationLevels[i] return self.prudentBetaLevel self.prudentBetaLevel = Med if Debug: ## self.computeChordlessCircuits() ## self.showChordlessCircuits() print('prudent order level = %s = med' % str(Med)) return Med
[docs] def computeValuationPercentiles(self,choice, percentages, withValues=False): """ Parameters: choice and list of percentages. renders a series of quantiles of the characteristics valuation of the arcs in the digraph. """ relation = self.relation vx = [] for x in choice: for y in choice: if x != y: vx.append(relation[x][y]) vx.sort() if withValues: print('values ', vx) nv = len(vx) percentile = {} for q in percentages: kq = q*nv//100 r = (nv*q)% 100 if q == 0: percentile[q] = vx[0] elif q == 100: percentile[q] = vx[nv-1] else: percentile[q] = vx[kq-1] + (Decimal(str(r))/Decimal('100.0')) * (vx[kq]-vx[kq-1]) return percentile
[docs] def computeValuationPercentages(self,choice,percentiles,withValues=False): """ Parameters: choice and list of percentages. renders a series of quantiles of the characteristics valuation of the arcs in the digraph. """ relation = self.relation vx = [] for x in choice: for y in choice: if x != y: vx.append(relation[x][y]) vx.sort() nv = len(vx) if withValues: print('values ', vx) np = len(percentiles) rv = [0.0 for i in range(np)] for val in vx: for i in range(np): if percentiles[i] > val: rv[i] += 1.0 percentages = {} for i in range(np): percentages[percentiles[i]] = rv[i]/float(nv) return percentages
[docs] def computeAverageValuation(self): """ Computes the bipolar average correlation between self and the crisp complete digraph of same order of the irreflexive and determined arcs of the digraph """ Med = self.valuationdomain['med'] relation = self.relation averageValuation = Decimal('0.0') determined = Decimal('0.0') #actionsList = [x for x in self.actions] nbDeterm = 0 for x,rx in relation.items(): for y,rxy in rx.items(): if x != y: if rxy != Med: nbDeterm += 1 averageValuation += rxy determined += abs(rxy) return averageValuation / determined
[docs] def computeDeterminateness(self): """ Computes the Kendalll distance in % of self with the all median valued (indeterminate) digraph. """ Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] relation = self.relation #actions = self.actions order = self.order deter = Decimal('0.0') for x,rx in relation.items(): for y,rxy in rx.items(): if x != y: #print(relation[x][y], Med, relation[x][y] - Med) deter += abs(rxy - Med) #print(deter) #deter = (deter /Decimal(str((order * (order-1))))) * (Max - Med) deter = ( Decimal(str(deter)) / Decimal(str((order * (order-1)))) ) return deter/(Decimal(str(Max-Med)))*Decimal('100')
[docs] def showStatistics(self): """ Computes digraph statistics like order, size and arc-density. """ #import array print('*----- general statistics -------------*') nbrcomp = len(self.components()) nbrstrcomp = len(self.strongComponents()) actions = [x for x in self.actions] relation = self.relation order = len(actions) size,undeterm,arcDensity = self.sizeSubGraph(actions) self.size = size self.undeterm = undeterm density = self.computeAllDensities(actions) self.arcDensity = density['arc'] outDegrees = self.outDegreesDistribution() inDegrees = self.inDegreesDistribution() symDegrees = self.symDegreesDistribution() nbDepths = self.neighbourhoodDepthDistribution() nb = len(nbDepths) meanLength = 0.0 for i in range(nb): meanLength += i * nbDepths[i] if nbDepths[nb-1] != 0: meanLength = 'infinity' else: meanLength = float(meanLength/order) self.meanNeighbourhoodDepth = meanLength self.digraphDiameter = self.diameter() self.agglomerationCoefficient,self.meanAgglomerationCoefficient = self.agglomerationDistribution() # Outranking determinateness Max = self.valuationdomain['max'] Med = self.valuationdomain['med'] deter = Decimal('0.0') for x,rx in relation.items(): for y,rxy in rx.items(): if x != y: # print(relation[x][y], Med) deter += abs(rxy - Med) deter /= order * (order-1) * (Max - Med) # output results print('for digraph : <' + str(self.name) + '.py>') print('order : ', self.order, 'nodes') print('size : ', self.size, 'arcs') print('# undetermined : ', self.undeterm, 'arcs') print('determinateness : %.2f' % (deter)) print("arc density : %.2f" % (density['arc'])) print("double arc density : %.2f" % (density['double'])) print("single arc density : %.2f" % (density['single'])) print("absence density : %.2f" % (density['absence'])) print("strict single arc density: %.2f" % (density['strictSingle'])) print("strict absence density : %.2f" % (density['strictAbsence'])) print('# components : ', nbrcomp) print('# strong components : ', nbrstrcomp) print('transitivity degree : %.2f' % (self.computeTransitivityDegree())) print(' : ', list(range(len(outDegrees)))) print('outdegrees distribution : ', list(outDegrees)) print('indegrees distribution : ', list(inDegrees)) print('mean outdegree : %.2f' % (self.computeMeanOutDegree())) print('mean indegree : %.2f' % (self.computeMeanInDegree())) print(' : ', list(range(len(symDegrees)))) print('symmetric degrees dist. : ', list(symDegrees)) print('mean symmetric degree : %.2f' % (self.computeMeanSymDegree())) outgini = self.computeConcentrationIndex(list(range(len(outDegrees))),list(outDegrees)) ingini = self.computeConcentrationIndex(list(range(len(inDegrees))),list(inDegrees)) symgini = self.computeConcentrationIndex(list(range(len(symDegrees))),list(symDegrees)) print('outdegrees concentration index : %.4f' % (outgini)) print('indegrees concentration index : %.4f' % (ingini)) print('symdegrees concentration index : %.4f' % (symgini)) listindex = list(range(order)) listindex.append('inf') print(' : ', listindex) print('neighbourhood depths distribution: ', list(nbDepths)) if meanLength != 'infinity': print("mean neighbourhood depth : %.2f " % (meanLength)) else: print('mean neighbourhood length : ', meanLength) print('digraph diameter : ', self.digraphDiameter) print('agglomeration distribution : ') for i in range(order): print(actions[i], end=' ') print(": %.2f" % (self.agglomerationCoefficient[i])) print("agglomeration coefficient : %.2f" % (self.meanAgglomerationCoefficient))
[docs] def meanLength(self,Oriented=False): """ Renders the (by default non-oriented) mean neighbourhoor depth of self. !!! self.order must be set previously !!! """ nbDepths = self.neighbourhoodDepthDistribution(Oriented) nb = len(nbDepths) meanLength = 0.0 for i in range(nb): meanLength += i * nbDepths[i] if nbDepths[nb-1] != 0: meanLength = 'infinity' else: meanLength = meanLength/float(self.order) return meanLength
[docs] def meanDegree(self): """ Renders the mean degree of self. !!! self.size must be set previously !!! """ order = len(self.actions) outDegrees = self.outDegreesDistribution() inDegrees = self.inDegreesDistribution() degrees = [] nd = len(outDegrees) meanDegree = 0.0 for i in range(nd): degrees.append(outDegrees[i]+inDegrees[i]) meanDegree += i * (max(outDegrees[i],inDegrees[i])) if self.size == 0: meanDegree = 0 else: meanDegree = meanDegree/float(2 * self.order) return meanDegree
[docs] def computeMeanOutDegree(self): """ Renders the mean degree of self. !!! self.size must be set previously !!! """ order = len(self.actions) outDegrees = self.outDegreesDistribution() nd = len(outDegrees) meanOutDegree = 0.0 for i in range(nd): meanOutDegree += i * outDegrees[i] if self.size == 0: meanOutDegree = 0 else: meanOutDegree = meanOutDegree/float(self.order) return meanOutDegree
[docs] def computeMeanInDegree(self): """ Renders the mean indegree of self. !!! self.size must be set previously !!! """ order = len(self.actions) inDegrees = self.inDegreesDistribution() nd = len(inDegrees) meanInDegree = 0.0 for i in range(nd): meanInDegree += i * inDegrees[i] if self.size == 0: meanInDegree = 0 else: meanInDegree = meanInDegree/self.order return meanInDegree
[docs] def computeMedianOutDegree(self): """ Renders the median outdegree of self. !!! self.size must be set previously !!! """ order = len(self.actions) outDegrees = self.outDegreesDistribution() nd = len(outDegrees) outDegreesList = [] for d in range(nd): for x in range(outDegrees[d]): outDegreesList.append(d) outDegreesList.sort() #print 'outdegrees sorted', outDegreesList ndl = len(outDegreesList) if ndl % 2 == 0: medpos = ndl//2 medianOutDegree = outDegreesList[medpos] else: medpos0 = ndl//2 medpos1 = (ndl + 1)//2 medianOutDegree = (outDegreesList[medpos0] + outDegreesList[medpos1])/2 return medianOutDegree
[docs] def computeMedianSymDegree(self): """ Renders the median symmetric degree of self. !!! self.size must be set previously !!! """ symDegrees = self.symDegreesDistribution() nd = len(symDegrees) symDegreesList = [] for d in range(nd): for x in range(symDegrees[d]): symDegreesList.append(d) nd = len(symDegrees) symDegreesList.sort() ndl = len(symDegreesList) if ndl % 2 == 0: medpos = ndl//2 medianSymDegree = symDegreesList[medpos] else: medpos0 = ndl/2 medpos1 = (ndl + 1)//2 medianSymDegree = (symDegreesList[medpos0] + symDegreesList[medpos1])/2 return medianSymDegree
[docs] def computeMeanSymDegree(self): """ Renders the mean degree of self. !!! self.size must be set previously !!! """ order = float(len(self.actions)) symDegrees = self.symDegreesDistribution() nd = len(symDegrees) meanSymDegree = 0.0 for i in range(nd): meanSymDegree += i * symDegrees[i] if self.size == 0: meanSymDegree = 0.0 else: meanSymDegree = meanSymDegree/self.order return meanSymDegree
[docs] def diameter(self, Oriented = False): """ Renders the (by default non-oriented) diameter of the digraph instance """ order = len(self.actions) nbDepths = self.neighbourhoodDepthDistribution(Oriented) nbDepths.reverse() if nbDepths[0] != 0: diameter = 'infinity' else: diameter = 0 for i in range(len(nbDepths)): if nbDepths[i+1] != 0: diameter = order - (i+1) break return diameter
[docs] def graphDetermination(self,Normalized=True): """ Output: average normalized (by default) arc determination: averageDeterm = ( sum_(x,y) [ abs( relf-relation[x][y] - Med )] / n ) / [( Max-Med ) if Normalized], where Med = self.valuationdomain['med'] and Max = self.valuationdomain['max']. """ Min = self.valuationdomain['min'] Med = self.valuationdomain['med'] Max = self.valuationdomain['max'] determ = Decimal("0.0") for x,rx in self.relation.items(): for y,rxy in rx.items(): if rxy > Med: determ += rxy - Med else: determ += Med - rxy if Normalized: averageDeterm = (determ / Decimal(str(self.order)))/(Max-Med) else: averageDeterm = (determ / Decimal(str(self.order))) return averageDeterm
[docs] def computeSize(self): """ Renders the number of validated non reflexive arcs """ Med = self.valuationdomain['med'] #actions = [x for x in self.actions] #actions = self.actions #relation = self.relation size = 0 for x,rx in self.relation.items(): for y,rxy in rx.items(): if x != y: if rxy > Med: size += 1 return size
[docs] def computeCoSize(self): """ Renders the number of non validated non reflexive arcs """ Med = self.valuationdomain['med'] #actions = [x for x in self.actions] #relation = self.relation coSize = 0 for x,rx in self.relation.items(): for y,rxy in rx.items(): if x != y: if rxy < Med: coSize += 1 return coSize
[docs] def sizeSubGraph(self,choice): """ Output: (size, undeterm,arcDensity). Renders the arc density of the induced subgraph. """ Med = self.valuationdomain['med'] relation = self.relation order = float(len(choice)) size = 0 undeterm = 0 for x in choice: rx = relation[x] for y in choice: if x != y: if rx[y] > Med: size += 1 if rx[y] == Med: undeterm += 1 if len(choice) < 2: arcDensity = 0.0 else: arcDensity = (size * 100.0)/ (order * (order - 1 )) return size, undeterm, arcDensity
[docs] def agglomerationDistribution(self): """ Output: aggloCoeffDistribution, meanCoeff Renders the distribution of agglomeration coefficients. """ import array actions = [x for x in self.actions] order = len(actions) aggloCoeff = array.array('f', [0] * order) meanCoeff = 0.0 for i in range(order): neighborhood = self.gamma[actions[i]][0] | self.gamma[actions[i]][1] size, undeterm, aggloCoeff[i] = self.sizeSubGraph(neighborhood) meanCoeff += aggloCoeff[i] if order == 0: meanCoeff = 0.0 else: meanCoeff /= order return aggloCoeff, meanCoeff
[docs] def outDegreesDistribution(self): """ Renders the distribution of outdegrees. """ import array order = len(self.actions) outDegrees = array.array('i', [0] * (order+1)) for x in self.actions: nx = len(self.gamma[x][0]) outDegrees[nx] += 1 return outDegrees
[docs] def computeConcentrationIndexTrapez(self,X,N): """ Renders the Gini concentration index of the X serie. N contains the partial frequencies. Based on the triangles summation formula. """ n = len(X) #dg = self.outDegreesDistribution() X = list(range(10)) N = [0,0,0,0,0,0,0,0,0,0,] print('Xi ', X, N) Q = [0.0 for i in range(n)] F = [0.0 for i in range(n)] Qsum = 0.0 for i in range(n): Qsum += X[i] * N[i] print('Qsum ',Qsum) F[0] = float(X[0])/float(n) Q[0] = 0.0 for i in range(1,n,1): qi = (X[i] * N[i])/Qsum Q[i] += Q[i-1] + qi print('Q[i] i ', i, Q[i]) fi = float(N[i])/n F[i] += F[i-1] + fi print('i, F[i]', i, F) f0 = float(N[0])/float(n) gini = 1.0 - (f0*Q[0]) print('o gini ', gini) for i in range(1,n): fi = (float(N[i])/float(n)) gini -= fi * (Q[i-1] + Q[i]) print('i gini', i, gini) return gini
[docs] def computeConcentrationIndex(self,X,N): """ Renders the Gini concentration index of the X serie. N contains the partial frequencies. Based on the triangle summation formula. """ Qsum = 0.0 n = 0.0 r = len(X) for i in range(r): n += N[i] Qsum += X[i] * N[i] if Qsum != 0.0: Q = [0.0 for i in range(r)] F = [0.0 for i in range(r)] F[0] = N[0]/n Q[0] = (X[0] * N[0])/Qsum for i in range(1,r,1): qi = (X[i] * N[i])/Qsum Q[i] += Q[i-1] + qi fi = N[i]/n F[i] += F[i-1] + fi gini = 0.0 for i in range(r-1): gini += (F[i]*Q[i+1]) - (Q[i]*F[i+1]) else: gini = -1 return gini
[docs] def inDegreesDistribution(self): """ Renders the distribution of indegrees. """ import array order = len(self.actions) inDegrees = array.array('i', [0] * (order+1)) for x in self.actions: nx = len(self.gamma[x][1]) inDegrees[nx] += 1 return inDegrees
[docs] def symDegreesDistribution(self): """ Renders the distribution of symmetric degrees. """ import array order = len(self.actions) symDegrees = array.array('i', [0] * ((2*order)+1)) for x in self.actions: nx = len(self.gamma[x][0])+len(self.gamma[x][1]) symDegrees[nx] += 1 return symDegrees
[docs] def neighbourhoodDepthDistribution(self, Oriented=False): """ Renders the distribtion of neighbourhood depths. """ import array,copy actions = set(self.actions) order = len(actions) nv = order + 1 vecNeighbourhoodDepth = array.array('i', [0] * nv) for x in actions: nbx = 0 neighbx = set([x]) restactions = actions - neighbx while restactions != set() and nbx < order: nbx += 1 iterneighbx = copy.copy(neighbx) for y in iterneighbx: if Oriented: neighbx = neighbx | self.gamma[y][0] else: neighbx = neighbx | self.gamma[y][0] | self.gamma[y][1] restactions = actions - neighbx if restactions != set(): vecNeighbourhoodDepth[order] += 1 else: vecNeighbourhoodDepth[nbx] += 1 return vecNeighbourhoodDepth
[docs] def neighbourhoodCollection(self, Oriented = False, Potential = False): """ Renders the neighbourhood. """ import array,copy actions = set(self.actions) order = len(actions) if Potential: weakGamma = self.weakGammaSets() neighbourhoods = {} for x in actions: nbx = 0 neighbx = set([x]) restactions = actions - neighbx while restactions != set() and nbx < order: nbx += 1 iterneighbx = copy.copy(neighbx) for y in iterneighbx: if Potential: if Oriented: neighbx = neighbx | weakGamma[y][0] else: neighbx = neighbx | weakGamma[y][0] | weakGamma[y][1] else: if Oriented: neighbx = neighbx | self.gamma[y][0] else: neighbx = neighbx | self.gamma[y][0] | self.gamma[y][1] restactions = actions - neighbx #print 'neighbx', neighbx neighbourhoods[x]= neighbx return neighbourhoods
[docs] def strongComponents(self, setPotential = False): """ Renders the set of strong components of self. """ neighbourhoods = self.neighbourhoodCollection(Oriented = True, Potential = setPotential) strongComponents = set() for x in self.actions: componentx = set([x]) for y in neighbourhoods[x]: if x in neighbourhoods[y]: componentx = componentx | set([y]) strongComponents = strongComponents | set([frozenset(componentx)]) return strongComponents
[docs] def showMIS(self,withListing=True): """ Prints all maximal independent choices: Result in self.misset. """ import time print('*--- Maximal independent choices ---*') t0 = time.time() self.misset = set() actions = set(self.actions) n = len(actions) v = [0 for i in range(n+1)] for choice in self.MISgen(actions,frozenset()): v[len(choice)] += 1 if withListing: print(list(choice)) t1 = time.time() print('number of solutions: ', len(self.misset)) print('cardinality distribution') print('card.: ', list(range(n+1))) print('freq.: ', v) print('execution time: %.5f sec.' % (t1-t0)) print('Results in self.misset')
[docs] def showMinDom(self,withListing=True): """ Prints all minimal dominant choices: Result in self.domset. """ import time print('*--- Computing minimal dominant choices ---*') t0 = time.time() actions = set(self.actions) cover = {} for x in actions: cover[x]=self.gamma[x][1] | set([x]) dom1 = (frozenset(list(actions)),cover) #print dom1 self.minset = set() self.minhistory = set() for choice in self.minimalChoices(dom1): pass n = len(actions) v = [0 for i in range(n+1)] for choice in self.minset: v[len(choice)] += 1 if withListing: print(list(choice)) t1 = time.time() print('number of solutions: ', len(self.minset)) print('cardinality distribution') print('card.: ', list(range(n+1))) print('freq.: ', v) print('execution time: %.5f sec.' % (t1-t0)) print('iteration history: ', len(self.minhistory)) self.domset = self.minset.copy() print('Results in self.domset')
[docs] def showMinAbs(self,withListing=True): """ Prints minimal absorbent choices: Result in self.absset. """ import time print('*--- Computing minimal absorbent choices ---*') t0 = time.time() actions = set(self.actions) cover = {} for x in actions: cover[x]=self.gamma[x][0] | set([x]) abs1 = (frozenset(list(actions)),cover) print(abs1) self.minset = set() self.minhistory = set() for choice in self.minimalChoices(abs1): pass n = len(actions) v = [0 for i in range(n+1)] for choice in self.minset: v[len(choice)] += 1 if withListing: print(list(choice)) t1 = time.time() print('number of solutions: ', len(self.minset)) print('cardinality distribution') print('card.: ', list(range(n+1))) print('freq.: ', v) print('execution time: %.5f sec.' % (t1-t0)) print('iteration history: ', len(self.minhistory)) self.absset = self.minset.copy() print('Results in self.absset')
[docs] def showMaxDomIrred(self,withListing=True): """ Computing maximal +irredundant choices: Result in self.domirset. """ import time print('*--- Computing maximal +irredundant choices ---*') t0 = time.time() actions = set(self.actions) self.domirset = set() for choice in self.plusirredundant(actions): add = 1 mirsetit = self.domirset.copy() for mir in mirsetit: if mir < choice: self.domirset.remove(mir) else: if choice <= mir: add = 0 break if add == 1: self.domirset.add(frozenset(choice)) t1 = time.time() n = len(self.actions) v = [0 for i in range(n+1)] for choice in self.domirset: v[len(choice)] += 1 if withListing: print(list(choice)) print('number of solutions: ', len(self.domirset)) print('cardinality distribution') print('card.: ', list(range(n+1))) print('freq.: ', v) print('execution time: %.5f sec.' % (t1-t0)) print('Results in self.domirset')
[docs] def showMaxAbsIrred(self,withListing=True): """ Computing maximal -irredundant choices: Result in self.absirset. """ import time print('*--- Computing maximal -irredundant choices ---*') t0 = time.time() actions = set(self.actions) self.absirset = set() for choice in self.absirredundant(actions): add = 1 mirsetit = self.absirset.copy() for mir in mirsetit: if mir < choice: self.absirset.remove(mir) else: if choice <= mir: add = 0 break if add == 1: self.absirset.add(frozenset(choice)) t1 = time.time() n = len(self.actions) v = [0 for i in range(n+1)] for choice in self.absirset: v[len(choice)] += 1 if withListing: print(list(choice)) print('number of solutions: ', len(self.absirset)) print('cardinality distribution') print('card.: ', list(range(n+1))) print('freq.: ', v) print('execution time: %.5f sec.' % (t1-t0)) print('Results in self.absirset')
[docs] def showPreKernels(self,withListing=True): """ Printing dominant and absorbent preKernels: Result in self.dompreKernels and self.abspreKernels """ import time print('*--- Computing preKernels ---*') actions = set(self.actions) n = len(actions) self.dompreKernels = set() self.abspreKernels = set() t0 = time.time() for choice in self.independentChoices(self.singletons()): restactions = actions - choice[0][0] if restactions <= choice[0][1]: self.dompreKernels.add(choice[0][0]) if restactions <= choice[0][2]: self.abspreKernels.add(choice[0][0]) t1 = time.time() if withListing: print('Dominant preKernels :') for choice in self.dompreKernels: print(list(choice)) print(' independence : ', self.intstab(choice)) print(' dominance : ', self.domin(choice)) print(' absorbency : ', self.absorb(choice)) print(' covering : %.3f' % self.averageCoveringIndex(choice, direction='out')) print('Absorbent preKernels :') for choice in self.abspreKernels: print(list(choice)) print(' independence : ', self.intstab(choice)) print(' dominance : ', self.domin(choice)) print(' absorbency : ', self.absorb(choice)) print(' covering : %.3f' % self.averageCoveringIndex(choice, direction='in')) print('*----- statistics -----') print('graph name: ', self.name) print('number of solutions') print(' dominant kernels : ', len(self.dompreKernels)) print(' absorbent kernels: ', len(self.abspreKernels)) print('cardinality frequency distributions') print('cardinality : ', list(range(n+1))) v = [0 for i in range(n+1)] for ch in self.dompreKernels: v[len(ch)] += 1 print('dominant kernel : ',v) v = [0 for i in range(n+1)] for ch in self.abspreKernels: v[len(ch)] += 1 print('absorbent kernel: ',v) print('Execution time : %.5f sec.' % (t1-t0)) print('Results in sets: dompreKernels and abspreKernels.')
[docs] def computePreKernels(self): """ computing dominant and absorbent preKernels: Result in self.dompreKernels and self.abspreKernels """ actions = set(self.actions) n = len(actions) dompreKernels = set() abspreKernels = set() for choice in self.independentChoices(self.singletons()): restactions = actions - choice[0][0] if restactions <= choice[0][1]: dompreKernels.add(choice[0][0]) if restactions <= choice[0][2]: abspreKernels.add(choice[0][0]) self.dompreKernels = dompreKernels self.abspreKernels = abspreKernels
[docs] def generateDomPreKernels(self): """ Generate all dominant prekernels from independent choices generator. """ actions = set(self.actions) for item in self.independentChoices(self.singletons()): choice = item[0][0] gammaDomChoice = item[0][1] restactions = actions - choice if restactions <= gammaDomChoice: yield choice
[docs] def generateAbsPreKernels(self): """ Generate all absorbent prekernels from independent choices generator. """ actions = set(self.actions) for item in self.independentChoices(self.singletons()): choice = item[0][0] gammaAbsChoice = item[0][2] restactions = actions - choice if restactions <= gammaAbsChoice: yield choice
[docs] def components(self): """Renders the list of connected components.""" A = {} for x in self.actions: A[x] = 0 ncomp = 1 ConComp = [] for x in A: Comp = set() if A[x] == 0: A[x] = ncomp Comp = Comp | set([x]) Comp = Comp | self.collectcomps(x, A, ncomp) if len(Comp) > 0: ncomp = ncomp + 1 ConComp = ConComp + [Comp] return ConComp
[docs] def showComponents(self): print('*--- Connected Components ---*') k=1 for Comp in self.components(): component = list(Comp) component.sort() print(str(k) + ': ' + str(component)) xk = k + 1
[docs] def collectcomps(self, x, A, ncomp): """Recursive subroutine of the components method.""" Comp = set() Nx = self.gamma[x][0] | self.gamma[x][1] for y in Nx: if A[y] == 0: A[y] = ncomp Comp.add(y) Comp = Comp | self.collectcomps(y, A, ncomp) return Comp
[docs] def outDegrees(self): """ renders the median cut outdegrees """ outDegrees ={} for x in self.actions: outDegrees[x] = len(self.gamma[x][0]) return outDegrees
[docs] def inDegrees(self): """ renders the median cut indegrees """ inDegrees ={} for x in self.actions: inDegrees[x] = len(self.gamma[x][1]) return inDegrees
[docs] def bestRanks(self): """ renders best possible ranks from indegrees account """ bestRanks = {} inDegrees = self.inDegrees() for x in self.actions: bestRanks[x] = inDegrees[x] + 1 return bestRanks
[docs] def worstRanks(self): """ renders worst possible ranks from outdegrees account """ worstRanks = {} outDegrees = self.outDegrees() for x in self.actions: worstRanks[x] = self.order - outDegrees[x] return worstRanks
[docs] def gammaSets(self): """ Renders the dictionary of neighborhoods {node: (dx,ax)} with set *dx* gathering the dominated, and set *ax* gathering the absorbed neighborhood. """ Med = self.valuationdomain['med'] actions = self.actions relation = self.relation gamma = {} for x in actions: dx = set() ax = set() rx = relation[x] for y in actions: if x != y: if rx[y] > Med: dx.add(y) if relation[y][x] > Med: ax.add(y) gamma[x] = (dx,ax) return gamma
[docs] def notGammaSets(self): """ Renders the dictionary of neighborhoods {node: (dx,ax)} with set *dx* gathering the not dominated, and set *ax* gathering the not absorbed neighborhood. """ Med = self.valuationdomain['med'] actions = self.actions relation = self.relation notGamma = {} for x in actions: dx = set() ax = set() rx = relation[x] for y in actions: if x != y: if rx[y] < Med: dx.add(y) if relation[y][x] < Med: ax.add(y) notGamma[x] = (dx,ax) return notGamma
def _gammaSets(self): """ Renders the dictionary of neighborhoods {node: (dx,ax)}""" gamma = {} for x in self.actions: dx = self.dneighbors(x) ax = self.aneighbors(x) gamma[x] = (dx,ax) return gamma
[docs] def weakGammaSets(self): """ Renders the dictionary of neighborhoods {node: (dx,ax)}""" weakGamma = {} for x in self.actions: dx = self.weakDneighbors(x) ax = self.weakAneighbors(x) weakGamma[x] = (dx,ax) return weakGamma
def _notGammaSets(self): """ Renders the dictionary of not neighborhoods {node: (dx,ax)} """ notGamma = {} for x in self.actions: dx = self.notdneighbors(x) ax = self.notaneighbors(x) notGamma[x] = (dx,ax) return notGamma
[docs] def weakDneighbors(self,node): """ Renders the set of dominated out-neighbors of a node.""" Med = self.valuationdomain['med'] nb = set() for a in self.actions: if self.relation[node][a] >= Med: nb.add(a) return nb
[docs] def dneighbors(self,node): """ Renders the set of dominated out-neighbors of a node.""" Med = self.valuationdomain['med'] nb = set() for a in self.actions: if self.relation[node][a] > Med: nb.add(a) return nb
[docs] def notdneighbors(self,node): """ Renders the set of not dominated out-neighbors of a node.""" Med = self.valuationdomain['med'] nb = set() for a in self.actions: if a != node: if self.relation[node][a] < Med: nb.add(a) return nb
[docs] def aneighbors(self,node): """ Renders the set of absorbed in-neighbors of a node.""" Med = self.valuationdomain['med'] nb = set() for a in self.actions: if self.relation[a][node] > Med: nb.add(a) return nb
[docs] def weakAneighbors(self,node): """ Renders the set of absorbed in-neighbors of a node.""" Med = self.valuationdomain['med'] nb = set() for a in self.actions: if self.relation[a][node] >= Med: nb.add(a) return nb
[docs] def notaneighbors(self,node): """ Renders the set of absorbed not in-neighbors of a node.""" Med = self.valuationdomain['med'] nb = set() for a in self.actions: ## if a != node: ## if self.relation[a][node] < Med: ## nb.add(a) if a != node: if self.relation[a][node] < Med: nb.add(a) return nb
[docs] def singletons(self): """list of singletons and neighborhoods [(singx1, +nx1, -nx1, not(+nx1 or -nx1)),.... ]""" s = [] for x in self.actions: indep = set(self.actions) - (self.gamma[x][0] | self.gamma[x][1]) s = s + [(frozenset([x]),self.gamma[x][0],self.gamma[x][1],indep)] return s
[docs] def MISgen(self,S,I): """ generator of maximal independent choices (voir Byskov 2004): * S ::= remaining nodes; * I ::= current independent choice .. note:: Inititalize: self.MISgen(self.actions.copy(),set()) """ if S == set(): add = 1 self.missetit = self.misset.copy() for mis in self.missetit: if mis < I: self.misset.remove(mis) else: if I <= mis: add = 0 break if add == 1: self.misset = self.misset | frozenset([I]) yield I else: v = S.pop() Sv = S - (self.gamma[v][0] | self.gamma[v][1]) Iv = I | set([v]) for choice in self.MISgen(Sv,Iv): yield choice for choice in self.MISgen(S,I): yield choice
[docs] def independentChoices(self,U): """ Generator for all independent choices with neighborhoods of a bipolar valued digraph: .. note:: * Initiate with U = self.singletons(). * Yields [(independent choice, domnb, absnb, indnb)]. """ if U == []: yield [(frozenset(),set(),set(),set(self.actions))] else: x = list(U.pop()) for S in self.independentChoices(U): yield S if x[0] <= S[0][3]: Sxgamdom = S[0][1] | x[1] Sxgamabs = S[0][2] | x[2] Sxindep = S[0][3] & x[3] Sxchoice = S[0][0] | x[0] Sx = [(Sxchoice,Sxgamdom,Sxgamabs,Sxindep)] yield Sx
[docs] def coveringIndex(self,choice,direction="out"): """ Renders the covering index of a given choice in a set of objects, ie the minimum number of choice members that cover each non selected object. """ from decimal import Decimal actions = set([x for x in self.actions]) nonSelected = actions - choice n = len(choice) index = n for x in nonSelected: if direction == 'out': index = min( index, len(self.gamma[x][1] & choice) ) else: index = min( index, len(self.gamma[x][0] & choice) ) if n > 0: return Decimal(str(index))/Decimal(str(n)) else: return Decimal("0.0")
[docs] def averageCoveringIndex(self,choice,direction="out"): """ Renders the average covering index of a given choice in a set of objects, ie the average number of choice members that cover each non selected object. """ from decimal import Decimal choice = set(choice) actions = set([x for x in self.actions]) nonSelected = actions - choice n = len(choice) m = len(nonSelected) index = 0 for x in nonSelected: if direction == 'out': index += len(self.gamma[x][1] & choice) else: index += len(self.gamma[x][0] & choice) if n > 0 and m > 0: return ( Decimal(str(index))/Decimal(str(m)) ) / Decimal(str(n)) elif n > 0: return Decimal("1.0") else: return Decimal("0.0")
[docs] def zoomValuation(self,zoomFactor=1.0): """ Zooms in or out, depending on the value of the zoomFactor provided, the bipolar valuation of a digraph. """ zoomFactor = Decimal(str(zoomFactor)) oldMax = self.valuationdomain['max'] oldMin = self.valuationdomain['min'] oldMed = self.valuationdomain['med'] newMin = oldMin * zoomFactor newMax = oldMax * zoomFactor newMed = oldMed * zoomFactor actions = self.actions oldRelation = self.relation newRelation = {} for x in actions: newRelation[x] = {} for y in actions: newRelation[x][y] = oldRelation[x][y] * zoomFactor # install new values in self self.valuationdomain['max'] = newMax self.valuationdomain['min'] = newMin self.valuationdomain['med'] = newMed self.relation = newRelation
[docs] def recodeValuation(self,newMin=-1.0,newMax=1.0,Debug=False): """ Recodes the characteristic valuation domain according to the parameters given. .. note:: Default values gives a normalized valuation domain """ from decimal import Decimal oldMax = self.valuationdomain['max'] oldMin = self.valuationdomain['min'] oldMed = self.valuationdomain['med'] try: oldPrecision = self.valuationdomain['precision'] except: oldPrecision = Decimal('0') oldAmplitude = oldMax - oldMin if Debug: print(oldMin, oldMed, oldMax, oldAmplitude) newMin = Decimal(str(newMin)) newMax = Decimal(str(newMax)) newMed = Decimal('%.3f' % ((newMax + newMin)/Decimal('2.0'))) newPrecision = oldPrecision/oldMax newAmplitude = newMax - newMin if Debug: print(newMin, newMed, newMax, newAmplitude) print('old and new precison', oldPrecision, newPrecision) actions = self.actions oldrelation = self.relation newrelation = {} for x in actions: newrelation[x] = {} nrx = newrelation[x] orx = oldrelation[x] for y in actions: if orx[y] == oldMax: nrx[y] = newMax elif orx[y] == oldMin: nrx[y] = newMin elif orx[y] == oldMed: nrx[y] = newMed else: nrx[y] = newMin + ((orx[y] - oldMin)/oldAmplitude)*newAmplitude if Debug: print(x,y,orx[y],nrx[y]) # install new values in self self.valuationdomain['max'] = newMax self.valuationdomain['min'] = newMin self.valuationdomain['med'] = newMed self.valuationdomain['precision'] = newPrecision self.valuationdomain['hasIntegerValuation'] = False self.relation = newrelation
[docs] def dominantChoices(self,S): """ Generates all minimal dominant choices of a bipolar valued digraph. .. note:: Initiate with S = self.actions,copy(). """ Med = self.valuationdomain['med'] add = 1 domsetit = self.domset.copy() for dom in domsetit: if S < dom: self.domset.remove(dom) else: if S >= dom: add = 0 break if add == 1: self.domset = self.domset | set([frozenset(S)]) yield S for x in S: S1 = S - set([x]) if self.domin(S1) > Med: for choice in self.dominantChoices(S1): yield choice
[docs] def minimalChoices(self,S): """ Generates all dominant or absorbent choices of a bipolar valued digraph. .. note: * Initiate with S = (actions, dict of dominant or absorbent closed neighborhoods) * See showMinDom and showMinAbs methods. """ if S[0] not in self.minhistory: self.minhistory = self.minhistory | set([frozenset(S[0])]) add = True minsetit = self.minset.copy() for minch in minsetit: if S[0] < minch: self.minset.remove(minch) else: if S[0] >= minch: add = False break if add: self.minset = self.minset | set([frozenset(S[0])]) yield S for x in S[0]: Sxchoice = S[0] - set([x]) Sx = (Sxchoice,{}) covering = True for cover in S[1]: coverx = S[1][cover] - set([x]) if coverx == set(): covering = False break Sx[1][cover] = coverx if covering: for choice in self.minimalChoices(Sx): yield choice
[docs] def absorbentChoices(self,S): """ Generates all minimal absorbent choices of a bipolar valued digraph. """ Med = self.valuationdomain['med'] add = 1 abssetit = self.absset.copy() for absch in abssetit: if S < absch: self.absset.remove(absch) else: if S >= absch: add = 0 break if add == 1: self.absset = self.absset | set([frozenset(S)]) yield S for x in S: S1 = S - set([x]) if self.absorb(S1) > Med: for choice in self.absorbentChoices(S1): yield choice
[docs] def kChoices(self,A,k): """ Renders all choices of length k from set A """ import copy if k == 0: yield set() else: while len(A) > 0: x = A.pop() Ax = copy.copy(A) k1 = k - 1 for ch in self.kChoices(Ax,k1): yield ch | set([x])
[docs] def powerset(self,U): """ Generates all subsets of a set. """ if U == set(): yield set() else: U1 = set(U) x = U1.pop() for S in self.powerset(U1): yield S yield S | set([x])
[docs] def plusirredundant(self,U): """ Generates all +irredundant choices of a digraph. """ Med = self.valuationdomain['med'] if U == set(): yield set() else: x = U.pop() for S in self.plusirredundant(U): yield S Sx = S | set([x]) if self.domirred(Sx) > Med: yield Sx
[docs] def absirredundant(self,U): """ Generates all -irredundant choices of a digraph. """ Med = self.valuationdomain['med'] if U == set(): yield set() else: x = U.pop() for S in self.absirredundant(U): yield S S1 = S | set([x]) if self.absirred(S1) > Med: Sx = S | set([x]) yield Sx
[docs] def intstab(self,choice): """ Computes the independence degree of a choice. """ Min = self.valuationdomain['min'] Max = self.valuationdomain['max'] relation = self.relation deg = Min for a in choice: for b in choice: x = relation[a][b] if x > deg and a != b: deg = x res = Max - deg + Min return res
[docs] def domin(self,choice): """ Renders the dominance degree of a choice. """ deg = self.valuationdomain['max'] Min = self.valuationdomain['min'] restactions = set(self.actions) - choice for a in restactions: dega = Min for b in choice: x = self.relation[b][a] if x > dega: dega = x if dega < deg: deg = dega return deg
[docs] def absorb(self,choice): """ Renders the absorbency degree of a choice. """ deg = self.valuationdomain['max'] Min = self.valuationdomain['min'] restactions = set(self.actions) - choice for a in restactions: dega = Min for b in choice: x = self.relation[a][b] if x > dega: dega = x if dega < deg: deg = dega return deg
[docs] def domirred(self,choice): """ Renders the crips +irredundance degree of a choice. """ Med = self.valuationdomain['med'] irred = 1 if len(choice) > 1: for x in choice: if self.domirredx(choice,x) < Med: irred = 0 break if irred == 1: return self.valuationdomain['max'] else: return self.valuationdomain['min']
[docs] def domirredval(self,choice,relation): """ Renders the valued +irredundance degree of a choice. """ #import array actions = self.actions n = len(actions) Min = Decimal(str(self.valuationdomain['min'])) Med = Decimal(str(self.valuationdomain['med'])) Max = Decimal(str(self.valuationdomain['max'])) for x in actions: relation[x][x] = Max result = Max for x in choice: nbclx = self.readabsvector(x,relation) nbclchoice = [Min for i in actions] restchoice = set(choice) restchoice.remove(x) for y in restchoice: nbcly = self.readabsvector(y,relation) nbclchoice = [max(nbclchoice[i],nbcly[i]) for i in range(n)] resultx = max([min(nbclx[i],self.contra(nbclchoice)[i]) for i in range(n)]) result = min(result, resultx) return result
[docs] def domirredx(self,choice,x): """ Renders the crips +irredundance degree of node x in a choice. """ Max = self.valuationdomain['max'] Min = self.valuationdomain['min'] nx = self.gamma[x][0] | set([x]) chx = choice - set([x]) ny = set() for y in chx: ny = ny | self.gamma[y][0] | set([y]) nxpriv = nx - ny if nxpriv == set(): return Min else: return Max
[docs] def absirredval(self,choice,relation): """ Renders the valued -irredundance degree of a choice. """ #import array actions = self.actions n = len(actions) Min = self.valuationdomain['min'] Med = self.valuationdomain['med'] Max = self.valuationdomain['max'] for x in actions: relation[x][x] = Max result = Max for x in choice: nbclx = self.readdomvector(x,relation) nbclchoice = [Decimal(str(Min)) for i in actions] restchoice = set(choice) restchoice.remove(x) for y in restchoice: nbcly = self.readdomvector(y,relation) nbclchoice = [