Download the PHP package dbeurive/graph without Composer

• Introduction
• License
• Installation
• Graphs' types
• Graphs' representations
  • Directed graphs
  • Directed and unweighted
  • Directed and weighted
  • Undirected graphs
  • Undirected and unweighted
  • Undirected and weighted
• Graphs' API
  • Introduction
  • Loading a graph from a CSV file
  • Loading CSV with the default loader
  • Loading CSV with a customized loader
  • Dumping a graph into a CSV file
  • Dumping into CSV with the default dumper
  • Dumping into CSV with a customized dumper
  • Dumping a graph into its GraphViz representation
• Using the algorithms
  • The "Breadth First Search" algorithm
  • Synopsis
  • The "Depth First Search" algorithm
  • Synopsis
  • The Dijkstra's algorithm
  • Synopsis
  • Illustration
  • The Tarjan's algorithm
  • Synopsis
  • Illustration

Introduction

This repository contains the implementations of various algorithms for graphs.

• The breadth-first search algorithm
• The depth-first search algorithm
• The Dijkstra's algorithm
• The Tarjan's strongly connected components algorithm

License

This code is published under the following license:

Creative Common Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)

See the file LICENSE.TXT

Installation

From the command line:

composer require dbeurive/graph

Or, from within the file composer.json:

"require": {
    "dbeurive/graph": "*"
}

Graphs' types

Graphs may be:

• Directed or not.
• Weighted or not.

A given graph may be:

Graphs' representations

Many formalisms may be used to represent a graph. For example:

• Edge lists
• Adjacency matrices
• Adjacency lists

This document presents various ways used to represent graphs:

https://fr.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs

This PHP module uses the formalism known as "Adjacency lists".

Directed graphs

Vertices have successors (and predecessors).

We can choose to describe the graph through its lists of successors or through its lists of predecessors.

Directed and unweighted

Let's consider the following directed unweighted graph:

The agency lists can be represented by the associative array below:

Or by a CSV file:

vertex1 vertex2 vertex5
vertex5 vertex6 vertex7
vertex2 vertex3
vertex3 vertex4
vertex4 vertex2

• The vertex vertex1 has two successors: vertex2 and vertex5.
• The vertex vertex2 has one successor: vertex3.
• ...

See this example.

Directed and weighted

Let's consider the following directed weighted graph:

The agency lists can be represented by the associative array below:

Or by a CSV file:

vertex1 vertex2:1 vertex5:2
vertex5 vertex6:3 vertex7:4
vertex2 vertex3:5
vertex3 vertex4:6
vertex4 vertex2:7

• The vertex vertex1 has two successors: vertex2 and vertex5.
  • The weight associated to the edge from vertex1 to vertex2 is 1.
  • The weight associated to the edge from vertex1 to vertex5 is 2.
• The vertex vertex2 has one successor: vertex3.
  • The weight associated to the edge from vertex2 to vertex3 is 5.
• ...

See this example.

Undirected graphs

Vertices have neighbours.

Undirected and unweighted

Let's consider the following undirected unweighted graph:

The agency lists can be represented by the associative array below:

Or by the CV file:

vertex1 vertex2 vertex5
vertex5 vertex6 vertex7
vertex2 vertex3
vertex3 vertex4
vertex4 vertex2

• The vertex vertex1 has two neighbours: vertex2 and vertex5.
• The vertex vertex1 has two neighbours: vertex6 and vertex7.
• ...

See this example.

Undirected and weighted

Let's consider the following undirected weighted graph:

The agency lists can be represented by the associative array below:

Or by the CSV file:

vertex1 vertex2:1 vertex5:2
vertex5 vertex6:3 vertex7:4
vertex2 vertex3:5
vertex3 vertex4:6
vertex4 vertex2:7

• The vertex vertex1 has two successors: vertex2 and vertex5.
  • The weight associated to the edge from vertex1 to vertex2 is 1.
  • The weight associated to the edge from vertex1 to vertex5 is 2.
• The vertex vertex2 has one successor: vertex3.
  • The weight associated to the edge from vertex2 to vertex3 is 5.
• ...

See this example.

Graphs' API

Introduction

The graph's API allows the following actions:

• Load a graph from a CSV file.
• Dump a graph into a CSV file.
• Create the GraphViz representation of a graph.
• "Complete" a graph's representation.
• For directed graphs: calculate the lists of predecessors from the lists of successors and vice versa.

Instead of presenting an-in depth description of the API, we will show examples of uses.

Detailed API description can be generated using phpDocumentor. Just go to the root directory of this package and issue the following command: phpdoc. The documentation will be generated within the directory doc/api.

Loading a graph from a CSV file

Loading CSV with the default loader

Synopsis:

By default:

• Fields are separated by a space.
• Edges' weight is indicated by the character ':'.
• Vertices' names are loaded "as is".

Examples of standard CSV files:

vertex1
vertex2 vertex1 vertex4
vertex5 vertex1
vertex6 vertex5
vertex7 vertex5
vertex3 vertex2
vertex4 vertex3

or:

vertex1
vertex2 vertex1:1 vertex4:7
vertex5 vertex1:2
vertex6 vertex5:3
vertex7 vertex5:4
vertex3 vertex2:5
vertex4 vertex3:6

See example from-csv-directed-unweighted.php.

See example from-csv-directed-weighted.php.

See example from-csv-undirected-unweighted.php.

See example from-csv-undirected-weighted.php.

Loading CSV with a customized loader

Synopsis:

While loading CSV files, it is possible to specify non-standard attributes:

• The field separator. The default field separator is the space (" ").
• The weight indicator (for weighted graphs only). The default weight indicator is the character ":".

It is also possible to specify actions applied to the following data:

• The vertices' names.
• The line of CSV (for example, you can remove leading and trailing spaces).

Actions are specified via a "callable" (see this explanation).

In the following examples:

• We changed the field separator (we use ";" instead of " ").
• We changed the weight indicator (we used "::" instead of ":").
• We convert vertices' names into uppercase.
• We remove leading and trailing spaces from each line before any other process.

See example from-csv-directed-unweighted-non-standard.php.

See example from-csv-directed-weighted-non-standard.php.

Dumping a graph into a CSV file

Dumping into CSV with the default dumper

Synopsis:

See example to-csv-directed-unweighted.php.

See example to-csv-directed-weighted.php.

See example to-csv-undirected-unweighted.php.

See example to-csv-undirected-weighted.php.

Dumping into CSV with a customized dumper

Synopsis:

While dumping CSV files, it is possible to specify non-standard attributes:

• The field separator. The default field separator is the space (" ").
• The weight indicator (for weighted graphs only). The default weight indicator is the character ":".

It is also possible to specify actions applied to the following data:

• The vertices' names.

Actions are specified via a "callable" (see this explanation).

See example to-csv-directed-unweighted-non-standard.php.

See example to-csv-directed-weighted-non-standard.php.

See example to-csv-undirected-unweighted-non-standard.php.

See example to-csv-undirected-weighted-non-standard.php.

Dumping a graph into its GraphViz representation

Synopsis:

Please note that the generated GraphViz representation is highly customisable. The methods dumpSuccessorsToGraphviz, dumpPredecessorsToGraphviz and dumpNeighboursToGraphviz take parameters. These parameters allow you to customise the appearances of the vertices and of the edges.

See example to-graphviz-directed-unweighted.php.

See example to-graphviz-directed-weighted.php.

See example to-graphviz-undirected-unweighted.php.

See example to-graphviz-undirected-weighted.php.

Using the algorithms

The "Breadth First Search" algorithm

See the description here.

Synopsis

Please note that this algorithm works for directed and undirected graphs.

Please note that the returned value of the callback function ($callback) determines the behaviour of the method run().

• If the callback function returns the value true, then the method run() continues the traversal of the graph.
• If the callback function returns the value false, then the method run() stops the traversal of the graph.

See example breadth-first-search-directed.php.

See example breadth-first-search-undirected.php.

The "Depth First Search" algorithm

See the description here.

Synopsis

Please note that this algorithm works for directed and undirected graphs.

Please note that the returned value of the callback function ($callback) determines the behaviour of the method run().

• If the callback function returns the value true, then the method run() continues the traversal of the graph.
• If the callback function returns the value false, then the method run() stops the traversal of the graph.

See example depth-first-search-directed.php.

See example depth-first-search-undirected.php.

The Dijkstra's algorithm

See the description here.

• This algorithm works for both directed and undirected graphs.
• The graph must be weighted.

Synopsis

See example dijkstra-directed.php.

See example dijkstra-undirected.php.

Illustration

Given the graph below, let's find the shortest paths from the vertex "1" to all other vertices.

After running the algorithm, we get:

• The shortest distance between vertex "1" and vertex "3" is 9.
• The shortest distance between vertex "1" and vertex "6" is 11.
• The shortest distance between vertex "1" and vertex "5" is 20.
• ...

Shortest paths are printed in red.

The Tarjan's algorithm

See the description here.

• This algorithm works for both directed graphs only.
• The graph may be weighted or not.

Synopsis

See example tarjan.php.

Illustration

Given the graph below, let's find all the cycles:

After running the algorithm, we get:

Please note that this algorithm does not return the list of cycles within the graph. It returns the list of strongly connected components. However, cycle detection is an application of this algorithm. Here, we choose to show the result of the method getCycles().