ChineseWhispers::find_neighbor_ranges() - Code Metrics - Inspection of "Implement the Chinese Whispers clustering algorith..." - matiasdelellis/facerecognition - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Pull Request — master (#691)

by Matias

created 2023-08-22 23:28 UTC

ChineseWhispers::find_neighbor_ranges() A

↳ Parent: ChineseWhispers

Complexity

Conditions	5
Paths	12

Size

Total Lines	18
Code Lines	11

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	9
CRAP Score	5.3906

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	5
eloc	11
c	1
b	0
f	0
nc	12
nop	2
dl	0
loc	18
ccs	9
cts	12
cp	0.75
crap	5.3906
rs	9.6111

<?php
declare(strict_types=1);
/**
 * @copyright Copyright (c) 2023, Matias De lellis
 *
 * @author Matias De lellis <[email protected]>
 *
 * @license AGPL-3.0-or-later
 *
 * This code is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License, version 3,
 * as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License, version 3,
 * along with this program. If not, see <http://www.gnu.org/licenses/>
 *
 */

namespace OCA\FaceRecognition\Clusterer;


/**
 * This class implements the graph clustering algorithm described in the
 * paper: Chinese Whispers - an Efficient Graph Clustering Algorithm and its
 * Application to Natural Language Processing Problems by Chris Biemann.
 *
 * In particular, it tries to be a shameless copy of the original dlib
 * implementation.
 *  - https://github.com/davisking/dlib/blob/master/dlib/clustering/chinese_whispers.h
 */
class ChineseWhispers {

	/**
	 * Cluster the dataset by assigning a label to each sample.from the edges
	 */
	static public function predict(array &$edges, array &$labels, int $num_iterations = 100)
	{
		$labels = [];
		if (count($edges) == 0)
			return 0;

		$neighbors = [];
		self::find_neighbor_ranges($edges, $neighbors);

		// Initialize the labels, each node gets a different label.
		for ($i = 0; $i < count($neighbors); ++$i)
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
			$labels[$i] = $i;

		for ($iter = 0; $iter < count($neighbors)*$num_iterations; ++$iter)
		{
			// Pick a random node.
			$idx = random_int(0, count($neighbors) - 1);

			// Count how many times each label happens amongst our neighbors.
			$labels_to_counts = [];
			$end = $neighbors[$idx][1];

			for ($i = $neighbors[$idx][0]; $i != $end; ++$i)
			{
				$iLabelFirst = $edges[$i][1];
				$iLabel = $labels[$iLabelFirst];
				if (isset($labels_to_counts[$iLabel]))
					$labels_to_counts[$iLabel]++;
				else
					$labels_to_counts[$iLabel] = 1;
			}

			// find the most common label
			// std::map<unsigned long, double>::iterator i;
			$best_score = PHP_INT_MIN;
			$best_label = $labels[$idx];
			foreach ($labels_to_counts as $key => $value)
			{
				if ($value > $best_score)
				{
					$best_score = $value;
					$best_label = $key;
				}
			}

			$labels[$idx] = $best_label;
		}

		// Remap the labels into a contiguous range.  First we find the
		// mapping.
		$label_remap = [];
		for ($i = 0; $i < count($labels); ++$i)
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
		{
			$next_id = count($label_remap);
			if (!isset($label_remap[$labels[$i]]))
				$label_remap[$labels[$i]] = $next_id;
		}
		// now apply the mapping to all the labels.
		for ($i = 0; $i < count($labels); ++$i)
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
		{
			$labels[$i] = $label_remap[$labels[$i]];
		}

		return count($label_remap);
	}

	static function find_neighbor_ranges (&$edges, &$neighbors) {

		// setup neighbors so that [neighbors[i].first, neighbors[i].second) is the range
		// within edges that contains all node i's edges.
		$num_nodes = self::max_index_plus_one($edges);
		for ($i = 0; $i < $num_nodes; ++$i) $neighbors[$i] = [0, 0];
		$cur_node = 0;
		$start_idx = 0;
		for ($i = 0; $i < count($edges); ++$i)
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
		{
			if ($edges[$i][0] != $cur_node)
			{
				$neighbors[$cur_node] = [$start_idx, $i];
				$start_idx = $i;
				$cur_node = $edges[$i][0];
			}
		}
		if (count($neighbors) !== 0)
			$neighbors[$cur_node] = [$start_idx, count($edges)];
	}

	static function max_index_plus_one ($pairs): int {

		if (count($pairs) === 0)
		{
			return 0;
		}
		else {
			$max_idx = 0;
			for ($i = 0; $i < count($pairs); ++$i)
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
			{
				if ($pairs[$i][0] > $max_idx)
					$max_idx = $pairs[$i][0];
				if ($pairs[$i][1] > $max_idx)
					$max_idx = $pairs[$i][1];
			}
			return $max_idx + 1;
		}
	}

	static function convert_unordered_to_ordered (&$edges, &$out_edges)

	{
		$out_edges = [];
		for ($i = 0; $i < count($edges); ++$i)
for ($i=0; $i<count($array); $i++) { // calls count() on each iteration
}

// Better
for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once
}
		{
			$out_edges[] = [$edges[$i][0], $edges[$i][1]];
			if ($edges[$i][0] != $edges[$i][1])
				$out_edges[] = [$edges[$i][1], $edges[$i][0]];
		}
	}
}


1		<?php
2		declare(strict_types=1);
3		/**
4		* @copyright Copyright (c) 2023, Matias De lellis
5		*
6		* @author Matias De lellis <[email protected]>
7		*
8		* @license AGPL-3.0-or-later
9		*
10		* This code is free software: you can redistribute it and/or modify
11		* it under the terms of the GNU Affero General Public License, version 3,
12		* as published by the Free Software Foundation.
13		*
14		* This program is distributed in the hope that it will be useful,
15		* but WITHOUT ANY WARRANTY; without even the implied warranty of
16		* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17		* GNU Affero General Public License for more details.
18		*
19		* You should have received a copy of the GNU Affero General Public License, version 3,
20		* along with this program. If not, see <http://www.gnu.org/licenses/>
21		*
22		*/
23
24		namespace OCA\FaceRecognition\Clusterer;
25
26
27		/**
28		* This class implements the graph clustering algorithm described in the
29		* paper: Chinese Whispers - an Efficient Graph Clustering Algorithm and its
30		* Application to Natural Language Processing Problems by Chris Biemann.
31		*
32		* In particular, it tries to be a shameless copy of the original dlib
33		* implementation.
34		* - https://github.com/davisking/dlib/blob/master/dlib/clustering/chinese_whispers.h
35		*/
36		class ChineseWhispers {
37
38		/**
39		* Cluster the dataset by assigning a label to each sample.from the edges
40		*/
41	1	static public function predict(array &$edges, array &$labels, int $num_iterations = 100)
42		{
43	1	$labels = [];
44	1	if (count($edges) == 0)
45		return 0;
46
47	1	$neighbors = [];
48	1	self::find_neighbor_ranges($edges, $neighbors);
49
50		// Initialize the labels, each node gets a different label.
51	1	for ($i = 0; $i < count($neighbors); ++$i)
		0 ignored issues – show Performance Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
52	1	$labels[$i] = $i;
53
54	1	for ($iter = 0; $iter < count($neighbors)*$num_iterations; ++$iter)
55		{
56		// Pick a random node.
57	1	$idx = random_int(0, count($neighbors) - 1);
58
59		// Count how many times each label happens amongst our neighbors.
60	1	$labels_to_counts = [];
61	1	$end = $neighbors[$idx][1];
62
63	1	for ($i = $neighbors[$idx][0]; $i != $end; ++$i)
64		{
65	1	$iLabelFirst = $edges[$i][1];
66	1	$iLabel = $labels[$iLabelFirst];
67	1	if (isset($labels_to_counts[$iLabel]))
68		$labels_to_counts[$iLabel]++;
69		else
70	1	$labels_to_counts[$iLabel] = 1;
71		}
72
73		// find the most common label
74		// std::map<unsigned long, double>::iterator i;
75	1	$best_score = PHP_INT_MIN;
76	1	$best_label = $labels[$idx];
77	1	foreach ($labels_to_counts as $key => $value)
78		{
79	1	if ($value > $best_score)
80		{
81	1	$best_score = $value;
82	1	$best_label = $key;
83		}
84		}
85
86	1	$labels[$idx] = $best_label;
87		}
88
89		// Remap the labels into a contiguous range. First we find the
90		// mapping.
91	1	$label_remap = [];
92	1	for ($i = 0; $i < count($labels); ++$i)
		0 ignored issues – show Performance Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
93		{
94	1	$next_id = count($label_remap);
95	1	if (!isset($label_remap[$labels[$i]]))
96	1	$label_remap[$labels[$i]] = $next_id;
97		}
98		// now apply the mapping to all the labels.
99	1	for ($i = 0; $i < count($labels); ++$i)
		0 ignored issues – show Performance Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
100		{
101	1	$labels[$i] = $label_remap[$labels[$i]];
102		}
103
104	1	return count($label_remap);
105		}
106
107	1	static function find_neighbor_ranges (&$edges, &$neighbors) {
		0 ignored issues – show Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It is generally recommended to explicitly declare the visibility for methods. Adding explicit visibility (`private`, `protected`, or `public`) is generally recommend to communicate to other developers how, and from where this method is intended to be used. Loading history...
108		// setup neighbors so that [neighbors[i].first, neighbors[i].second) is the range
109		// within edges that contains all node i's edges.
110	1	$num_nodes = self::max_index_plus_one($edges);
111	1	for ($i = 0; $i < $num_nodes; ++$i) $neighbors[$i] = [0, 0];
112	1	$cur_node = 0;
113	1	$start_idx = 0;
114	1	for ($i = 0; $i < count($edges); ++$i)
		0 ignored issues – show Performance Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
115		{
116	1	if ($edges[$i][0] != $cur_node)
117		{
118		$neighbors[$cur_node] = [$start_idx, $i];
119		$start_idx = $i;
120		$cur_node = $edges[$i][0];
121		}
122		}
123	1	if (count($neighbors) !== 0)
124	1	$neighbors[$cur_node] = [$start_idx, count($edges)];
125		}
126
127	1	static function max_index_plus_one ($pairs): int {
		0 ignored issues – show Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It is generally recommended to explicitly declare the visibility for methods. Adding explicit visibility (`private`, `protected`, or `public`) is generally recommend to communicate to other developers how, and from where this method is intended to be used. Loading history...
128	1	if (count($pairs) === 0)
129		{
130		return 0;
131		}
132		else {
133	1	$max_idx = 0;
134	1	for ($i = 0; $i < count($pairs); ++$i)
		0 ignored issues – show Performance Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
135		{
136	1	if ($pairs[$i][0] > $max_idx)
137		$max_idx = $pairs[$i][0];
138	1	if ($pairs[$i][1] > $max_idx)
139		$max_idx = $pairs[$i][1];
140		}
141	1	return $max_idx + 1;
142		}
143		}
144
145	1	static function convert_unordered_to_ordered (&$edges, &$out_edges)
		0 ignored issues – show Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It is generally recommended to explicitly declare the visibility for methods. Adding explicit visibility (`private`, `protected`, or `public`) is generally recommend to communicate to other developers how, and from where this method is intended to be used. Loading history...
146		{
147	1	$out_edges = [];
148	1	for ($i = 0; $i < count($edges); ++$i)
		0 ignored issues – show Performance Best Practice introduced 2023-08-22 23:32 UTC by Report Bug Copy Issue Report It seems like you are calling the size function `count()` as part of the test condition. You might want to compute the size beforehand, and not on each iteration. If the size of the collection does not change during the iteration, it is generally a good practice to compute it beforehand, and not on each iteration: for ($i=0; $i<count($array); $i++) { // calls count() on each iteration } // Better for ($i=0, $c=count($array); $i<$c; $i++) { // calls count() just once } Loading history...
149		{
150	1	$out_edges[] = [$edges[$i][0], $edges[$i][1]];
151	1	if ($edges[$i][0] != $edges[$i][1])
152		$out_edges[] = [$edges[$i][1], $edges[$i][0]];
153		}
154		}
155		}
156

matiasdelellis / facerecognition

Pull Request — master (#691)

ChineseWhispers::find_neighbor_ranges() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like