PHP Classes
elePHPant
Icontem

Graph Coloring: Assign colors to graph points from a vertex list

Recommend this page to a friend!
  Info   Screenshots Screenshots   View files View files (5)   DownloadInstall with Composer Download .zip   Reputation   Support forum   Blog    
Last Updated Ratings Unique User Downloads Download Rankings
2015-12-12 (7 months ago) RSS 2.0 feedStarStarStar 59%Total: 1,243 All time: 2,953 This week: 1,088Up
Version License Categories
graphcoloring 1.0.1GNU General Publi...Algorithms, PHP 5, Math
Description Author

This class can be used to assign colors to graph points defined in a vertex list.

It can retrieve the coordinates of vertex points from a file or executing a MySQL database query.

Then it defines it assigns colors to vertex points establishing connections between the points from list of vertexes, so that two consecutive vertexes do not get the same color.

Innovation Award
PHP Programming Innovation award winner
May 2006
Winner


Prize: One book of choice by O'Reilly
Some kinds of graphs need to plot a series of points relevant to the context of the graph.

Often it is convenient to make points that are next to each other appear in distinct colors, so the graph is presented clearly.

This class can assign colors to each point to be plotted in the graph satisfying this convenience.

Manuel Lemos
Picture of Rupom Razzaque
  Performance   Level  
Name: Rupom Razzaque is available for providing paid consulting. Contact Rupom Razzaque .
Classes: 12 packages by
Country: Bangladesh Bangladesh
Age: 35
All time rank: 161 in Bangladesh Bangladesh
Week rank: 117 Down6 in Bangladesh Bangladesh Down
Innovation award
Innovation award
Nominee: 1x

Winner: 1x

Details
What's graph coloring:

In a connected graph (where vertices are connected e.g. no isolated vertex exists), graph coloring is the process that ensures proper marker (/color) has (/have) been assigned to a vertex so that no adjacent (connected) vertices hold the same marker (/color).

How this class works:
This class implemented a new algorithm of graph coloring. The present class works as follow:

1. Gets graph from source (file OR DB)
1. Represents the graph (connections as well) as an array
2. Traverses the array to color vertices according to the algorithm
3. Displays the color result

The New Graph Coloring Algorithm:
 
The new approach of graph coloring works as follow:
==========================================================================
graph = graph array
i=1
j=1
while(i<=no_of_vertices)
   while(j<=no_of_vertices)
     if (graph[i][j]==1)
        i. color vertex i, push it into the colored array
        ii. process(i)
     else
        graph[i][j]:= 0;
     endif
6. j++
   End of while
7. i++
End of while

-----------------------------------------
function process(j)
 i=1 
 while(i<=no_of_vertices)
   if(graph[j][i]==1)
    (i). graph[j][i]:=0 //Disconnects the colered vertex j from its connected ones -- duplex disconnection
    (ii).Disconnects vertex i(which is connected to the newly colored vertex j)from its connected ones--simplex disconnection
   endif
 End of while   

end of function
====================================================================================

I am not giving the complexity analysis of this algorithm here. Future versions will come with so.

And Me:
I have designed and implemented this new graph coloring algorithm in C++ first. Then, as a Web Programmer, I decided to implement it in PHP. This class is the result of such thinking. I hope that everyone (especially those like programming) will enjoy it and implement it to their applications.

Please rate this class if you like and if it comes to your needs. Please feel free to contact me for any further assistance
regarding the algorithm and implementation.

==============================================================================
MA Razzaque Rupom (aka Rupom Razzaque)
Moderator, phpResource Group
http://groups.yahoo.com/group/phpresource/

CEO, OS CLiCKS
http://www.osclicks.com

My Blog : http://rupom.wordpress.com
Emails:
rupom@osclicks.com
rupom.bd@gmail.com
Screenshots  
  • screenshot.jpg
  Files folder image Files  
File Role Description
Accessible without login Plain text file graph.sql Data Input SQL
Accessible without login Plain text file graph.txt Data Input File
Plain text file GraphColoring.class.php Class The Main Class File
Accessible without login Plain text file ReadMe.txt Doc. Documentation File
Accessible without login Plain text file usage.php Example Example Usage

 Version Control Unique User Downloads Download Rankings  
 0%
Total:1,243
This week:0
All time:2,953
This week:1,088Up
 User Ratings  
 
 All time
Utility:75%StarStarStarStar
Consistency:70%StarStarStarStar
Documentation:70%StarStarStarStar
Examples:75%StarStarStarStar
Tests:-
Videos:-
Overall:59%StarStarStar
Rank:1071