src/Graph.php
<?php
declare(strict_types=1);
namespace PHGraph;
use PHGraph\Contracts\Attributable;
use PHGraph\Contracts\Directable;
use PHGraph\Support\VertexReplacementMap;
use PHGraph\Traits\Attributes;
use UnderflowException;
use UnexpectedValueException;
/**
* Representation of a Mathematical Graph.
*/
final class Graph implements Attributable, Directable
{
use Attributes;
/** @var \PHGraph\Vertex[] */
protected array $vertices = [];
/**
* Degree: get degree for k-regular-graph (only if each vertex has the same
* degree).
*
* @throws UnderflowException if graph is empty
* @throws UnexpectedValueException if graph is not regular
*
* @return int
*/
public function getDegree(): int
{
if (count($this->vertices) === 0) {
throw new UnderflowException('Graph is empty');
}
$degree = reset($this->vertices)->degree();
foreach ($this->vertices as $vertex) {
$i = $vertex->degree();
if ($i !== $degree) {
throw new UnexpectedValueException('Graph is not k-regular');
}
}
return $degree;
}
/**
* Degree: get minimum degree of vertices.
*
* @throws UnderflowException if graph is empty
*
* @return int
*/
public function getDegreeMin(): int
{
if (count($this->vertices) === 0) {
throw new UnderflowException('Graph is empty');
}
return min(array_map(static function ($item) {
return $item->degree();
}, $this->vertices));
}
/**
* Degree: get maximum degree of vertices.
*
* @throws UnderflowException if graph is empty
*
* @return int
*/
public function getDegreeMax(): int
{
if (count($this->vertices) === 0) {
throw new UnderflowException('Graph is empty');
}
return max(array_map(static function ($item) {
return $item->degree();
}, $this->vertices));
}
/**
* get the vertices in the graph.
*
* @return \PHGraph\Vertex[]
*/
public function getVertices(): array
{
return $this->vertices;
}
/**
* add Vertex to Graph.
*
* @param \PHGraph\Vertex $vertex vertex to add
*
* @return void
*/
public function addVertex(Vertex $vertex): void
{
$this->vertices[$vertex->getId()] = $vertex;
if ($this !== $vertex->getGraph()) {
$vertex->setGraph($this);
}
}
/**
* create a new Vertex in this Graph.
*
* @param mixed[] $attributes attributes for the vertex
*
* @return \PHGraph\Vertex
*/
public function newVertex(array $attributes = []): Vertex
{
$vertex = new Vertex($this, $attributes);
$this->vertices[$vertex->getId()] = $vertex;
return $vertex;
}
/**
* remove Vertex from Graph.
*
* @param \PHGraph\Vertex $vertex vertex to remove
*
* @return void
*/
public function removeVertex(Vertex $vertex): void
{
unset($this->vertices[$vertex->getId()]);
$vertex->destroy();
}
/**
* get the edges in the graph.
*
* @return \PHGraph\Edge[]
*/
public function getEdges(): array
{
$edges = [];
/** @var \PHGraph\Vertex $vertex */
foreach ($this->vertices as $vertex) {
foreach ($vertex->getEdges() as $edge) {
$edges[$edge->getId()] = $edge;
}
}
return $edges;
}
/**
* Create a copy of this graph with only the supplied edges.
*
* @param \PHGraph\Edge[] $edges edges to use
*
* @return \PHGraph\Graph
*/
public function newFromEdges(array $edges): Graph
{
$new_graph = new static();
$new_graph->attributes = $this->attributes;
$vertex_replacement_map = new VertexReplacementMap();
$vertices = [];
foreach ($edges as $edge) {
foreach ($edge->getVertices() as $vertex) {
$vertices[$vertex->getId()] = $vertex;
}
}
/** @var \PHGraph\Vertex $vertex */
foreach ($vertices as $vertex) {
$new_vertex = clone $vertex;
$new_vertex->setGraph($new_graph);
$vertex_replacement_map[$vertex] = $new_vertex;
}
/** @var \PHGraph\Edge $edge */
foreach ($edges as $edge) {
$new_edge = clone $edge;
$new_edge->replaceVerticesFromMap($vertex_replacement_map);
}
return $new_graph;
}
/**
* Create a copy of this graph with only the supplied verticies.
*
* @param \PHGraph\Vertex[] $vertices vertices to use
*
* @return \PHGraph\Graph
*/
public function newFromVertices(array $vertices): Graph
{
$new_graph = new static();
$new_graph->attributes = $this->attributes;
$keyed_vertices = [];
foreach ($vertices as $vertex) {
$keyed_vertices[$vertex->getId()] = true;
}
$vertex_replacement_map = new VertexReplacementMap();
/** @var \PHGraph\Edge[] $edges */
$edges = [];
foreach ($vertices as $vertex) {
$new_vertex = clone $vertex;
$new_vertex->setGraph($new_graph);
$vertex_replacement_map[$vertex] = $new_vertex;
foreach ($vertex->getAllEdges() as $edge) {
if (
isset($keyed_vertices[$edge->getFrom()->getId()])
&& isset($keyed_vertices[$edge->getTo()->getId()])
) {
$edges[$edge->getId()] = $edge;
}
}
}
foreach ($edges as $edge) {
$new_edge = clone $edge;
$new_edge->replaceVerticesFromMap($vertex_replacement_map);
}
return $new_graph;
}
/**
* Grouped: count total number of different groups assigned to vertices.
*
* @return int
*/
public function getNumberOfGroups(): int
{
return count($this->getGroups());
}
/**
* Grouped: checks whether the input graph’s vertex groups are a valid
* bipartition.
*
* @return bool
*/
public function isBipartit(): bool
{
if ($this->getNumberOfGroups() !== 2) {
return false;
}
/** @var \PHGraph\Vertex $vertex */
foreach ($this->vertices as $vertex) {
$group = $vertex->getAttribute('group');
/** @var \PHGraph\Vertex $vertex_neighbor */
foreach ($vertex->getVerticesTo() as $vertex_neighbor) {
if ($vertex_neighbor->getAttribute('group') === $group) {
return false;
}
}
}
return true;
}
/**
* Grouped: get vector of all group numbers.
*
* @return array<int>
*/
public function getGroups(): array
{
$groups = [];
/** @var \PHGraph\Vertex $vertex */
foreach ($this->vertices as $vertex) {
$groups[(int) $vertex->getAttribute('group')] = true;
}
return array_keys($groups);
}
/**
* Grouped: get set of all Vertices in the given group.
*
* @param int $group
*
* @return \PHGraph\Vertex[]
*/
public function getVerticesGroup(int $group): array
{
return array_filter($this->vertices, static function ($vertex) use ($group) {
return $vertex->getAttribute('group') === $group;
});
}
/**
* Directed: checks whether the graph has any directed edges.
*
* @return bool
*/
public function hasDirected(): bool
{
foreach ($this->getEdges() as $edge) {
if ($edge->isDirected()) {
return true;
}
}
return false;
}
/**
* Directed: checks whether the graph has any undirected edges.
*
* @return bool
*/
public function hasUndirected(): bool
{
foreach ($this->getEdges() as $edge) {
if (!$edge->isDirected()) {
return true;
}
}
return false;
}
/**
* Directed: checks whether this is a mixed graph.
*
* @return bool
*/
public function isMixed(): bool
{
return $this->hasDirected() && $this->hasUndirected();
}
/**
* Degree: checks whether the indegree of every vertex equals its outdegree.
*
* @return bool
*/
public function isBalanced(): bool
{
foreach ($this->vertices as $vertex) {
if ($vertex->degreeIn() !== $vertex->degreeOut()) {
return false;
}
}
return true;
}
/**
* Complete: checks whether this graph is complete.
*
* @return bool
*/
public function isComplete(): bool
{
foreach ($this->vertices as $vertex_a) {
$connected_vertices = $vertex_a->getVertices();
foreach ($this->vertices as $vertex_b) {
if (
$vertex_a !== $vertex_b
&& !isset($connected_vertices[$vertex_b->getId()])
) {
return false;
}
}
}
return true;
}
/**
* Degree: checks whether this graph is regular, i.e. each vertex has the
* same indegree/outdegree.
*
* @return bool
*/
public function isRegular(): bool
{
if (count($this->vertices) === 0) {
return true;
}
try {
$this->getDegree();
return true;
} catch (UnexpectedValueException $ignore) {
// ignoring UnexpectedValueException
}
return false;
}
}