Contest Results
Here’s my answer to last week’s contest:
struct Node
{
Node **links; // pointers to other nodes
// links[n] will never be NULL
// 0 <= n < numLinks
int numLinks; // number of links
int color; // initialized to 0,
// yours to use for whatever
};
bool IsTwoColorable( Node* pStart )
{
// Determine if the graph with pStart in it
// can be colored with two colors
// Make a good trade off between memory and performance
if( pStart == NULL )
return true; // Null graph is 0 colorable
// Set to keep track of nodes we are visiting
TSet< Node* > visitNodes;
pStart->color = 1;
visitNodes.Add( pStart );
Node *pParent, *pLink;
do
{
pParent = visitNodes.First();
for( int i = 0; i < pParent->numLinks; i++ )
{
pLink = pParent->links[i];
// If not yet visited, set its color
if( pLink->color == 0 )
{
pLink->color = !(pParent->color-1)+1;
visitNodes.Add( pLink );
}
// Otherwise, if the link node has the same color
// we're not two colorable
else if( pLink->color == pParent->color )
return false;
}
visitNodes.Remove( pParent );
}
while( visitNodes.FHasElements() );
return true;
}
Some things to note, it’s functionally correct:
· It handles NULL graphics
· It handles multiple links to the same node
· It handles reflective links to the current node
Remember, there was no statement that this was a simple graph so you can have multiple links to the same node (which doesn’t affect colorability) and have nodes with multiple links to itself (which does affect colorability)
For some speed and memory considerations:
· It uses a set so that multiple links to the same node aren’t visited more than once.
· There’s no copying between “visit” and “to visit” sets.
· Not recursive
· Quick to short circuit
The last point is notable: the code above favors returning false before adding stuff to the set. Sets are O(log(n)) time to access, so favoring the check for color before adding it to the set saves use on iteration on the loop.
Also note how there’s no iterator. Accessing the first element in a set is fast and removing one is O(log(n)). Since we just need to traverse the set once and only once, we can destroy it as we go. Creating an iterator (or worse a bi-directional iterator) is just overhead.
Winner[s]
‘mauricio’ and ‘shaoxp’ both had good answers. ‘mauricio’ earns brownie points because his came with a unit test J.
Thanks for all your entries! I’m going to switch to a Monday/Monday schedule. I will post a new contest next Monday and answers the following Monday. Fridays tend to be a bit hectic so analyzing and posting results then isn’t always possible.
