A graph is an ordered pair of vertices and edges \(G = (V,E)\).

The graph class is generally the main class you'll use, you can use both the default Graph class or the GraphInterface interface.

A graph always contains a set of vertices \(V\) that you're free to set or get, and contains a set of edges \(E\) you can approach in the same way:

use Bisarca\Graph\Graph;

$graph = new Graph();

// e.g. add a new vertex to the set

$vertices = $graph->getVertexSet(); // Bisarca\Graph\Vertex\Set

$vertices->add(new Vertex());

$graph->setVertexSet($vertices);

// e.g. add a new vertex to the set

$edges = $graph->getEdgeSet(); // Bisarca\Graph\Edge\Set

$edges->add(new Edge());

$graph->setEdgeSet($edges);

When a graph is defined, it generally already contains these sets, so you can do:

use Bisarca\Graph\Edge\Set as Edges;
use Bisarca\Graph\Graph;
use Bisarca\Graph\Vertex\Set as Vertices;

$vertices = new Vertices();
$edges = new Edges();

$graph = new Graph($vertices, $edges);

You can also attach nested graphs, because a graph can be considered a vertex too. Attention: only the basic implementation is considered a vertex, if you want to declare your graph as a vertex you'll need to implement both the GraphInterface and the VertexInterface.

use Bisarca\Graph\Graph;

$vertices = $graph->getVertexSet(); // Bisarca\Graph\Vertex\Set

$vertices->add(new Graph());

$graph->setVertexSet($vertices);

Descriptors

The Graph class contains many method those help to describe the graph itself.

Loop

A graph also offers a way to check if it contains a loop.

// $graph1 contains a loop on $vertex1
// $graph2 doesn't contain a loop

var_dump(
    $graph1->hasLoop(),           // bool(true)
    $graph1->hasLoopOn($vertex1), // bool(true)
    $graph1->hasLoopOn($vertex2), // bool(false)
    $graph2->hasLoop(),           // bool(false)
    $graph2->hasLoopOn($vertex1)  // bool(false)
);

Size

The size of a graph \(G\) is the number of its edges, \(|E(G)|\).

// graph with 5 edges

$size = $graph->getSize();
// $size === 5

See also order, the number of vertices.

Order

The order of a graph \(G\) is the number of its vertices, \(|V(G)|\).

// graph with 6 vertices

$order = $graph->getOrder();
// $order === 6

See also size, the number of edges.

Degree

To know what the following methods will do, read the graphs degree page on Wikipedia.

// maximum degree of a vertex in $graph
$maxDegree = $graph->getMaxDegree();

// minimum degree of a vertex in $graph
$minDegree = $graph->getMinDegree();

// flag used to check if the graph is regular
// (every vertex has the same degree)
if ($graph->isRegular()) {

    // if the graph is regular, than you can get the graph degree
    // if you don't check the regularity of the graph and the graph is
    // not regular or it's empty, than when you'll call the getDegree
    // method you'll obtain a Bisarca\Graph\Graph\Descriptor\DegreeException
    $graphDegree = $graph->getDegree();
}

// flag used to check if the graph is regular and
// all its edges have the degree $degree
if ($graph->hasRegularity(3)) {
    // the graph is cubic, you can also check with: $graph->isCubic()
}

// a graph is balanced if for every vertex the in-degree and out-degree value is the same,
// than the graph is called a balanced directed graph
if ($graph->isBalanced()) {
    // ...
}

Inside a graph, a vertex has more implicit properties, so some helpers are available:

// number of incoming edges inside of $graph, linked to $vertex
$vertexInDegree = $graph->getVertexInDegree($vertex);

// number of outgoing edges inside of $graph, linked from $vertex
$vertexOutDegree = $graph->getVertexOutDegree($vertex);

// sum of ingoing and outgoing edges inside of $graph,
// linked from/to $vertex
$vertexDegree = $graph->getVertexDegree($vertex);


if ($graph->isIsolatedVertex($vertex)) {
    // vertex with degree 0
}

if ($graph->isLeafVertex($vertex)) {
    // vertex with degree 1
}

if ($graph->isDominatingVertex($vertex)) {
    // vertex with degree |V(G)| - 1
}

Digraph

This library doesn't force you to choose between a directed graph and an undirected graph before executing your code, so you can check if a graph is undirected or it's directed (a digraph) using the isDigraph utility.

use Bisarca\Graph\Edge\DirectedEdge;
use Bisarca\Graph\Edge\Edge;

$graph
    ->getEdgeSet()
    ->add(new Edge(/* ... */));

var_dump($graph->isDigraph()); // bool(false)

$graph
    ->getEdgeSet()
    ->add(new DirectedEdge(/* ... */));

var_dump($graph->isDigraph()); // bool(true)