2017 © Pedro Peláez
 

library graph

A mathematical graph/network library written in PHP

image

iipokypatop/graph

A mathematical graph/network library written in PHP

  • Monday, May 30, 2016
  • by iipokypatop
  • Repository
  • 1 Watchers
  • 0 Stars
  • 181 Installations
  • PHP
  • 2 Dependents
  • 0 Suggesters
  • 57 Forks
  • 0 Open issues
  • 17 Versions
  • 0 % Grown

The README.md

clue/graph Build Status

A mathematical graph/network library written in PHP, (*1)

Quickstart examples

Once installed, let's initialize a sample graph:, (*2)

<?php
require_once 'vendor/autoload.php';

use \Fhaculty\Graph\Graph as Graph;

$graph = new Graph();

// create some cities
$rome = $graph->createVertex('Rome');
$madrid = $graph->createVertex('Madrid');
$cologne = $graph->createVertex('Cologne');

// build some roads
$cologne->createEdgeTo($madrid);
$madrid->createEdgeTo($rome);
// create loop
$rome->createEdgeTo($rome);

Let's see which city (Vertex) has road (i.e. an edge pointing) to Rome, (*3)

foreach ($rome->getVerticesEdgeFrom() as $vertex) {
    echo $vertex->getId().' leads to rome'.PHP_EOL;
    // result: Madrid and Rome itself
}

Features

This library is built around the concept of mathematical graph theory (i.e. it is not a charting library for drawing a graph of a function). In essence, a graph is a set of nodes with any number of connections inbetween. In graph theory, vertices (plural of vertex) are an abstract representation of these nodes, while connections are represented as edges. Edges may be either undirected ("two-way") or directed ("one-way", aka di-edges, arcs)., (*4)

Depending on how the edges are constructed, the whole graph can either be undirected, can be a directed graph (aka digraph) or be a mixed graph. Edges are also allowed to form loops (i.e. an edge from vertex A pointing to vertex A again). Also, multiple edges from vertex A to vertex B are supported as well (aka parallel edges), effectively forming a multigraph (aka pseudograph). And of course, any combination thereof is supported as well. While many authors try to differentiate between these core concepts, this library tries hard to not impose any artificial limitations or assumptions on your graphs., (*5)

Components

This library provides the core data structures for working with graphs, its vertices, edges and attributes., (*6)

There are several official components built on top of these structures to provide commonly needed functionality. This architecture allows these components to be used independently and on demand only., (*7)

Following is a list of some highlighted components. A list of all official components can be found in the graphp project., (*8)

Graph drawing

This library is built to support visualizing graph images, including them into webpages, opening up images from within CLI applications and exporting them as PNG, JPEG or SVG file formats (among many others). Because graph drawing is a complex area on its own, the actual layouting of the graph is left up to the excelent GraphViz "Graph Visualization Software" and we merely provide some convenient APIs to interface with GraphViz., (*9)

See graphp/graphviz for more details., (*10)

Common algorithms

Besides graph drawing, one of the most common things to do with graphs is running algorithms to solve common graph problems. Therefor this library is being used as the basis for implementations for a number of commonly used graph algorithms:, (*11)

  • Search
    • Deep first (DFS)
    • Breadth first search (BFS)
  • Shortest path
    • Dijkstra
    • Moore-Bellman-Ford (MBF)
    • Counting number of hops (simple BFS)
  • Minimum spanning tree (MST)
    • Kruskal
    • Prim
  • Traveling salesman problem (TSP)
    • Bruteforce algorithm
    • Minimum spanning tree heuristic (TSP MST heuristic)
    • Nearest neighbor heuristic (NN heuristic)
  • Maximum flow
    • Edmonds-Karp
  • Minimum cost flow (MCF)
    • Cycle canceling
    • Successive shortest path
  • Maximum matching
    • Flow algorithm

See graphp/algorithms for more details., (*12)

Install

The recommended way to install this library is through composer. New to composer?, (*13)

{
    "require": {
        "clue/graph": "~0.9.0"
    }
}

You may also want to install some of the additional components. A list of all official components can be found in the graphp project., (*14)

Tests

This library uses phpunit for its extensive testsuite. You can either use a global installation or rely on the one composer installs when you first run $ composer install. This sets up the developer environment, so that you can now run it from the project root directory:, (*15)

$ php vendor/bin/phpunit

Contributing

This library comes with an extensive testsuite and is regularly tested and used in the real world. Despite this, this library is still considered beta software and its API is subject to change. The changelog lists all relevant information for updates between releases., (*16)

If you encounter any issues, please don't hesitate to drop us a line, file a bug report or even best provide us with a patch / pull request and/or unit test to reproduce your problem., (*17)

Besides directly working with the code, any additional documentation, additions to our readme or even fixing simple typos are appreciated just as well., (*18)

Any feedback and/or contribution is welcome!, (*19)

Check out #graphp on irc.freenode.net., (*20)

License

Released under the terms of the permissive MIT license., (*21)

The Versions

30/05 2016

dev-develop

dev-develop https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

07/03 2016

dev-issue-2723

dev-issue-2723 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

07/03 2016

dev-issue-2724

dev-issue-2724 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

07/03 2016

dev-performance3

dev-performance3 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

07/03 2016

dev-test_proxy_writable

dev-test_proxy_writable https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

19/02 2016

dev-debug

dev-debug https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

19/02 2016

dev-performance

dev-performance https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

19/02 2016

dev-performance2

dev-performance2 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

19/02 2016

dev-master

9999999-dev https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

19/02 2016

dev-issue-2579

dev-issue-2579 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

02/12 2015

dev-graph-clone-override-support

dev-graph-clone-override-support https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

07/03 2015

v0.9.0

0.9.0.0 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph network mathematical vertex edge

31/12 2014

v0.8.0

0.8.0.0 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graph dijkstra network mathematical vertex edge shortest path moore-bellman-ford minimum spanning tree kruskal prim

12/03 2014

v0.7.1

0.7.1.0 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graphviz graph dijkstra network mathematical vertex edge shortest path moore-bellman-ford minimum spanning tree kruskal prim

12/09 2013

v0.7.0

0.7.0.0 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graphviz graph dijkstra network mathematical vertex edge shortest path moore-bellman-ford minimum spanning tree kruskal prim

11/07 2013

v0.6.0

0.6.0.0 https://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

The Development Requires

graphviz graph dijkstra network mathematical vertex edge shortest path moore-bellman-ford minimum spanning tree kruskal prim

07/05 2013

v0.5.0

0.5.0.0 http://github.com/clue/graph

A mathematical graph/network library written in PHP

  Sources   Download

MIT

The Requires

  • php >=5.3.0

 

graph dijkstra network mathematical vertex edge shortest path moore-bellman-ford minimum spanning tree kruskal prim