Graph colouring in python using adjacency matrix

How can I implement graph colouring in python using a开发者_StackOverflow中文版djacency matrix? Is it possible? I implemented it using list. But it has some problems. I want to implement it using matrix. Can anybody give me the answer or suggestions to this?

---

Is it possible? Yes, of course. But are your problems with making Graphs, or coding algorithms that deal with them?

Separating the algorithm from the data type might make it easier for you. Here are a couple suggestions:

• create (or use) an abstract data type Graph
• code the coloring algorithm against the Graph interface
• then, vary the Graph implementation between list and matrix forms

If you just want to use Graphs, and don't need to implement them yourself, a quick Google search turned up this python graph library.

---

Implementing using adjacency is somewhat easier than using lists, as lists take a longer time and space. igraph has a quick method neighbors which can be used. However, with adjacency matrix alone, we can come up with our own graph coloring version which may not result in using minimum chromatic number. A quick strategy may be as follows: Initalize: Put one distinct color for nodes on each row (where a 1 appears) Start: With highest degree node (HDN) row as a reference, compare each row (meaning each node) with the HDN and see if it is also its neighbor by detecting a 1. If yes, then change that nodes color. Proceed like this to fine-tune. O(N^2) approach! Hope this helps.