README

phgraph/graph

PHGraph is a modern mathematical graph/network library written in PHP.

Installation

You can install the package via composer:

composer require phgraph/graph

Usage

Creation and Search

use PHGraph\Graph;
use PHGraph\Search\BreadthFirst;
…

$graph = new Graph;
$columbus = $graph->newVertex([
    'name' => 'Columbus',
]);
$cleveland = $graph->newVertex([
    'name' => 'Cleveland',
]);
$cincinnati = $graph->newVertex([
    'name' => 'Cincinnati',
]);

$columbus->createEdge($cleveland);
$columbus->createEdge($cincinnati);

$search = new BreadthFirst($cincinnati);
if ($search->hasVertex($cleveland)) {
    echo "We can get from Cincinnati to Cleveland\n";
} else {
    echo "We can’t get from Cincinnati to Cleveland\n";
}

Graph drawing

This library has support for visualizing graphs as images using GraphViz "Graph Visualization Software". You will need GraphViz installed on your system for this to work.

use PHGraph\Graph;
use PHGraph\GraphViz\GraphViz;
…

$graph = new Graph;
$columbus = $graph->newVertex([
    'name' => 'Columbus',
]);
$cleveland = $graph->newVertex([
    'name' => 'Cleveland',
]);
$cincinnati = $graph->newVertex([
    'name' => 'Cincinnati',
]);
$columbus->createEdge($cleveland);
$columbus->createEdge($cincinnati);

$graphviz = new GraphViz($graph);
// open the image on your system
$graphviz->display();

output:

Algorithms

A graph library is rather boring without the ability to use algorithms on it, here is a list of the currently supported ones:

• Search
  • Depth first
  • Breadth first
• Shortest path
  • Dijkstra
  • Moore-Bellman-Ford
  • Least Hops
• Minimum Spanning Tree
  • Kruskal’s algorithm
  • Prim’s algorithm
• Traveling Salesman Problem
  • Nearest Neighbor

Development

Installing dependencies

You will need Composer for the development dependencies. Once you have that, run the following

$ composer install

Running tests

You can run the current test suite with the following command

$ composer test

For static analysis of the code run the following

$ composer analyse

Bug Reports

Bug reports for the current release version can be opened in this repository’s issue tracker.

Thanks

this was heavily inspired by graphp/graph.