88 lines
2.1 KiB
PHP
88 lines
2.1 KiB
PHP
|
<?php
|
||
|
|
|
||
|
|
namespace Graphp\Algorithms;
|
||
|
|
|
||
|
|
use Graphp\Algorithms\BaseGraph;
|
||
|
|
use Fhaculty\Graph\Graph;
|
||
|
|
use Fhaculty\Graph\Set\Vertices;
|
||
|
|
|
||
|
|
class Groups extends BaseGraph
|
||
|
|
{
|
||
|
|
/**
|
||
|
|
* count total number of different groups assigned to vertices
|
||
|
|
*
|
||
|
|
* @return int
|
||
|
|
* @uses AlgorithmGroups::getGroups()
|
||
|
|
*/
|
||
|
|
public function getNumberOfGroups()
|
||
|
|
{
|
||
|
|
return count($this->getGroups());
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* checks whether the input graph's vertex groups are a valid bipartition
|
||
|
|
*
|
||
|
|
* @return boolean
|
||
|
|
* @see AlgorithmBipartit() if you do NOT want to take vertex groups into consideration
|
||
|
|
* @uses AlgorithmGroups::getNumberOfGroups()
|
||
|
|
* @uses Vertex::getGroup()
|
||
|
|
*/
|
||
|
|
public function isBipartit()
|
||
|
|
{
|
||
|
|
// graph has to contain exactly 2 groups
|
||
|
|
if ($this->getNumberOfGroups() !== 2) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
|
||
|
|
// for each vertex
|
||
|
|
foreach ($this->graph->getVertices() as $vertex) {
|
||
|
|
// get current group
|
||
|
|
$group = $vertex->getGroup();
|
||
|
|
// for every neighbor vertex
|
||
|
|
foreach ($vertex->getVerticesEdge() as $vertexNeighbor) {
|
||
|
|
// vertex group must be other group
|
||
|
|
if ($vertexNeighbor->getGroup() === $group) {
|
||
|
|
return false;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return true;
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* get vector of all group numbers
|
||
|
|
*
|
||
|
|
* @return int[]
|
||
|
|
* @uses Vertex::getGroup()
|
||
|
|
*/
|
||
|
|
public function getGroups()
|
||
|
|
{
|
||
|
|
$groups = array();
|
||
|
|
foreach ($this->graph->getVertices() as $vertex) {
|
||
|
|
$groups[$vertex->getGroup()] = true;
|
||
|
|
}
|
||
|
|
|
||
|
|
return array_keys($groups);
|
||
|
|
}
|
||
|
|
|
||
|
|
/**
|
||
|
|
* get set of all Vertices in the given group
|
||
|
|
*
|
||
|
|
* @param int $group
|
||
|
|
* @return Vertices
|
||
|
|
* @uses Vertex::getGroup()
|
||
|
|
*/
|
||
|
|
public function getVerticesGroup($group)
|
||
|
|
{
|
||
|
|
$vertices = array();
|
||
|
|
foreach ($this->graph->getVertices()->getMap() as $vid => $vertex) {
|
||
|
|
if ($vertex->getGroup() === $group) {
|
||
|
|
$vertices[$vid] = $vertex;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return new Vertices($vertices);
|
||
|
|
}
|
||
|
|
}
|