Also we need an additional array JOIN which indicates which nodes are adjacent (i.e., if JOIN(A) = B then every node joined to A must be in the same set as B.) JOIN should be initialized to 0 (as no one is adjacent to anyone in the beginning.) Note that the order of consideration is relevant. (See me and consider (1,2), (4,3), (1, 4) - same edges but placement of 3 and 4 makes a difference. Trace your own algorithm with these edges.) Hence the algorithm below does not make decisions about set containment until it has enough knowlege
Algorithm BIPART (i,j)
{
// procedure to see if the edge(i,j) is an element of a bipartite graph //
A = FIND(i)
If A = B then return (not bipartite) //same parents implies same set //
If JOIN(A) = 0 and JOIN(B) = 0 then //isolated nodes - neither in "contained" set yet //
If JOIN(A) = 0 and JOIN(B) != 0 then
If JOIN(A) = !0 and JOIN(B) = 0 then
If JOIN(A) = !0 and JOIN(B) != 0 then
Consider the simple graph noted earlier. Build JOIN and PARENT arrays
Let edges = m, then BIPART will be called to test m edges in time
Another (consider time)(don't forget that this one has some problems- discussed in class):
V[1:n] is an array of all vertices in the graph.
Algorithm DOUBLEMAXMIN
So, within loop - 9 comparisons done (n-5+1)/4 times
so total comparisons are 9(n-4/4) + 5
We cannot assume that the graph is connected. We start with a 'forest" of individual (1 node) trees. Thus, initialize UNION - FIND structures (as noted in class) for n before the program BIPART is first called. As we need to know the root of the tree after a UNION - let UNION return a value r (the root returned after the UNION).
// the first step is to find the parent (root) of i and j //
// whatever happens to the parent also happens to the children //
B = FIND(j)
// to avoid confusion, will not use nested if, as each if returns and hence run time is not effected but readability improves //
JOIN(A) = B
JOIN(B) = A
return (bipartite)
r = UNION(A, JOIN(B)) // i is isolated - include in JOIN(B) //
Join(B) = r // i now has parent r //
Join(r) = B // A points to r in parent map, so use JOIN(r) rather than JOIN(A) //
return (bipartite)
r = UNION(B, JOIN(A)) // Perform Union (changes parent array) - j is isolated - include in JOIN(A) //
JOIN(A) = r
JOIN(r) = A
return (bipartite)
if JOIN(A) = B and JOIN(B) = A then return(bipartite)
// elements were already in proper sets //
else // consider "containment" of each //
r = UNION(A, JOIN(B))
s = UNION(B, JOIN(A))
JOIN(s) = r
JOIN(r) = s
return (bipartite)
}
O(n+m) (m for calling m edges and n for initialization of UNION/FIND/JOIN structures). Problem statement said to do no more than 2m FINDS + max{m, n-2} UNIONS
This algorithm does so as there are 2 FINDs for each edge call, and each node is UNIONed only once (when decision is made about set containment). Note also that the first node in a set "tree" is the parent and hence needs no UNION, so there will be n-2 calls to UNION maximum.
blnBipartite is initially true and indicates whether the graph is bipartite or not when the function is complete.
i and j are adjacent vertices (i.e. they make up an edge in the graph).
Set1 and Set2 are sets.
FIND returns the set to which a vertex belongs.
UNION makes a vertex belong to a set.
OPPOSITE returns the set to which a vertex does not belong.
BIPAR(i, j)
{
if FIND(i) = FIND(j) then
{
blnBipartite = false
}
else if i or j do not belong to a set
{
if i and j do not belong to a set
UNION(Set1, i)
UNION(Set2, j)
else if i does not belong to a set then
UNION(OPPOSITE(j), i)
else
UNION(OPPOSITE(i), j)
for each vertex adjacent to V[i] except j
BIPAR(vertex, i)
for each vertex adjacent to V[j] except i
BIPAR(j, vertex)
}
}
DOUBLEMAXMIN
This procedure uses two subroutines SWITCH and ORDER. It uses no recursion - however it essentially mimics recursion by grouping from the bottom up. You probably want to try a recursive solution for the experience.
Algorithm SWITCH (a,b)
temp = a
a = b
b = temp
and
Algorithm ORDER(A(1), A(2), A(3), A(4), MAX1, MAX2, MIN1, MIN2)
{
If A(1) < A(2) the SWITCH(A(1), A(2)) // switches groups of 2
If A(3) < A(4) the SWITCH(A(3), A(4)) // (max, min)(max, min)
If A(1) < A(3) the SWITCH(A(1), A(3)) // largest element in A(1)
If A(2) < A(4) the SWITCH(A(2), A(4)) // smallest element in A(4)
If A(2) < A(3) the SWITCH(A(2), A(3)) // middle terms in order
// Array A is now in decreasing order //
MAX1 = A(1)
MAX2 = A(2)
MIN1 = A(3)
MIN2 = A(4)
}
And the main algorithm:
Algorithm DOUBLEMAXMIN(S)
{
ORDER(S(1), S(2), S(3), S(4), MAXONE, MAXTWO, MINTWO, MINONE)
For i = 5 to n by 4 do
{
ORDER(S(i), S(i+1), S(i+2), S(i+3), MAX2A, MAX2B, MIN2A, MIN2B)
// Two comparisons to find the two max in order
If MAXONE > MAX2A then
{
if MAX2A > MAXTWO then MAXTWO = MAX2A
} //endif
else
{
if MAX2B > MAXONE then MAXTWO = MAX2B
else MAXTWO = MAXONE
MAXONE = MAX2A
} //endif
// Two comparisons to find the two min in order
If MINONE < MIN2A then
{
if MIN2A < MINTWO then MINTWO = MIN2A
} //endif
else
{
if MIN2B < MINONE then MINTWO = MIN2B
else MINTWO = MINONE
MINONE = MIN2A
} // endif
} // end for
return(MAXONE, MAXTWO, MINTWO, MINONE)
}
Time Analysis:
ORDER does 5 comparisions
For i = 5 to n by 4 do
ORDER - 5 comparisons
get MAX - 2 comparisons
get MIN - 2 comparisons
= 9n/4 - 9 + 5
= 9n/4 - 4
