PHP Classes

PHP Euler Circuit: Find nodes of a Euler circuit and Hamiltonian path

Recommend this page to a friend!
     
  Info   Example   View files Files   Install with Composer Install with Composer   Download Download   Reputation   Support forum   Blog    
Ratings Unique User Downloads Download Rankings
Not enough user ratingsTotal: 252 All time: 7,906 This week: 560Up
Version License PHP version Categories
euler-circuit 0.2BSD License4Algorithms, Geography
Description 

Author

This class can find nodes of a Euler circuit and Hamiltonian path.

It takes a list of nodes and its connections and computes the Euler circuit traversing the all nodes and returning to the initial without passing again in an already traversed node.

The class can return an array with the path of the Euler Circuit nodes.

It can also compute the Hamiltonian path by cleaning a path to include only nodes traversed once.

Innovation Award
PHP Programming Innovation award winner
September 2014
Winner


Prize: PhpStorm IDE personal permanent license
An Euler circuit is a path defined between a set of network points that avoids passing over the same point more than once.

This class implements an algorithm to compute the Euler circuit path for a given network of points.

Manuel Lemos
Picture of Chi H.
  Performance   Level  
Name: Chi H. <contact>
Classes: 28 packages by
Country: France France
Age: 39
All time rank: 33922 in France France
Week rank: 214 Up9 in France France Up
Innovation award
Innovation award
Nominee: 22x

Winner: 3x

Example

<?php
/***************************************************************
* Copyright notice
*
* (c) 2011-2014 Chi Hoang (info@chihoang.de)
* All rights reserved
*
***************************************************************/
require_once ( "main.php" );

$example3 = Array ( 1 => Array ( 1, 2, 3, 8, 7 ),
                     
2 => Array ( 1, 3 ),
                     
3 => Array ( 1, 2, 4, 7 ),
                     
4 => Array ( 3, 7, 9, 5 ),
                     
5 => Array ( 4, 9 ),
                     
6 => Array ( 7, 9 ),
                     
7 => Array ( 1, 3, 4, 6, 8, 9 ),
                     
8 => Array ( 1, 7 ),
                     
9 => Array ( 4, 5, 6, 7 ),
                  );
                 
$example2 = Array ( 1 => Array ( 2, 3 ),
                   
2 => Array ( 1,3,4,5 ),
                   
3 => Array ( 1,2,4,5 ),
                   
4 => Array ( 2,3,5 ),
                   
5 => Array ( 2,3,4 )
                );

$example1 = Array (
                   
1 => Array ( 2, 3, 4, 5 ),
                   
2 => Array ( 1,4 ),
                   
3 => Array ( 1,4,5, 6 ),
                   
4 => Array ( 1,2,3, 6 ),
                   
5 => Array ( 1, 3 ),
                   
6 => Array ( 3, 4 )
                );
               
$obj = new eulerCircuit ();
$start = $obj->begin ($example1);
$euler = $obj->find ($start);
$hamiltonian = $obj->HamiltonianPath ($euler);
var_dump($euler);
var_dump($hamiltonian);
?>


  Files folder image Files (2)  
File Role Description
Accessible without login Plain text file example.php Example example class
Plain text file main.php Class main class

The PHP Classes site has supported package installation using the Composer tool since 2013, as you may verify by reading this instructions page.
Install with Composer Install with Composer
 Version Control Unique User Downloads Download Rankings  
 0%
Total:252
This week:0
All time:7,906
This week:560Up