Graph Colouring With Simple Backtracking, Part One

re: Graph Colouring With Simple Backtracking, Part One

Svick — Thu, 15 Jul 2010 13:09:22 GMT

@nick-m

If you need to find out whether an edge between two vertices exists, then sure.

But you don't need that in this problem, the class Graph doesn't even have something like public bool IsEdge(int node1, int node2).

So, if the only thing you need is to find out the list of all neighbours of certain vertex, adjacency list is faster or as fast (in the case of a complete graph) as adjacency matrix.

re: Graph Colouring With Simple Backtracking, Part One

nick-m — Thu, 15 Jul 2010 10:24:10 GMT

@Svick

That implementation will do better for sparse graphs. For dense graphs we may as well use the matrix because we can determine if an edge exists in O(1) time, rather than O(degree)

re: Graph Colouring With Simple Backtracking, Part One

AC — Wed, 14 Jul 2010 21:29:10 GMT

There is some redundancy in the information provided to the constructor. We could have deduced the number of nodes by taking the maximum integer found in the list of edges, instead of requiring that it be passed.

</blockquote>

I just wanted to point out that explicitly requesting the length up front is probably a good idea because it doesn't assume that everything has an edge. Not having any edges is also information. Hawaii anyone?

re: Graph Colouring With Simple Backtracking, Part One

Daniel Brückner — Wed, 14 Jul 2010 13:35:03 GMT

I have to disagree with "There is some redundancy in the information provided to the constructor." in the general case. The highest node number found in the list of edges will not be the highest node number of the graph if the node(s) with the highest node number(s) is(are) of degree zero. (Although for representing maps it should be quite safe to assume a non-zero degree for all nodes except the case of a single node.)

re: Graph Colouring With Simple Backtracking, Part One

Gabe — Wed, 14 Jul 2010 00:04:53 GMT

I think this highlights one of the advantages of pair programming. Even when making nearly-trivial classes like this, you implicitly must make dozens of design decisions. If you have to stop and think about what decisions you're making, the code takes much longer to write, and you are more likely to end up making the wrong decision. If you have to ask somebody about a decision, you have to stop what you and somebody else are doing, explain the context to them, and hope they can give you a meaningful answer.

With pair programming, there's always somebody there who has the full context of the situation who can give you advice on the decision. Ideally, this person has already even thought about the decision while you were typing in some other code, and has good reasons for their answer.

re: Graph Colouring With Simple Backtracking, Part One

Jeffrey L. Whitledge — Tue, 13 Jul 2010 20:05:59 GMT

@Leon re: uint

I can't speak for Eric, of course, but...

I once developed a system in which negative values made no sense as a parameter, so rather than validating that the parameter values were non-negative, I thought it would be a great idea to just use uint instead. I quickly discovered that whenever I used those values for anything (like calling BCL methods), they had be converted to signed integers. This meant that I had to validate that the values didn't exceed the signed integer range on the top end, so I gained nothing. Also, every time the code was called, the ints that were being used (often received from BCL functions) had to be converted to uints. It didn't take long before I changed all those uints back to ints and took all that unnecessary casting out. I still have to validate that the numbers are not negative, but the code is much cleaner!

Couldn't have said it better myself. You almost never need the range of a uint, and they are not CLS-compliant. The standard way to represent a small integer is with "int", even if there are values in there that are out of range. A good rule of thumb: only use "uint" for situations where you are interoperating with unmanaged code that expects uints, or where the integer in question is clearly used as a set of bits, not a number. Always try to avoid it in public interfaces. - Eric

re: Graph Colouring With Simple Backtracking, Part One

Leon — Tue, 13 Jul 2010 14:47:27 GMT

Is there any reason that you used int instead of uint for the 'nodes' parameter and to represent the nodes themselves?

Pros:

-A user cannot pass a negative number of nodes or node by mistake

-No extra work (except to type the extra u ;-) )

Cons: ?

re: Graph Colouring With Simple Backtracking, Part One

Jeff Yates — Tue, 13 Jul 2010 12:21:49 GMT

In the 11th paragraph, you write:

"Suppose we do the first one: simply build an undirected graph and require the user to add edges in pairs if they want an undirected graph. "

I think the first "undirected" should be "directed".

re: Graph Colouring With Simple Backtracking, Part One

An American — Tue, 13 Jul 2010 12:02:31 GMT

> I've spelled "Neighbours" the British/Canadian way. (Tradeoff: correctness vs familiarity to Americans)

You mean (Tradeoff: cuteness vs correctness) right?

re: Graph Colouring With Simple Backtracking, Part One

Denis — Tue, 13 Jul 2010 04:01:18 GMT

Yes, software developers do a lot of decisions-making and face interesting challenges every step of the way. However, I am still going to move on towards architecture and management. Tradeoff 1: intellectual gratification vs. job security. Tradeoff 2: being bossed around by pompous boys 10 years younger than you vs. leaving your comfort zone. Tradeoff 3: thinking how to do what you are ordered to do vs. thinking what needs to be done, and why.

Except at Microsoft and a few other Big Guys, software development has become routine, anyway (Tradeoff: cutting edge of technology vs. service industry).