RankedPairs_Core::makeArcs() - Code Metrics - julien-boudry/Condorcet - Measure and Improve Code Quality continuously with Scrutinizer

RankedPairs_Core::makeArcs() B
last analyzed 2019-08-30 22:36 UTC

↳ Parent: RankedPairs_Core

Complexity

Conditions	7
Paths	13

Size

Total Lines

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	16
CRAP Score	7

Importance

Changes

Metric	Value
cc	7
nc	13
nop	0
dl	0
loc	27
rs	8.5546
c	0
b	0
f	0
ccs	16
cts	16
cp	1
crap	7

<?php
/*
    Part of RANKED PAIRS method Module - From the original Condorcet PHP

    Condorcet PHP - Election manager and results calculator.
    Designed for the Condorcet method. Integrating a large number of algorithms extending Condorcet. Expandable for all types of voting systems.

    By Julien Boudry and contributors - MIT LICENSE (Please read LICENSE.txt)
    https://github.com/julien-boudry/Condorcet
*/
declare(strict_types=1);

namespace CondorcetPHP\Condorcet\Algo\Methods\RankedPairs;

use CondorcetPHP\Condorcet\Result;
use CondorcetPHP\Condorcet\Algo\{Method, MethodInterface};

// Ranker Pairs is a Condorcet Algorithm | http://en.wikipedia.org/wiki/Ranked_Pairs
class RankedPairs_Core extends Method implements MethodInterface
{
    // Limits
        public static $MaxCandidates = 40;

    // Ranked Pairs
    protected $_PairwiseSort;
    protected $_Arcs;
    protected $_Stats;
    protected $_StatsDone = false;


/////////// PUBLIC ///////////


    // Get the Ranked Pairs ranking
    public function getResult () : Result
    {
        // Cache
        if ( $this->_Result !== null ) :
            return $this->_Result;
        endif;

            //////

        // Sort pairwise
        $this->_PairwiseSort = $this->pairwiseSort();

        // Ranking calculation
        $this->makeArcs();

        // Make Stats
        $this->_Stats['tally'] = $this->_PairwiseSort;
        $this->_Stats['arcs'] = $this->_Arcs;

        // Make Result      
        return $this->_Result = $this->createResult($this->makeResult());
    }

    // Get the Ranked Pair ranking
    protected function getStats () : array
    {
        if (!$this->_StatsDone) :
            foreach ($this->_Stats['tally'] as &$Roundvalue) :
                foreach ($Roundvalue as $ArcKey => &$Arcvalue) :
                    foreach ($Arcvalue as $key => &$value) :
                        if ($key === 'from' || $key === 'to') :
                            $value = $this->_selfElection->getCandidateObjectFromKey($value)->getName();
                        endif;
                    endforeach;
                endforeach;
            endforeach;

            foreach ($this->_Stats['arcs'] as $ArcKey => &$Arcvalue) :
                foreach ($Arcvalue as $key => &$value) :
                    if ($key === 'from' || $key === 'to') :
                        $value = $this->_selfElection->getCandidateObjectFromKey($value)->getName();
                    endif;
                endforeach;
            endforeach;

            $this->_StatsDone = true;
        endif;

        return $this->_Stats;
    }


/////////// COMPUTE ///////////


    //:: RANKED PAIRS ALGORITHM. :://

    protected function makeResult () : array
    {
        $result = [];
        $alreadyDone = [];

        $rang = 1;
        while (count($alreadyDone) < $this->_selfElection->countCandidates()) :
            $winners = $this->getWinners($alreadyDone);

            foreach ($this->_Arcs as $ArcKey => $Arcvalue) :
                foreach ($winners as $oneWinner) :
                    if ($Arcvalue['from'] === $oneWinner || $Arcvalue['to'] === $oneWinner ) :
                        unset($this->_Arcs[$ArcKey]);
                    endif;
                endforeach;
            endforeach;

            $result[$rang++] = $winners;
            $alreadyDone = array_merge($alreadyDone,$winners);
        endwhile;

        return $result;
    }

    protected function getWinners (array $alreadyDone) : array
    {
        $winners = [];

        foreach ($this->_selfElection->getCandidatesList() as $candidateKey => $candidateId) :
            if (!in_array($candidateKey, $alreadyDone, true)) :
                $win = true;
                foreach ($this->_Arcs as $ArcKey => $ArcValue) :
                    if ($ArcValue['to'] === $candidateKey) :
                        $win = false;
                    endif;
                endforeach;

                if ($win) :
                    $winners[] = $candidateKey;
                endif;
            endif;
        endforeach;

        return $winners;
    }


    protected function makeArcs () : void
    {
        $this->_Arcs = [];

        foreach ($this->_PairwiseSort as $newArcsRound) :
            $virtualArcs = $this->_Arcs;
            $testNewsArcs = [];

            $newKey = max((empty($highKey = array_keys($virtualArcs)) ? [-1] : $highKey)) + 1;
            foreach ($newArcsRound as $newArc) :
                $virtualArcs[$newKey] = [ 'from' => $newArc['from'], 'to' => $newArc['to'] ];
                $testNewsArcs[$newKey] = $virtualArcs[$newKey];
                $newKey++;
            endforeach;

            foreach ($this->getArcsInCycle($virtualArcs) as $cycleArcKey) :
                if (array_key_exists($cycleArcKey, $testNewsArcs)) :
                    unset($testNewsArcs[$cycleArcKey]);
                endif;
            endforeach;

            foreach ($testNewsArcs as $newArc) :
                $this->_Arcs[] = $newArc;
            endforeach;

        endforeach;
    }

    protected function getArcsInCycle (array $virtualArcs) : array
    {
        $cycles = [];

        foreach ($this->_selfElection->getCandidatesList() as $candidateKey => $candidateId) :
            $cycles = array_merge($cycles,$this->followCycle($virtualArcs,$candidateKey,$candidateKey));
        endforeach;

        return $cycles;
    }

    protected function followCycle (array $virtualArcs, int $startCandidateKey, int $searchCandidateKey, array &$done = [])
    {
        $arcsInCycle = [];

        foreach ($virtualArcs as $ArcKey => $ArcValue) :
            if ($ArcValue['from'] === $startCandidateKey) :
                if (in_array($ArcKey, $done, true)) :
                    continue;
                elseif ($ArcValue['to'] === $searchCandidateKey) :
                    $done[] = $ArcKey;
                    $arcsInCycle[] = $ArcKey;
                else :
                    $done[] = $ArcKey;
                    $arcsInCycle = array_merge($arcsInCycle,$this->followCycle($virtualArcs,$ArcValue['to'],$searchCandidateKey, $done));
                endif;
            endif;
        endforeach;

        return $arcsInCycle;
    }

    protected function pairwiseSort () : array
    {
        $pairs = [];  

        $i = 0;
        foreach ($this->_selfElection->getPairwise() as $candidate_key => $candidate_value) :
            foreach ($candidate_value['win'] as $challenger_key => $challenger_value) :

                if ($challenger_value > $candidate_value['lose'][$challenger_key]) :

                    // Victory
                    $pairs[$i]['from'] = $candidate_key;
                    // Defeat
                    $pairs[$i]['to'] = $challenger_key;

                    $pairs[$i]['win'] = $challenger_value;
                    $pairs[$i]['minority'] = $candidate_value['lose'][$challenger_key];
                    $pairs[$i]['margin'] = $candidate_value['win'][$challenger_key] - $candidate_value['lose'][$challenger_key];

                    $i++;

                endif;

            endforeach;
        endforeach;

        usort($pairs, function (array $a, array $b) : int {
            if ($a[static::RP_VARIANT_1] < $b[static::RP_VARIANT_1]) :
                return 1;
            elseif ($a[static::RP_VARIANT_1] > $b[static::RP_VARIANT_1]) :
                return -1;
            else : // Equal
                return $a['minority'] <=> $b['minority'];
            endif;
        });

        $newArcs = [];
        $i = 0;
        $f = true;
        foreach ($pairs as $pairsKey => $pairsValue) :
            if ($f === true) :
                $newArcs[$i][] = $pairs[$pairsKey];
                $f = false;
            elseif ($pairs[$pairsKey][static::RP_VARIANT_1] === $pairs[$pairsKey - 1][static::RP_VARIANT_1] && $pairs[$pairsKey]['minority'] === $pairs[$pairsKey - 1]['minority']) :
                $newArcs[$i][] = $pairs[$pairsKey];
            else :
                $newArcs[++$i][] = $pairs[$pairsKey];
            endif;
        endforeach;

        return $newArcs;
    }
}


1			<?php
2			/*
3			Part of RANKED PAIRS method Module - From the original Condorcet PHP
4
5			Condorcet PHP - Election manager and results calculator.
6			Designed for the Condorcet method. Integrating a large number of algorithms extending Condorcet. Expandable for all types of voting systems.
7
8			By Julien Boudry and contributors - MIT LICENSE (Please read LICENSE.txt)
9			https://github.com/julien-boudry/Condorcet
10			*/
11			declare(strict_types=1);
12
13			namespace CondorcetPHP\Condorcet\Algo\Methods\RankedPairs;
14
15			use CondorcetPHP\Condorcet\Result;
16			use CondorcetPHP\Condorcet\Algo\{Method, MethodInterface};
17
18			// Ranker Pairs is a Condorcet Algorithm \| http://en.wikipedia.org/wiki/Ranked_Pairs
19			class RankedPairs_Core extends Method implements MethodInterface
20			{
21			// Limits
22			public static $MaxCandidates = 40;
23
24			// Ranked Pairs
25			protected $_PairwiseSort;
26			protected $_Arcs;
27			protected $_Stats;
28			protected $_StatsDone = false;
29
30
31			/////////// PUBLIC ///////////
32
33
34			// Get the Ranked Pairs ranking
35	19		public function getResult () : Result
36			{
37			// Cache
38	19		if ( $this->_Result !== null ) :
39	7		return $this->_Result;
40			endif;
41
42			//////
43
44			// Sort pairwise
45	19		$this->_PairwiseSort = $this->pairwiseSort();
46
47			// Ranking calculation
48	19		$this->makeArcs();
49
50			// Make Stats
51	19		$this->_Stats['tally'] = $this->_PairwiseSort;
52	19		$this->_Stats['arcs'] = $this->_Arcs;
53
54			// Make Result
55	19		return $this->_Result = $this->createResult($this->makeResult());
56			}
57
58			// Get the Ranked Pair ranking
59	19		protected function getStats () : array
60			{
61	19		if (!$this->_StatsDone) :
62	19	View Code Duplication	foreach ($this->_Stats['tally'] as &$Roundvalue) :
63	19		foreach ($Roundvalue as $ArcKey => &$Arcvalue) :
64	19		foreach ($Arcvalue as $key => &$value) :
65	19		if ($key === 'from' \|\| $key === 'to') :
66	19		$value = $this->_selfElection->getCandidateObjectFromKey($value)->getName();
67			endif;
68			endforeach;
69			endforeach;
70			endforeach;
71
72	19	View Code Duplication	foreach ($this->_Stats['arcs'] as $ArcKey => &$Arcvalue) :
73	19		foreach ($Arcvalue as $key => &$value) :
74	19		if ($key === 'from' \|\| $key === 'to') :
75	19		$value = $this->_selfElection->getCandidateObjectFromKey($value)->getName();
76			endif;
77			endforeach;
78			endforeach;
79
80	19		$this->_StatsDone = true;
81			endif;
82
83	19		return $this->_Stats;
84			}
85
86
87			/////////// COMPUTE ///////////
88
89
90			//:: RANKED PAIRS ALGORITHM. :://
91
92	19		protected function makeResult () : array
93			{
94	19		$result = [];
95	19		$alreadyDone = [];
96
97	19		$rang = 1;
98	19		while (count($alreadyDone) < $this->_selfElection->countCandidates()) :
99	19		$winners = $this->getWinners($alreadyDone);
100
101	19		foreach ($this->_Arcs as $ArcKey => $Arcvalue) :
102	19		foreach ($winners as $oneWinner) :
103	19		if ($Arcvalue['from'] === $oneWinner \|\| $Arcvalue['to'] === $oneWinner ) :
104	19		unset($this->_Arcs[$ArcKey]);
105			endif;
106			endforeach;
107			endforeach;
108
109	19		$result[$rang++] = $winners;
110	19		$alreadyDone = array_merge($alreadyDone,$winners);
111			endwhile;
112
113	19		return $result;
114			}
115
116	19		protected function getWinners (array $alreadyDone) : array
117			{
118	19		$winners = [];
119
120	19		foreach ($this->_selfElection->getCandidatesList() as $candidateKey => $candidateId) :
121	19		if (!in_array($candidateKey, $alreadyDone, true)) :
122	19		$win = true;
123	19		foreach ($this->_Arcs as $ArcKey => $ArcValue) :
124	19		if ($ArcValue['to'] === $candidateKey) :
125	19		$win = false;
126			endif;
127			endforeach;
128
129	19		if ($win) :
130	19		$winners[] = $candidateKey;
131			endif;
132			endif;
133			endforeach;
134
135	19		return $winners;
136			}
137
138
139	19		protected function makeArcs () : void
140			{
141	19		$this->_Arcs = [];
142
143	19		foreach ($this->_PairwiseSort as $newArcsRound) :
144	19		$virtualArcs = $this->_Arcs;
145	19		$testNewsArcs = [];
146
147	19		$newKey = max((empty($highKey = array_keys($virtualArcs)) ? [-1] : $highKey)) + 1;
148	19		foreach ($newArcsRound as $newArc) :
149	19		$virtualArcs[$newKey] = [ 'from' => $newArc['from'], 'to' => $newArc['to'] ];
150	19		$testNewsArcs[$newKey] = $virtualArcs[$newKey];
151	19		$newKey++;
152			endforeach;
153
154	19		foreach ($this->getArcsInCycle($virtualArcs) as $cycleArcKey) :
155	10		if (array_key_exists($cycleArcKey, $testNewsArcs)) :
156	10		unset($testNewsArcs[$cycleArcKey]);
157			endif;
158			endforeach;
159
160	19		foreach ($testNewsArcs as $newArc) :
161	19		$this->_Arcs[] = $newArc;
162			endforeach;
163
164			endforeach;
165	19		}
166
167	19		protected function getArcsInCycle (array $virtualArcs) : array
168			{
169	19		$cycles = [];
170
171	19		foreach ($this->_selfElection->getCandidatesList() as $candidateKey => $candidateId) :
172	19		$cycles = array_merge($cycles,$this->followCycle($virtualArcs,$candidateKey,$candidateKey));
173			endforeach;
174
175	19		return $cycles;
176			}
177
178	19		protected function followCycle (array $virtualArcs, int $startCandidateKey, int $searchCandidateKey, array &$done = [])
179			{
180	19		$arcsInCycle = [];
181
182	19		foreach ($virtualArcs as $ArcKey => $ArcValue) :
183	19		if ($ArcValue['from'] === $startCandidateKey) :
184	19		if (in_array($ArcKey, $done, true)) :
185	7		continue;
186	19		elseif ($ArcValue['to'] === $searchCandidateKey) :
187	10		$done[] = $ArcKey;
188	10		$arcsInCycle[] = $ArcKey;
189			else :
190	19		$done[] = $ArcKey;
191	19		$arcsInCycle = array_merge($arcsInCycle,$this->followCycle($virtualArcs,$ArcValue['to'],$searchCandidateKey, $done));
192			endif;
193			endif;
194			endforeach;
195
196	19		return $arcsInCycle;
197			}
198
199	19		protected function pairwiseSort () : array
200			{
201	19		$pairs = [];
202
203	19		$i = 0;
204	19		foreach ($this->_selfElection->getPairwise() as $candidate_key => $candidate_value) :
205	19		foreach ($candidate_value['win'] as $challenger_key => $challenger_value) :
206
207	19		if ($challenger_value > $candidate_value['lose'][$challenger_key]) :
208
209			// Victory
210	19		$pairs[$i]['from'] = $candidate_key;
211			// Defeat
212	19		$pairs[$i]['to'] = $challenger_key;
213
214	19		$pairs[$i]['win'] = $challenger_value;
215	19		$pairs[$i]['minority'] = $candidate_value['lose'][$challenger_key];
216	19		$pairs[$i]['margin'] = $candidate_value['win'][$challenger_key] - $candidate_value['lose'][$challenger_key];
217
218	19		$i++;
219
220			endif;
221
222			endforeach;
223			endforeach;
224
225			usort($pairs, function (array $a, array $b) : int {
226	19		if ($a[static::RP_VARIANT_1] < $b[static::RP_VARIANT_1]) :
227	12		return 1;
228	19		elseif ($a[static::RP_VARIANT_1] > $b[static::RP_VARIANT_1]) :
229	11		return -1;
230			else : // Equal
231	12		return $a['minority'] <=> $b['minority'];
232			endif;
233	19		});
234
235	19		$newArcs = [];
236	19		$i = 0;
237	19		$f = true;
238	19		foreach ($pairs as $pairsKey => $pairsValue) :
239	19		if ($f === true) :
240	19		$newArcs[$i][] = $pairs[$pairsKey];
241	19		$f = false;
242	19		elseif ($pairs[$pairsKey][static::RP_VARIANT_1] === $pairs[$pairsKey - 1][static::RP_VARIANT_1] && $pairs[$pairsKey]['minority'] === $pairs[$pairsKey - 1]['minority']) :
243	12		$newArcs[$i][] = $pairs[$pairsKey];
244			else :
245	19		$newArcs[++$i][] = $pairs[$pairsKey];
246			endif;
247			endforeach;
248
249	19		return $newArcs;
250			}
251			}
252

julien-boudry / Condorcet

RankedPairs_Core::makeArcs() B last analyzed 2019-08-30 22:36 UTC

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like

RankedPairs_Core::makeArcs() B
last analyzed 2019-08-30 22:36 UTC