The Python digraphs module for Rubis - Ernst
Contents
1. Obvi ously we only may work with digraphs of finite order The size s G of the digraph G is given by the number of more present than absent arcs characterised via R The ratio of the size over the maximum possible number of arcs which is n x n represents the arc density or the fill rate of the digraph The example digraph testdigraph py distributed with the digraphs module is characterised as shown in table 2 5This design feature allows to easily model only partially characterized graphs 6Please notice that we ignore in the fill rate statistic the trivially present reflexive arcs 10 In nauty format the same digraph may be represented as n 5 1 dg 5 oP WN RF e eNU p WwW oe with help of the g showdre method In order to be able to treat valued digraphs of medium or even large sized order of up to several thousands of vertices we store the persistent definition of a given digraph in a Python dictionary format that guarantees the best possible access times to any individual arc s charateristic value The Python dictionary object representation based on a hashed key based access mechanism gives here the best possible performance Below we show the Python representation of the same example digraph The actions vertices of the graph are represented as a listobject actions from a list of keys in the format of quoted strings 1 2 3 4 5 The characteristic relation2. The digraphs module code source is free this means that everyone is free to use it and free to redistribute it on certain conditions The digraphs module is not in the public domain it is copyrighted and there are restrictions on its distribution as follows Copyright 2006 2013 Raymond Bisdorff University of Luxembourg This Python source code 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 2 of the License or at your option any later version This resource 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 A copy of the GNU General Public License is available on the World Wide web You can also obtain it by writing to the Free Software Foundation Inc 675 Mass Ave Cambridge MA 02139 USA References 1 Raymond Bisdorff Marc Pirlot and Mare Roubens On Choices and kernels in bipolar valued digraphs European Journal of Operational Research EJOR 175 2006 155 170 2 Raymond Bisdorff Patrick Meyer Marc Roubens RuBy a bipolar valued outranking method ology for the best choice decision problem SMA Preprints 02 version 01 University of Lux embourg 2006 PDF 3 Raymond Bisdorff Patrick Meyer and Thomas Veneziano Quick dive into
3. XMCDA 2 0 De cision Deck Consortium Specificiation Committee 2009 4 B la Bollob s Random Graphs 2nd edition Cambridge University Press 2001 Sat http www gnu org copyleft gpl html 26 Index bipolar outranking graph 9 Class BipolarOutrankingDigraph 21 CompleteDigraph 20 CondorcetDigraph 18 Digraph 17 19 20 EmptyDigraph 20 Kemeny Order 19 LinearOrder 19 OutrankingDigraph 22 PerformanceTableau 18 22 RandomDigraph 14 RankedPairsOrder 19 SortingDigraph 19 VotingProfile 18 install the software 1 interactive use 4 Method 4 Digraph components 12 Digraph gammaSets 12 Digraph notGammaSets 12 Digraph save 14 Digraph showAll 11 Digraph showdre 11 Digraph showPreKernels 5 Digraph showshort 4 Digraph showStatistics 4 Performance Tableau 22 persistent storage 10 random digraphs 13 RuBy 6 saving digraphs 14 test the installation 2 XMCDA 2 0 15 XML storage 14 27 Contents 1 Introduction 1 2 Purpose of the digraphs module 1 3 Download and installation of the digraphs module 1 4 Interactive use of the digraphs module methods 4 5 Solving a RuBIS decision aiding problem 6 5 1 The example choice decision problem 00 000020 e ee 6 5 2 The example Python datafile 0 2 020200 eee eee eee 6 5 3 Computing the RUBIS choice recommendation 000 7 5 4 Illustration of the RUBIS recommendation
4. access order is undetermined as is formally required for the dictionary as well as for the generalset object The showAll self method method outputs all the definition data of a given digraph gt gt gt g showAl1 KK KK KK KK OK K FK OK 2K K KK K Digraph reltest 11 Actions 17 2 3 747 757 Valuation domain med 0 0 max 10 0 min 10 0 Relation f 94 41 10 0 3 10 0 2 10 0 5 10 0 4 10 73 41 10 0 3 10 0 2 10 0 5 10 0 4 10 22 41 10 0 3 10 0 2 10 0 5 10 0 4 10 7B 4 10 0 3 10 0 2 10 0 5 10 0 4 10 9A 1 10 0 3 10 0 2 10 0 5 10 0 4 10 Connected Components 1 set 1 3 2 5 47 Neighborhoods Gamma 4 set 4 set 5 47 73 set 2 5 set 2 5 4 2 set 3 set 3 7B set 1 3 set 3 47 4 set 1 73 5 set 1 Not Gamma 4 set 3 72 5 set 3 2 73 set 1 47 set 17 2 set 1 5 47 set 1 5 4 7B set 2 47 set 1 27 74 gt set 2 set 3 2 5 The neighborhoods of a given action in a digraph are
5. comparisonType gt R lt comparisonType gt lt pairs gt lt description gt lt subTitle gt Valued Adjacency Table lt subTitle gt lt comment gt general general Digraph lt comment gt lt description gt lt pair gt lt initial gt lt alternativeID gt 1 lt alternativeID gt lt initial gt lt terminal gt lt alternativelID gt 1 lt alternativeID gt lt terminal gt lt value gt lt real gt 0 00 lt real gt lt value gt lt pair gt lt pair gt lt initial gt lt alternativeID gt 1 lt alternativeID gt lt initial gt lt terminal gt lt alternativelID gt 2 lt alternativelD gt lt terminal gt lt value gt lt real gt 0 00 lt real gt lt value gt lt pair gt lt pair gt lt initial gt lt alternativeID gt 10 lt alternativeID gt lt initial gt lt terminal gt lt alternativeID gt 10 lt alternativeID gt lt terminal gt lt value gt lt real gt 0 00 lt real gt lt value gt lt pair gt lt pairs gt lt alternativesComparisons gt lt xmcda XMCDA gt The validating XML Schema Definition is stored in the joined XMCDA 2 0 0 xsd file Such XML description of digraphs like sampleDigraph xmcda2 may be conveniently accessed with an XML enhanced browser via a joined XSL stylesheet xmcda2Rubis xsl The resulting HTML visualition of the testdigraph instance is illustrated when clicking on the following link sampleDigraph xml It is worthwhile having a look at the frame source code which will reproduce the
6. gt set 4 2 in gt set 3 4 5 out gt set 3 4 5 3 in gt set 2 4 out gt set 1 2 4 5 4 in gt set 1 2 3 out gt set 2 3 5 5 in gt set 2 3 4 out gt set 2 Not Gamma 4 in gt set 2 4 5 out gt set 2 3 5 2 in gt set 1 out gt set 1 73 in gt set 1 5 out gt set 4 in gt set 5 out gt set 1 75 in gt set 1 out gt set 1 3 4 If you see this line all tests were passed successfully Enjoy BEA AAAI kkk kkk kkk R B September 2008 Revision 1 18 FKK KK KK K K K K FK K K 3K K 2K K FK K FK K OK K OK K FK FK FK FK K FK K KK K K Extensive verbose tests may be run with the following command see the makefile file HOME Digraph make verboseTests This user manual may also be downloaded under pdf format digraphsdoc pdf 4 Interactive use of the digraphs module methods You may also start an interactive Python session for exploring the classes and methods provided by the digraphs py ressource To do so enter the Python commands following the session prompts marqued with gt gt gt The lines without the prompt are output from the Python interpreter HOME Digraph python Python 2 7 3
7. highlighted XML source code for this web page 6 5 Reading XML encoded digraph files An XMCDA 2 0 encoded digraph file such as the sampleDigraph xm1 file shown above may be instantiated as a normal digraph object via the XMCDA2Digraph class constructor gt gt gt g XMCDA2Digraph sampleDigraph gt gt gt g showshort SSS show short Digraph sampleDigraph Actions Pait a2 a3 Valuation domain max 1 0 med 0 0 min 1 0 16 Connected Components 1 al a2 a3 gt gt gt 7 The modules hierarchy v 1 6 The Digraph source code is divided into two main interdependent modules the digraphs and the perfTabs modules followed by three additional modules the votingDigraphs the sortingDigraphs and the linearOrders modules for tackling respectively voting sorting and ranking problem 7 1 The digraphs module design v 1 6 The digraphs module contains the main Digraph The subclass hierarchy for versions 1 6 is shown hereafter CLASSES Digraph AsymmetricDigraph AsymmetricPartialDigraph CirculantDigraph CoDualDigraph CocaDigraph CompleteDigraph DualDigraph EmptyDigraph GridDigraph IndeterminateDigraph KneserDigraph MedianExtendedDigraph OutrankingDigraph Digraph perfTabs PerformanceTableau BipolarOutrankingDigraph OutrankingDigraph perfTabs PerformanceTableau BipolarIntegerOutrankingDigraph BipolarOutranki
8. lt title gt Nodes of the digraph lt title gt lt comment gt Set of nodes of the digraph lt comment gt lt description gt lt alternative id 1 name nameless gt lt description gt lt comment gt No comment lt comment gt lt description gt lt type gt real lt type gt lt active gt true lt active gt lt reference gt false lt reference gt lt alternative gt lt alternative id 2 name nameless gt lt description gt lt comment gt No comment lt comment gt lt description gt lt type gt real lt type gt lt active gt true lt active gt lt reference gt false lt reference gt lt alternative gt lt alternative id 10 name nameless gt lt description gt lt comment gt No comment lt comment gt lt description gt lt type gt real lt type gt lt active gt true lt active gt lt reference gt false lt reference gt lt alternative gt lt alternatives gt lt alternativesComparisons id 1 name R gt lt description gt lt title gt Randomly Valued Binary Relation lt title gt lt comment gt general general Digraph lt comment gt lt description gt 15 lt scale name valuationDomain gt lt description gt lt subTitle gt Valuation Domain lt subTitle gt lt description gt lt quantitative gt lt minimum gt lt real gt 0 00 lt real gt lt minimum gt lt maximum gt lt real gt 1 00 lt real gt lt maximum gt lt quantitative gt lt scale gt lt
9. the RandomDigraph class constructor renders irreflexive digraphs instances i e all reflexive relation x x are in fact put to certainly false by default Indeed in the context of outranking relations the reflexive part of the preference structure is trivially given and we opted for ignoring in general this part of the outranking graph Therefore the fill rate shown here above is not taking into account the reflexive part of the relation 6 3 Saving digraphs class instances We finish our presentation of the digraphs implementation of digraphs with showing the method save self filename for persistently store a digraphs class instance Continuing the previous example session Continue gt gt gt g save fileName random10 20 Saving digraph in file lt random10 20 py gt gt gt gt h Digraph random10 20 gt gt gt h showShort x show short Digraph random10 20 Actions es 2 73 74 7B 6 tg 78 797 210 Valuation domain med Decimal 0 5 max Decimal 1 0 gt min Decimal 0 Connected Components 1 ET 10 2D 73 74 75 6 RES 8 9 gt gt gt Omitting the fileName argument produces an automatic saving with the default filename lt tempdigraph py gt 6 4 Storing digraphs as XML documents In order to allow easy access to stored digraphs we have also implemented procedures fo
10. the source code illustrates how 20 variety of digraphs of all types can be generated and how their characteristics and properties may be computed and printed 8 2 The BipolarOutrankingDigraph class The BipolarOutrankingDigraph class instantiates a digraph on the basis of a stored or a randomly generated performance tableau class BipolarOutrankingDigraph OutrankingDigraph PerformanceTableau Parameters performanceTableau fileName of valid py code optional coalition sublist of criteria Specialization of the standard OutrankingDigraph class for generating new bipolar ordinal valued outranking digraphs def __init__ self argPerfTab None coalition None NoVeto False import copy if isinstance argPerfTab PerformanceTableau RandomPerformanceTableau FullRandomPerformanceTableau perfTab argPerfTab else if argPerfTab None perfTab RandomPerformanceTableau else perfTab PerformanceTableau argPerfTab self name rel_ perfTab name self actions copy deepcopy perfTab actions Min Decimal 100 0 Med Decimal 0 0 Max Decimal 100 0 self valuationdomain min Min med Med max Max if coalition None criteria copy deepcopy perfTab criteria else criteria for g in coalition criterialg copy deepcopy perfTab criteria g self criteria criteria self convertWeightFloatToDecimal self relation self constructRelation crit
11. v2 7 3 70274d53cidd Apr 9 2012 20 52 43 GCC 4 2 1 Apple Inc build 5666 dot 3 on darwin Type help copyright credits or license for more information gt gt gt from digraphs import Digraph gt gt gt g Digraph test testdigraph gt gt gt g showShort show short Digraph testdigraph Actions pan Neos le Se oS TP a A Valuation domain med 0 max 10 min 10 Connected Components Ae APE Dek otis hy AP ARB 24 D22 uai The Digraph showshort method output reveals us that the default digraph testdigraph py is a connected digraph of order five evaluated in a valuation domain from 10 to 10 where arcs with credibility degrees above 0 are considered to be more or less present arcs with credibility degrees below 0 are considered to be more or less absent Arcs evaluated with a credibility degree of 0 are considered to be undetermined with respect to their presence or absence in the given digraph Some simple methods are easily applicable to this instantiated Digraph object g like the following Digraph showStatistics method gt gt gt g showStatistics aca general statistics for digraph lt testdigraph py gt order 5 nodes size 9 arcs undetermined 0 arcs arc density 45 00 components P at 0 1 2 3 4 outdegrees distribution 0 2 2 1 0 indegrees distribution 0 2 2 1 0 degrees dist
12. 00 0 00x percentile 0 83 Threshold pref 14 00 0 00x percentile 0 167 Threshold weakveto 50 00 0 00x percentile 0 83 C5 Scale 0 100 Weight 0 200 Threshold ind 10 00 0 00x percentile 0 5 Threshold veto 50 00 0 00x percentile 1 0 Threshold pref 14 00 0 00x percentile 0 5 Threshold weakveto 50 00 0 00x percentile 1 0 And the following exportGraphViz command generates a graph image see Figure 5 4 of the outranking relation on A RUBIS choice recommendation gt gt gt g exportGraphViz bestChoice g bestChoice worstChoice g worstChoice exporting a dot file dor GraphViz tools Exporting to rel_rubyExample dot dot Grankdir BT Tpng rel_rubyExample dot o rel_rubyExample png gt gt gt The next section introduces the design of the RuBIS digraph implementation 6 About bipolar valued digraphs In this section we shall introduce bipolar valued digraphs and illustrate a Python implementation design for persistent storage of such objects We conclude the section with the presentation of a method for generating diferent kinds of random digraphs Figure 1 The example outranking digraph 6 1 Persistent storage of digraphs A bipolar valued digraph G consists of a set of vertices generally called actions and denoted A The presence or absence of an arc x y between two vertices x and y in A G is evaluated via a characteristic relation function R that takes its v
13. 000000 8 6 About bipolar valued digraphs 9 6 1 Persistent storage of digraphs 2 0 00000000000 000 10 6 2 Working with random digraphs 0 2 2 000000 00000 13 6 3 Saving digraphs class instances ooo e ee 14 6 4 Storing digraphs as XML documents 20 0 0 0000000 14 6 5 Reading XML encoded digraph files 2 0 0 000 16 7 The modules hierarchy v 1 6 17 7 1 The digraphs module design v 1 64 0000000 eee eee 17 7 2 The perfTabs module design v 1 6 ooo a a 000000004 18 7 3 The votingDigraphs module design v 1 6 o o a 18 7 4 The sortingDigraphs module design v 16 000 19 7 5 The linearOrders module design v 1 6 2 000004 19 8 Technical documentation v 1 6 19 8 1 ThesmainDigraph class way ae a OAR a RPE eR te es ee 19 8 2 The BipolarOutrankingDigraph class 2 ee ee 21 8 3 The PerformanceTableau class 1 0 0 0 0 00000 eee ee 22 9 Writing Python scripts using the digraphs module 23 10 Version comments 24 11 Acknowledgments 26 12 Copyright 26 28
14. 2Digraph XMCDADigraph XMLDigraph XMLDigraph24 7 2 The perfTabs module design v 1 6 The perfTabs module contains the main the PerformanceTableau class The subclass hierarchy for versions 1 6 is shown hereafter PerformanceTableau FullRandomPerformanceTableau O1dXMCDAPerformanceTableau RandomCBPerformanceTableau RandomPerformanceTableau RandomS3PerformanceTableau XMCDA2PerformanceTableau XMCDAPerformanceTableau XMLPerformanceTableau XMLRubisPerformanceTableau 7 3 The votingDigraphs module design v 1 6 The additional votingDigraphs module allowing to tackle election ballots contains the main the VotingProfile classe with its subclass hierarchy for versions 1 6 and the CondorcetDigraph 18 CLASSES VotingProfile ApprovalVotingProfile RandomApprovalVotingProfile RandomVotingProfile digraphs Digraph CondorcetDigraph 7 4 The sortingDigraphs module design v 1 6 The additional sortingDigraphs module allowing to tackle sorting problems contains the main the SortingDigraph classe a specialisation either of the BipolarOutrankingDigraph or of the PerformanceTableau class CLASSES digraphs BipolarOutrankingDigraph digraphs QutrankingDigraph perfTabs PerformanceTableau SortingDigraph digraphs BipolarOutrankingDigraph perfTabs PerformanceTableau perfTabs PerformanceTableau SortingDigraph digraphs BipolarOutrankingDigraph perfTabs PerformanceTableau 7 5 The linearOrders module design v 1
15. 6 The additional linearOrders module allowing to tackle linear ranking problems contains the generic LinearOrder class a specialisation of the general Digraph class with its concrete children essentially the KemenyOrder and the RankedPairsOrder classes CLASSES digraphs Digraph ExtendedPrudentDigraph LinearOrder KemenyOrder KohlerOrder NetFlowsOrder RankedPairsOrder 8 Technical documentation v 1 6 In an interactive Python shell it is possible to browse the classes and their methods with the help X where X is any class name in the list above A detailed technical documentation auto matically prepared from the current version may be found here 8 1 The main Digraph class The Digraph class is the principal object of the digraphs module The constructor __init__ either creates a RandomValuationDigraph instance or instantiates a Digraph object from a permantly stored version of the following format 19 actionset lt actioniName gt lt action2Name gt valuationdomain min lt minimum gt med lt median value gt max lt maximum gt relation lt actioniName gt lt actioniName gt lt value in valuationdoain gt lt action2Name gt lt value in valuationdoain gt lt action2Name gt lt actioniName gt lt value in valuationdoain gt lt action2Name gt lt value in valuationdoain gt The digraph stored object is composed of a list of actions a val
16. The Python digraphs module for RUBIS Raymond Bisdorff Computer Sciences and Communication Research Unit Faculty of Sciences Technology and Communication University of Luxembourg 1 Introduction This Manual Revision 1 18 describes the Python implementation of a generic digraphs module for computing kernels and other qualified choices in bipolar valued outranking digraphs This computing ressource is useful in the context of the testing of the RUBIS decision support method 1 Developping the RUBIS decision support methodology is an ongoing research project of Ray mond Bisdorff University of Luxembourg The Python digraphs module is based on the optimized in built set class and therefore requires at least version 2 4 0 of Python The basic idea of the digraphs Python module is to make easy python interactive sessions or write short Python scripts for computing all kind of results from a bipolar valued outranking digraph These include such features as maximal independent or irredundant choices maximal dominant or absorbent choices etc The Python development of these computing ressources offers the advantage of an easy to write and maintain OOP source code as expected from a performing scripting language without loosing on efficiency in execution times compared to compiled languages such as C or Java 2 Purpose of the digraphs module This document describes how to use the Python digraphs module for computing qualified choices in
17. adn detection e Revision 1 594 e Revision 1 593 tion tests Revision 1 592 Revision 1 586 Revision 1 580 Revision 1 575 Revision 1 565 tion Revision 1 563 Revision 1 562 Revision 1 557 Revision 1 556 Revision 1 555 eTableau class Revision 1 553 Revision 1 552 Revision 1 551 Revision 1 548 Revision 1 546 Revision 1 539 for tree layout added bipolar correlation with bipolar equivalence counts added ordinal correlation computation with the standard Kemeny index added strict and weak Condorcet Winners detecters added outrankingDigraphs module to auto sphinx documentation mode added ranking by choosing method added flatChoice method released under GPL version 3 added sphinx autodoc generation tools added degrees best and worst preordering methods to Digraph class added digrap2Graph method refactoring proportional threshold computation added agrum directory with C sources for chordless circuits enumeration refactoring perfTabs py module added RandomRankPerformanceTableau class for linear orderings aggrega added hasOddWeightsAlgebra method to the PerformanceTableau class added difference valuation digraph class added KemenyOrder class added NormalizedPerformanceTableau Class refactored old version RubyChoice to RubisBestChoiceRecommenda added linear order graphviz drawing added RankedPairsOrder class added Slater s ranking rule added rankedPairs and Kemeny order generatio
18. alues in a discrete valuation domain L m m 1 1 0 1 m 1 m For R z y gt 0 we consider that the arc x y is more present than absent when R x y lt 0 we consider that the arc in question is more absent than present If R x y m the arc x y is certainly present if R a y m the arc in question is certainly absent In case R x y 0 we dont decide whether the arc is actually present or absent This way three values of the characteristic domain L are distinguished the minimum value m signifying warranted absence the maximum value m signifying warranted presence and the median value 0 signifying undeterminedness of existence of an arc in the given digraph Table 2 A crisp digraph characterisation R z y a b c d m m M m e m m m m mM m m m m m m m m m m M Aaa or m M m m m A bipolar valued digraph such that only values m and m are used by the characteristic function R is called a crisp digraph To any bipolar m m valued digraph we may also associate a solely positive or null characteristic valuation Commonly a 2 digits percent transformation such as the following R a y m 2m x 100 is used therefore Conversely any bipolar valuation may be normalized to a standard m m valuation domain by the inverse transformation R x y 100 x 2m m The order n of a given bipolar graph G corresponds to the number of vertices in V G
19. aux showPerformanceTableau self sorted True Print the performance Tableau showAll self Show fonction for performance tableau An template Python file of a performance tableau data file is given below HHHHHHHFHHEHHHHHHEHHHRHHEHHEHHHHHHHHHE REESE performance tableau data file template HHEHHHHHHHHHHHHHEHHEHHHEHHEHHEHHHHHEHHHE EH actions al a2 a3 a4 criteria g1 scale 0 10 thresholds ind 1 0 0 0 pref 2 0 0 0 gt weakveto 6 0 0 0 veto 8 0 0 0 gt weight 2 0 22 g2 scale 0 10 thresholds ind 1 0 0 0 pref 2 0 0 0 gt weakveto 6 0 0 0 veto 8 0 0 0 weight 1 0 evaluation g1 al 1 0 a2 g2 gt al 8 0 a 9 Writing Python scripts using the digraphs module The digraphs module allows to easily write Python scripts for specific purposes We shall illustrate this use with some example of statistical investigation of random digraphs usr bin env python Example of Digraph module usage R B May 2009 HHHHHHHHHHARHHHHHHHEHRRARA RR import sys random copy array from digraphs import RandomDigraph narg len sys argv if narg lt 2 fileoutName densitytest csv sample 100 arcProbability 0 6 else fileoutName str sys argv 1 sample eval sys argv 2 arcProbability eval
20. bipolar valued digraphs and explains some computational results you may expect to get from this computing resource It does not teach you how to write Python scripts and source code in general There are Python tutorials and user manuals available at the official Python web site which you might want to consult the need given The Python digraphs module source code is copyrighted 3 Download and installation of the digraphs module Using the digraphs module is easy You only need to have a Python system installed of version 2 4 and later By default Python 2 7 is supposed to be installed However the installation procedure proposes also a conversion to Python 3 see below Notice that the recent Python 3 3 version implements very efficiently Decimals in C Now Decimals are mainly used in the digraph valuation functions which makes this last python version much faster more than twice as fast when extensive digraph operations are performed Two download options are given 1 Either easiest under Linux or Mac OS X access the subversion repository with the following command svn co http leopold loewenheim uni 1lu svn repos Digraph extract it somewhere and cd to the Digraph directory 2 Or download from the http ernst schroeder uni lu Digraph web page the distribu tion file Digraph Revision 1 xxx into your home directory say HOME for instance Extract ing the zip file installs a working directory HOME Digraph with all ne
21. cessary files Following make options are available e Digraph make docHTML generates the HTML documentation in the doc subdirectory hyperlatex needed apt get install hyperlatex e Digraph make docPDF generates a PDF document in the doc subdirectory e Digraph make tests runs a nose test suite in the test directory python nose package required easy_install nose e Digraph make verboseTests runs a verbose with stdout not captured nose test suite e Digraph make install installs with sudo the digraphs module in the current running python environment e Digraph make 2to3 converts automatically the Python 2 sources to Python 3 and saves them into the py3 direc tory e Digraph sudo make install3 installs with sudo the digraphs Python 3 module in the corresponding environment the case given You may test your Python installations by simply running the digraphs py source code as a batch Python program HOME Digraph python digraphs py Simple execution will show a list of results concerning a randomly generated digraph Home Digraph digraphs py EEEE EE o ARIK II ARIK Python digraphs module Revision 1 18 Copyright C 2006 2007 University of Luxembourg The module comes with ABSOLUTELY NO WARRANTY to the extent permitted by the applicable law lIf the source code file digraphs py is made excutable with chmod x digraphs py i
22. d graphs for testing the chordless circuits enumeration e Revision 1 450 launch R via env for Mac OS X compatibility Revision 1 448 hasBipolarVeto Flag added to RandomBipolarOutrankingDigraph construc tor Revision 1 447 added Python 3 1 version Revision 1 440 final hopefully bipolar veto implementation Revision 1 438 added Decimal conversion for stored digraph float instances debugged Revision 1 435 refactoring of the outrankindex computation Revision 1 433 added vetoType parameter Revision 1 428 added hasBipolarVeto Flag to BipolarIntegerOutrankingDigraph Revision 1 425 new definition of bipolar outranking relation with hasBipolarVeto Flag 25 Revision 1 422 added CoDualDigraph class and introduced the bipolar veto concept for bipolar outranking digraphs Revision 1 421 added Digraph showActions method for strongComponentCollapsedDi graph presentation support Revision 1 420 added StrongComponentCollapsedDigraph class Revision 1 417 showall converted to showAll and refactored Revision 1 415 added nose tests separated file nosetests vs noseTestsDigraph py Revision 1 413 refactoring CocaDigraph construction Revision 1 411 added RandomTournament Class Revision 1 410 optimised chordless circuits extraction Revision 1 406 complete set of nose tests passed 11 Acknowledgments Thanks to everybody who reported bugs or who suggested or even implemented useful new features 12 Copyright
23. dule allows to easily compute the RUBIS choice recommendation for this example data file HOME Digraph python Python 2 4 4 Sep 10 2005 14 42 42 GCC 3 4 4 20050721 Red Hat 3 4 4 2 on linux2 Type help copyright credits or license for more information gt gt gt from digraphs import gt gt gt t PerformanceTableau examples samplePerformanceTableau gt gt gt g BipolarQutrankingDigraph t gt gt gt g showRubyChoice BOO OO A CARA ACK RuBy choice recommendation weak cordless odd circuits a gt c gt b gt d gt result 0 weak circuit s set No weak circuits added x Relation Table S 2a p Le q a 0 00 60 00 60 00 100 00 b 20 00 0 00 60 00 60 00 c 20 00 100 00 0 00 60 00 ar 20 00 20 00 20 00 0 00 Ruby best choice recommendation s in decreasing order of determinateness Credibility domain med 0 0 max 100 0 min 100 0 gt gt potential BC choice b irredundancy 100 00 independence 100 00 dominance 20 00 absorbency 0 00 determinateness 0 20 characteristic vector a 20 00 b 20 00 c 20 00 d 20 00 gt gt gt The bipolar outranking digraph constructed from this example data file does not show any cordless odd circuit and alternative b is recommended as best decision candidate 5 4 Illustrati
24. ef scale 0 100 gt thresholds ind 10 0 0 0 pref 14 0 0 0 gt weakveto 50 0 0 0 veto 50 0 0 0 weight 1 0 F MG Deis E gt scale 0 100 gt thresholds ind 10 0 0 0 pref 14 0 0 0 gt weakveto 50 0 0 0 veto 50 0 0 0 gt weight 1 0 EX Gk Maen hi gt scale 0 100 gt thresholds ind 10 0 0 0 pref 14 0 0 0 gt weakveto 50 0 0 0 veto 50 0 0 0 gt weight 1 0 F3 4The problem has been submitted for discussion by B Roy private communication 2005 C_4 f gt scale 0 100 gt thresholds ind 10 0 0 0 pref 14 0 0 0 weakveto 50 0 0 0 veto 50 0 0 0 gt weight 1 0 Cro gt scale 0 100 gt thresholds ind 10 0 0 0 pref 14 0 0 0 gt weakveto 50 0 0 0 veto 50 0 0 0 gt weight 1 0 evaluation C_1 a 30 0 b 40 0 c 75 0 d 85 0 C2 a 85 0 b 60 0 c 60 0 d 40 0 a Oe ae a 80 0 b 60 0 c 60 0 d 70 0 gt C_4 a 60 0 b 80 0 c 25 0 d 60 0 GbR a 70 0 b 75 0 verr 75 0 d 55 0 5 3 Computing the RUBIS choice recommendation An interactive Python session importing all classes and methods of our digraphs mo
25. eria perfTab evaluation NoVeto NoVeto self evaluation copy deepcopy perfTab evaluation self convertEvaluationFloatToDecimal try self description copy deepcopy perfTab description except pass methodData try 21 valuationType perfTab parameter valuationType variant perfTab parameter variant except valuationType bipolar variant standard methodDatal parameter valuationType valuationType gt variant variant self methodData methodData self order len self actions self gamma self gammaSets self notGamma self notGammaSets In both cases the digraph instance inheritates the objects and methods of the given performance tableau instance and all general outranking digraphs specific methods gathered under the abstract OutrankingDigraph class or namespace 8 3 The PerformanceTableau class The PerformanceTableau class handles decision problem datas such as decision actions and cri teria class PerformanceTableau __builtin__ object performanceTableau fileName of valid py code A general class for performance tableaus Methods defined here _init__ self filePerfTab testnewperftab computeWeightPreorder self renders the weight preorder following from the given criteria weights in a list of increasing equivalence lists of criteria save self fileName tempperftab Persistant storage of Performance Table
26. function R is implemented as a two dimensional Python dictionary object which allows efficient access to the charactistic value of a given arc x y via the call relation x y actions 1 2 3 4 5 valuationdomain min 10 0 med 0 0 max 10 0 relation 4 f 1 10 0 2 10 0 3 10 0 4 10 0 5 10 0 2 f 1 10 0 2 10 0 3 10 0 4 10 0 5 10 0 3 f 1 10 0 72 10 0 3 10 0 4 10 0 5 10 0 7A 1 10 0 2 10 0 3 10 0 4 10 0 5 10 0 7B 1 10 0 2 10 0 3 10 0 4 10 0 5 10 0 In the interactive Python session we may explore this example digraph as illustrated below gt gt gt g Digraph test testdigraph gt gt gt g actions Pea E PA PSF gt gt gt g valuationdomain med 0 max 10 0 min 10 0 gt gt gt g relation 1 1 10 0 3 10 0 2 10 0 5 10 0 4 10 3 ML 1 10 0 73 10 0 2 10 0 5 10 0 4 10 2 C 1 10 0 73 10 0 2 10 0 5 10 0 4 10 B C 1 10 0 73 10 0 2 10 0 5 10 0 4 10 A NL 1 10 0 73 10 0 2 10 0 5 10 0 4 10 POD Sis Please notice that the keys of the actions list are not in general alphanumerically ordered in the relation dictionary The
27. ime g computePreKernels print Execution time 5f seconds time time t0 Execution time 0 00015 seconds gt gt gt 3It might be important to start the Python session with the 0 flag in order to avoid the debugging overhead otherwise included by default The interactive timing results are in this latter case identical with direct batch running of the Python source code file 5 Solving a RUBIS decision aiding problem 5 1 The example choice decision problem Let us consider four decision actions A a b c d evaluated on a coherent family F C1 C2 C3 C4 C5 of five criteria of equal significance On each criterion we apply a prefer ence scale from 0 to 100 with an indifference threshold of 10 a preference threshold of 14 and a veto threshold of 50 The following performance tableau is given Table 1 Performance tableau actions C C2 C3 C4 Cs a 30 85 80 60 70 b 40 60 60 80 75 c 75 60 60 25 75 d 8 40 70 60 55 Based on the performance tableau 1 the decision maker is faced with the problem of choosing a single best decision action from A What could be a convincing choice recommendation 5 2 The example Python data file The previous data is gathered in the following Python file FOO OOOO III kkk I Example choice problem data B Roy du 4 novembre 2005 Filename samplePerformanceTableau py FOO OOOO IIIa IR A actions a b c d criteria 2G 1
28. lued digraphs instances following the standard model of random graphs 4 see Chapter 2 gt gt gt from digraphs import RandomDigraph gt gt gt g RandomDigraph order 10 arcProbability 0 20 gt gt gt g showStatistics k general statistics for digraph lt randomDigraph py gt order 10 nodes size 20 arcs undetermined 0 arcs determinateness 1 00 arc density 0 22 double arc density 0 02 single arc density 0 40 absence density 0 58 strict single arc density 0 40 strict absence density 0 58 components 2 1 strong components 6 transitivity degree 0 41 0 1 2 3 4 5 6 7 8 9 10 outdegrees distribution 1 3 4 0 1 1 0 0 O 0 0 indegrees distribution 1 3 2 3 1 0 0 0 0 0 OJ mean outdegree 2 00 mean indegree 2 00 lO iy 25 830450105 G Ti 8y 95 LON 11 12 13 14 15 16 17 18 19 20 symmetric degrees dist 0 1 0 3 0 6 0 0 0 0 0 0 0 0 O0 O O O O O OJ mean symmetric degree 4 00 outdegrees concentration index 0 3700 indegrees concentration index 0 3300 symdegrees concentration index 0 1650 0 1 2 5 neighbourhood depths distribution 0 0 4 6 0 0 mean neighbourhood depth 2 60 digraph diameter 7 3 agglomeration distribution 50 00 25 00 20 00 33 33 0 00 0 00 OonRWNKE 13 7 30 00 8 16 67 9 25 00 10 15 00 agglomeration coefficient 21 50 gt gt gt 1 Please note that
29. n to the Digraph class added computeWeightedAveragePerformances method to the Performanc migrate ranking rules to parent Digraph class added omax and omin operator to Digraph class instances added ExtendedPrudentDigraph class refactored VotingProfile and ApprovalVotingProfile Classes added normalizeEvaluations method to PerformanceTableau class added RandomTree Class and adapted exportGraphViz method fwith neato 24 Revision 1 533 introduced the omax operator with a Couceiro Grabisch rule for handling the non associativity Revision 1 532 added min max decoration on showPerformanceTable Revision 1 525 added robust Condorcet sorting Revision 1 524 added bipolar valued sorting characteristics to SortingDigraph Revision 1 522 SortingDigraph Class added orderedCategoryKeys method Revision 1 520 added SortingDigraph class for multiple criteria based sorting into ordered categories Revision 1 519 added actions correlation analysis Revision 1 514 abstract env paths for calmat and R subroutines Revision 1 511 added average covering index to OutrankingDigraph showAll Revision 1 510 added average covering index computation for a choice in a set of objects Revision 1 509 added coveringIndex computation to choices in Digraph instances Revision 1 504 added hasVeto flag default True to the Performanc eTableau saveX MCDA2 method Revision 1 502 debugged no thresholds situations Revision 1 500 refining showPairwiseC
30. ngDigraph perfTabs PerformanceTableau BipolarPreferenceDigraph BipolarOutrankingDigraph perfTabs PerformanceTableau EquiSignificanceMajorityOutrankingDigraph BipolarOutrankingDigraph perfTabs PerformanceTableau MedianBipolarOutrankingDigraph BipolarOutrankingDigraph perfTabs PerformanceTableau NewRobustOutrankingDigraph BipolarOutrankingDigraph perfTabs PerformanceTableau RandomBipolarQutrankingDigraph BipolarOutrankingDigraph perfTabs PerformanceTableau RandomOutrankingDigraph RobustOutrankingDigraph BipolarOutrankingDigraph perfTabs PerformanceTableau DissimilarityOutrankingDigraph OutrankingDigraph perfTabs PerformanceTableau Electre30utrankingDigraph OutrankingDigraph perfTabs PerformanceTableau 17 RandomElectre30utrankingDigraph Electre30utrankingDigraph perfTabs PerformanceTableau MultiCriteriaDissimilarityDigraph OutrankingDigraph perfTabs PerformanceTableau OrdinalOutrankingDigraph OutrankingDigraph perfTabs PerformanceTableau UnanimousOutrankingDigraph OutrankingDigraph perfTabs PerformanceTableau PolarisedDigraph PolarisedQutrankingDigraph PolarisedDigraph OutrankingDigraph perfTabs PerformanceTableau PreferenceDigraph Preorder RandomDigraph RandomFixedDegreeSequenceDigraph RandomFixedSizeDigraph RandomRegularDigraph RandomTournament RandomTree RandomValuationDigraph RandomWeakTournament StrongComponentsCollapsedDigraph SymmetricPartialDigraph WeakCocaDigraph XMCDA
31. omparison method Revision 1 499 added html output to showCriteriaCorrelationTable Revision 1 493 taking consistently into account missing evaluations in XMCDA2 conversion and back Revision 1 491 added html output to showPairwiseComparison method Revision 1 490 changed NoVeto flag to hasNoVetoFlag in OutrankingDigraph constructions Revision 1 481 added stringInput to XMCDA2PerformanceTableau constructor Revision 1 480 added beta law generator to Random and FullRandomPerformanceTableau generator Revision 1 476 added equivalent weightDistribution mode Revision 1 475 parametrized correctly RandomPerformanceTableau Revision 1 474 added htmlPerformaceTable rendering for D4 Revision 1 473 added isColored flag to htm RelationTable Revision 1 472 added htmlRelationTable generator Revision 1 470 xmcda2string problemText production Revision 1 468 added isMemoryMapped flag to saveXMCDA2 method for Perforamnc eTableau instances Revision 1 467 new RobustOutrankingDigraph class constructor e Revision 1 466 added EquiSignificanceMajorityDigraph class e Revision 1 462 added separated criteria weights and thresholds initialisation for XM CDA2PerformanceTableau files Revision 1 459 added extrme performances count to bipolar outranking digraph constructor The showRelationTable method has now a hasLPDDenotation Flag Revision 1 454 added MultiCriteriaDissimilarityDigraph class Revision 1 451 added Random and Round Gri
32. on of the RUBIS recommendation The performance tableau below shows indeed that this alternative is the only alternative that is performing at least as good as all the other remaining alternatives gt gt gt g showPerformanceTableau performance tableau criteria a p c d dS eG ee ee ee ee gt C_1 3 40 0 75 0 85 0 0 0 C_2 85 0 60 0 60 0 40 0 0 0 The discrimination thresholds observed on the family of criteria may be inspected with the showCriteria method of the BipolarOutrankingDigraph object g gt gt gt g showCriteria criteria Ci Scale 0 100 Weight 0 200 Threshold ind 10 00 0 00x percentile 0 33 Threshold veto 50 00 0 00x percentile 0 83 Threshold pref 14 00 0 00x percentile 0 33 Threshold weakveto 50 00 0 00x percentile 0 83 Cds 32 Scale 0 100 Weight 0 200 Threshold ind 10 00 0 00x percentile 0 167 Threshold veto 50 00 0 00x percentile 1 0 Threshold pref 14 00 0 00x percentile 0 167 Threshold weakveto 50 00 0 00x percentile 1 0 G23 Scale 0 100 Weight 0 200 Threshold ind 10 00 0 00x percentile 0 67 Threshold veto 50 00 0 00x percentile 1 0 Threshold pref 14 00 0 00x percentile 0 67 Threshold weakveto 50 00 0 00x percentile 1 0 Cg Scale 0 100 Weight 0 200 Threshold ind 10 00 0 00x percentile 0 167 Threshold veto 50
33. r saving and accessing digraph description under the XML standard of the Decision Deck project Given a Digraph class instance g we may generate a XMCDA 20 description as follows gt gt gt g saveXMCDA2 fileName sampleDigraph category general subcategory general author R Bisdorff reference Test XML implementation innn saving digraph in XML format File testdigraph xmcda saved gt gt gt rra T n this sense we are somehow compatible with the idea of simple digraphs similar to simple graphs 14 The category and subcategory are useful for spezialising the self showAl11 procedure when reading in a XML description The resulting XMCDA 2 0 description is stored in the sampleDigraph xml file you may inspect hereafter lt xml version 1 0 encoding UTF 8 gt lt xml stylesheet type text xsl href xmcda2Rubis xsl gt lt xmcda XMCDA xmlns xsi http www w3 org 2001 XMLSchema instance xsi schemaLocation http www decision deck org 2009 XMCDA 2 0 0 file XMCDA 2 0 0 xsd xmlns xmcda http www decision deck org 2009 XMCDA 2 0 0 gt lt projectReference id testdigraph name randomDigraph gt lt title gt Valued Digraph in XMCDA 2 0 format lt title gt lt user gt R Bisdorff lt user gt lt version gt Test XML implementation lt version gt lt projectReference gt lt alternatives mcdaConcept Digraph nodes gt lt description gt
34. represented as dictionaries and may be accessed via the gammaSets self and notGammaSets self methods gt gt gt g gammaSets 0 1 Gset 4 set 5 47 23 set 2 5 set 2 5 47 2 set 3 set 3 gt B set 1 3 set 3 4 2A set 1 3 5 set 1 gt gt gt g notGammaSets 01 set 3 2 5 set 3 27 73 set 1 47 set 1 2 set 1 5 47 set 1 5 47 5 set 2 4 set 1 2 A4 set 2 set 3 2 57 gt gt gt 2 Implementing a specific g notGammaSets method is necessary here because of the three folded bipolar characteristic function which in the presence of undetermined arcs doesn t allow to access the negation of a characterisation via simple complementation of arc sets as is natural to do in the classic Boolean bi valued setting Finally the connected components of a given digraph g may be computed and accessed as a list of sets of actions with the help of the g components method 12 gt gt gt g components set 1 es a 72 252 4 QOD oh 6 2 Working with random digraphs In order to experiment with various exploitation techniques of outranking graphs the digraphs module provides a random generator for bipolar 0 100 va
35. ribution 0 4 4 2 0 mean degree 1 80 neighbourhood depths distribution mean neighbourhood depth 2 80 digraph diameter 4 agglomeration distribution 1 50 00 2 0 00 3 16 67 4 50 00 5 50 00 agglomeration coefficient 33 33 gt gt gt Similarly computing all dominant and absorbent kernels in the same digraph testdigraph py for instance is immediate via the Digraph showPreKernels method gt gt gt g showPreKernels Computing preKernels Dominant preKernels Pi 432 independence 10 dominance 10 absorbency 10 its ear independence 10 dominance 10 absorbency 10 Absorbent preKernels ie eee independence 10 dominance 10 absorbency 10 ete 2 independence 10 dominance Z 210 absorbency 10 statistics graph name testdigraph number of solutions dominant kernels 2 absorbent kernels 2 cardinality frequency distributions cardinality 0 1 2 3 4 5 dominant kernel 0 0 2 0 0 OJ absorbent kernel 0 0 2 O O 0 Execution time 0 00013 sec Results in sets dompreKernels and abspreKernels gt gt gt print g dompreKernels set frozenset 1 3 frozenset 2 4 gt gt gt print g abspreKernels set frozenset 1 3 frozenset 1 2 gt gt gt Timing such a result is straight forward too in interactive Python 3 gt gt gt import time gt gt gt tO time t
36. sys argv 3 fo open fileoutName w fo write Random Digraphs Statistics n fo write sample 4s arc probability s n sample arcProbability fo write order size undeterm dgini double single absence n for i in range sample print i i sorder random randint 10 31 g RandomDigraph sorder arcProbability concentDegrees g computeConcentrationIndex range g order list g outDegreesDistribution print sorder sorder size undeterm arcDensity g sizeSubGraph g actions density g computeAllDensities g actions fo write d wd fd 2 3f 2 3f 2 3f 2 3f n sorder size undeterm concentDegrees 23 density double density single density absence fo close The resulting comma separated data file densitytest csv may be easily explored with gretl or the statistical package R for instance 10 Version comments Features to come e Extension to undirected grpahs Release 1 6 Provided features Revision 1 675 tance methods Revision 1 674 added deprecating warnings for the old bipolar Kendall correlation and dis added CoceDigraph class for generating chordless odd circuits eliminated digraph instances Revision 1 668 Revision 1 667 Revision 1 662 Revision 1 636 Revision 1 634 Revision 1 632 Revision 1 631 Revision 1 624 Revision 1 613 Revision 1 613 Revision 1 608 Revision 1 597
37. t will be possible to run the file directly from the command line with HOME Digraph digraphs py lt filename gt A valid digraph specification file may be given as optional argument Try digraphs py for usage instructions It may be necessary to adapt the Python version in the first line 2To make directly executable the Python code source you will have to adapt the case given the first line of the source code accordingly to the location of your Python 2 5 or 2 4 installation directory See the Python documentation pages in case of troubles This is free software and you are welcome to redistribute it if it remains free software FEA AAA I 3K K K k ak ak ak K 3K 3K 3K I A A K K A I I KK 21 21 21 2 3K K K KK K K koce Testing classes and methods gt gt Testing RandomDigraph class instantiation x show detail Digraph randomDigraph Actions Ded ADP Be As T Characteristic valuation domain med Decimal 0 5 min Decimal 0 max Decimal 1 0 Relation Table S pr PA PDP Stas A BI Seen iPoeeesncet abate oe el ate eee he fee eee gt 4 0 00 0 00 0 00 1 00 0 00 2 0 00 0 00 1 00 1 00 1 00 73 1 00 1 00 0 00 1 00 1 00 4 0 00 1 00 1 00 0 00 1 00 75 0 00 1 00 0 00 0 00 0 00 Connected Components ee Pe 0 8 AA Be Neighborhoods Neighborhoods Gamma 1 in gt set 3 out
38. uation domain dictionary and a relation dictionary The constructor adds to these three basic information a list of precomputed data such as the name and the order of the digraph the dominated neighbours gamma the dominating neighbours notgamma If available digraph automorphism generators are added to the digraph object def __init__ self file None import digraphs sys copy if file None g digraphs RandomValuationDigraph order 9 self name g name self actions copy deepcopy g actions self order len self actions self valuationdomain copy deepcopy g valuationdomain self relation copy deepcopy g relation self gamma self gammaSets self notGamma self notGammaSets else fileName filet py execfile fileName self name file self actions locals actionset self order len self actions self valuationdomain locals valuationdomain self relation locals relation self gamma self gammaSets self notGamma self notGammaSets try self reflections locals reflections self rotations locals rotations except pass All other digraph classes are specializations of this initial Digraph class The CompleteDigraph or the EmptyDigraph class give access to such instances of given order To discover the full features of these classes it is useful and instructive to look at the source code of the digraphs module A special test part at the end of
Download Pdf Manuals
Related Search