Sign in to follow this  

Bipartite Algorithm

This topic is 4811 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I came up with a bipartite algorithm that is O(m) where m is the number of connections in the graph. It does the coloring too. Not sure if it's like the others out there.
bool Graph::Bipartite()
{
	int count = 0;
	int size;
	
	for(int i = 0; i < m_numberVertices; i++)
	{
		if(m_vertices[i].m_color == 1)
		{
			size = m_vertices[i].GetNumberConnections();
			for(int j = 0; j < size; j++)
			{
				if(m_vertices[m_vertices[i].GetConnection(j)].m_color != 2)
				{
					m_vertices[m_vertices[i].GetConnection(j)].m_color = 2;
					count++;
				}
			}
		}		
		else if(m_vertices[i].m_color == 2)
		{
			size = m_vertices[i].GetNumberConnections();
			for(int j = 0; j < size; j++)
			{
				if(m_vertices[m_vertices[i].GetConnection(j)].m_color != 1)
				{
					m_vertices[m_vertices[i].GetConnection(j)].m_color = 1;
					count++;
				}
			}
		}
		else
		{
			m_vertices[i].m_color = 1;
			count++;
			size = m_vertices[i].GetNumberConnections();
			for(int j = 0; j < size; j++)
			{
				if(m_vertices[m_vertices[i].GetConnection(j)].m_color != 2)
				{
					m_vertices[m_vertices[i].GetConnection(j)].m_color = 2;
					count++;
				}
			}
		}
	}

	if(m_numberVertices == count)
	{
		return true;
	}
	
	return false;
}


[Edited by - Zefrieg on October 10, 2004 8:40:48 AM]

Share this post


Link to post
Share on other sites
I do not understand what you mean by numberListOne++;
so I will assume it means count++; or nothing.

* If it means count++, I considered the case:

graph: 1-3-4-2, colors: R/B


1-3-4-2
?-?-?-? count = 0
R-B-?-? count = 2
R-B-B-R count = 4
R-B-R-R count = 5
R-B-R-B count = 6


In which case m_numberVertices != count although the graph is bipartite.

* Now, if it does not mean count++, I considered the case:

graph: 1-2-3, colors: R/B


1-2-3
?-?-? count = 0
R-B-? count = 1
R-B-R count = 2
R-B-R count = 2


Then again, m_numberVertices != count, again with a bipartite graph.

Did I understand something wrong?

Share this post


Link to post
Share on other sites
Yeah, you are steping through the algorithm wrong. Also, I fixed that problem with the count variable. It is suppost to be count++ instead of numberListOne++. The numberVertices corresponds to the number of vertices in the graph.

for:

1-2-3

?-?-? count = 0
R-B-? count = 2
R-B-R count = 3

numberVertices == count so bipartite

for:

1-3-2-4

?-?-?-? count = 0
R-B-?-? count = 2
R-B-R-? count = 3
R-B-R-B count = 4

4 == 4

numberVertices == count so bipartite

A simple proceedure of what the algorithm does is as follows:

1. Iterate through each node once
2. If a node has not been visited, then color the node red and increase count, then color all connected non-black nodes black and increase count for each node colored black.
3. If a node is red, then color all connected non-black nodes black and increase count for each node colored black.
4. If a node is black, then color all connected non-red nodes red and increase count for each node colored red.

The case when a graph is not biparte occurs when a previously colored node is changed to a different color. Basically, take for example a red colored node with all of its' connections colored black. If a black node is connected to any of the red node's connections, then a change from red to black or black to red would occur. This would cause the coloring count to be greater than the number of vertices in the graph.

Share this post


Link to post
Share on other sites
How does your algorithm function on the graph 1-3-4-2 I interpreted above? I understood it would perform:

Computing vertex 1:
1 not visited so:
1 -> R (count = 1)
1 = R and 3 != B so:
3 -> B (count = 2)

Computing vertex 2:
2 not visited so:
2 -> R (count = 3)
2 = R and 4 != B so:
4 -> B (count = 4)

Computing vertex 3:
3 = B and 4 != R so:
4 -> R (count = 5)

Computing vertex 4:
4 = R and 2 != B so:
2 -> B (count = 6)

EDIT: what troubles me is that you seem to be doing the same amount of work as a depth-first coloring algorithm, while discarding adjacency information for already-colored vertices (because you "leave" the already colored areas to paint remote vertices in a color without being certain that this "other" color is the correct one).

Share this post


Link to post
Share on other sites
I see what you mean. It seems as though just looking at the count will not determine if the graph is bipartite. Although, It does seem to color the vertices correctly.

1-3-4-2

Vertex 1:
1 not colored
1->R
3 connected to 1
3->B

State: R-B-?-?

Vertex 2:
2 not colored
2->R
4 connected to 2
4->B

State: R-B-B-R

Vertex 3:
3 is B
1 connected to 3
1->R
4 connected to 3
4->R

State: R-B-R-R

Vertex 4:
4 is R
3 connected to 4
3->B
2 connected to 4
2->B

State: R-B-R-B

Share this post


Link to post
Share on other sites
If I used a depth first search, I could then look at the number of vertices that were colored to determine if the graph is bipartite too, right? It seems as though the method works if I pick a colored node without connections colored every time.

Perhaps I could use some sort of priority queue to pick out the vertices that have been colored that have the least amount of colored connections.

If any nodes have been recolored then not bipartite. Could exit at that point since coloring would be wrong anyway.

Exit when number of non-recolored nodes colored equals the total number of nodes.

Share this post


Link to post
Share on other sites
Well, using a Depth-First search, you could simultaneously color the entire graph, and, if you happen to need to recolor something, find out that the graph is not bipartite. All in O(#vertices + #edges)

The downside is that it doesn't work on graphs that are not connex.

Share this post


Link to post
Share on other sites

This topic is 4811 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this