PHPackages                             algb12/graph-ds - PHPackages - PHPackages  [Skip to content](#main-content)[PHPackages](/)[Directory](/)[Categories](/categories)[Trending](/trending)[Leaderboard](/leaderboard)[Changelog](/changelog)[Analyze](/analyze)[Collections](/collections)[Log in](/login)[Sign up](/register)

1. [Directory](/)
2. /
3. [Utility & Helpers](/categories/utility)
4. /
5. algb12/graph-ds

ActiveLibrary[Utility & Helpers](/categories/utility)

algb12/graph-ds
===============

A fast implementation of the graph data-structure in PHP

1.0.9(7y ago)81132.4k↓14.6%2[1 issues](https://github.com/algb12/GraphDS/issues)1MITPHPPHP >=5.3.0

Since Nov 20Pushed 7y ago4 watchersCompare

[ Source](https://github.com/algb12/GraphDS)[ Packagist](https://packagist.org/packages/algb12/graph-ds)[ RSS](/packages/algb12-graph-ds/feed)WikiDiscussions master Synced 1mo ago

READMEChangelog (10)Dependencies (2)Versions (13)Used By (1)

GraphDS
=======

[](#graphds)

[![Code Climate](https://camo.githubusercontent.com/a11e1855ff9f560ecce9859bf11245de936d9fdd478d8f6b5f35fedd0760c136/68747470733a2f2f636f6465636c696d6174652e636f6d2f6769746875622f616c676231322f477261706844532f6261646765732f6770612e737667)](https://codeclimate.com/github/algb12/GraphDS)[![Test Coverage](https://camo.githubusercontent.com/a0af863fdc185bee6e715965e27b45d13a99ee8187651eaa686bafa52dd88bb3/68747470733a2f2f6170692e636f6465636c696d6174652e636f6d2f76312f6261646765732f33326638653633646464653432383266643134612f746573745f636f766572616765)](https://codeclimate.com/github/AchoArnold/GraphDS/test_coverage)

What is GraphDS and why was it created?
---------------------------------------

[](#what-is-graphds-and-why-was-it-created)

GraphDS is an object-oriented, lightweight implementation of the graph data-structure in PHP.

In a project of mine, I needed a way to represent graphs in PHP. None of the existing solutions suited me, so I have decided to write my own graph library from scratch. The original implementation used in my project contains additional functions for graph traversal and refactoring of graphs, but these functions are specific to my project.

This version of GraphDS used to be a toned-down version of my original implementation, but has now grown into a separate project. It makes use of OOP practices to allow on-demand loading of algorithms, making GraphDS fast, extendable and lightweight at the same time.

GraphDS requires at least PHP version 5.3. Unit tests can be run from PHP 5.4 onwards. Although compatibility with older PHP versions tries to be maintained, unit tests are only run officially for the last 3 major PHP versions.

How to install
--------------

[](#how-to-install)

Simply require the Composer package. In the directory of your project, run:

`composer require algb12/graph-ds`

What is it even useful for?
---------------------------

[](#what-is-it-even-useful-for)

Graphs are useful for many things, ranging from transportation to social networks. In this regard, GraphDS makes working with graphs in PHP a lot easier.

Please see the RoadPlanner sample app in the `SampleApp_RoadPlanner` directory to find a primitive application of GraphDS. The RoadPlanner app calculates the shortest road between two cities, using Dijkstra's, multi-path Dijkstra's and the Floyd-Warshall algorithm. Computed paths are represented visually on the source map. To test GraphDS out with your own map, take a look at the `roads.json` file in `src/data`, where you can add in your own map/"country".

Basic syntax
------------

[](#basic-syntax)

GraphDS has functions to create vertices and edges for both, undirected and directed graphs. The user does not need to worry about which type of edge/vertex is created, as this is all abstracted away under the relevant classes.

The following is a quick primer on the usage of GraphDS:

### Directed and undirected graphs

[](#directed-and-undirected-graphs)

In graph theory, there are two main types of graphs. On one hand, there are directed graphs. A directed graph has vertices connected with by one-way edges. Think of a edges of a directed graph as a one-way lanes – you can start at any vertex, but can then only follow along the directionality of the edge to the neighboring vertex.

On the other hand, there are undirected graphs. They allow you to get from any vertex to any neighbor, as in undirected graphs, there is no concept of ancestors and descendants. Think of edges of an undirected graph as normal roads, with traffic in both directions. Vertices are simply connected with each other by directionless edges.

The following shows how to initialize a directed graph:

```