To implement the algorithm of (a), we use an array
c to keep track of the candidate
and selected vertices.
c[i] = 1 if vertex i
has been selected for the independent set;
c[i] = 0 if vertex i
cannot be selected for the independent set (this happens when vertex
i is adjacent to at least one
of the selected vertices); and
c[i] = 2 if vertex i
is still a candidate for selection (this requires that vertex
i not be adjacent to any vertex that is
already selected).
Another array
count such that
count[i] is
the number
of candidate vertices that candidate vertex i
is adjacent to is also used.
At each stage, we select, for inclusion in the independent set, from vertices
with
c[i] = 2 a vertex
minV with minimum
count value.
c[minV] becomes 1 and we must update
the c and count
values for the remaining candidates. Former candidates
that are adjacent to the newly added vertex
minV are no longer candidates.
Former candidates
that are not adjacent to the newly added vertex
minV remain candidates but their
count count value may decrease
because some of the eliminated vertices may be adjacent to them.
To update the count values,
we examine the vertices adjacent to all eliminated candidates
and reduce the count of their adjacent vertices.
The code
is given below. A test program, input, and output appear in the files
TestMaxIndependentSet.*.
/** find an independent set using the greedy method
* @return an array v[0:v.length-1] that contains the
* independent set vertices */
public int [] maxIndependentSet()
{
// make sure this is an undirected graph
verifyUndirected("maxIndependentSet");
int n = vertices();
int [] c = new int [n + 1]; // candidate array
// i is a candidate iff c[i] = 2
// count[i] is the number of candidate vertices i is not adjacent to
int [] count = new int [n + 1];
// initialize candidate array
for (int i = 1; i <= n; i++)
c[i] = 2;
// find vertex with min degree
int minDegree = degree(1);
int minV = 1;
for (int i = 2; i <= n; i++)
{
int m = degree(i);
if (m < minDegree)
{
minDegree = m;
minV = i;
}
}
// minV is first vertex in independent set
c[minV] = 1;
int sizeOfIndependentSet = 1;
// vertices adjacent to minV are no longer candidates
Iterator iv = iterator(minV);
while (iv.hasNext())
c[((EdgeNode) iv.next()).vertex] = 0;
// create candidate list
ArrayLinearList candV = new ArrayLinearList();
for (int i = 1; i <= n; i++)
if (c[i] == 2)
candV.add(candV.size(), new Integer(i));
// find next vertex to add to independent set
// this is a candidate vertex which is adjacent to
// to the fewest other candidate vertices
minDegree = n + 1;
// define an iterator to go down list of candidates
Iterator ic = candV.iterator();
while (ic.hasNext())
{
int u = ((Integer) ic.next()).intValue();
// vertex u is a candidate
// find number of other candidates adjacent to it
Iterator iu = iterator(u);
count[u] = 0;
while (iu.hasNext())
{
int v = ((EdgeNode) iu.next()).vertex;
// if v is a candidate, increment count[u]
if (c[v] == 2)
count[u]++;
}
// is this better vertex to add next?
if (count[u] < minDegree)
{// yes it is
minDegree = count[u];
minV = u;
}
}
// add additional vertices to independent set and
// create a list of eliminated candidates
ArrayLinearList elimV = new ArrayLinearList();
while (minDegree < n + 1)
{// minV will be added to independent set and
// adjacent candidate vertices will be eliminated
// label eliminated candidates
iv = iterator(minV);
while (iv.hasNext())
{
int v = ((EdgeNode) iv.next()).vertex;
// v is to be eliminated, but first
// make sure it was a candidate
if (c[v] == 2)
{// it was a candidate
c[v] = 0;
elimV.add(elimV.size(), new Integer(v));
}
}
// add minV to independent set
c[minV] = 1;
sizeOfIndependentSet++;
// now set up chain of new candidates
ArrayLinearList newV = new ArrayLinearList();
ic = candV.iterator();
while (ic.hasNext())
{
int u = ((Integer) ic.next()).intValue();
if (c[u] == 2)
// u remains a candidate
newV.add(newV.size(), new Integer(u));
}
candV = newV;
// update count to account for eliminated
// candidates and selection of minV
Iterator ie = elimV.iterator();
while (ie.hasNext())
{
int u = ((Integer) ie.next()).intValue();
// u has been eliminated
// reduce count of adjacent candidates
Iterator iu = iterator(u);
while (iu.hasNext())
// easier to reduce everyone's count
count[((EdgeNode) iu.next()).vertex]--;
}
// update minV
minDegree = n + 1;
ic = candV.iterator();
while (ic.hasNext())
{
int u = ((Integer) ic.next()).intValue();
if (count[u] < minDegree)
{
minDegree = count[u];
minV = u;
}
}
}
// put independent vertices into an array
int [] indepSet = new int [sizeOfIndependentSet];
int s = -1;
for (int i = 1; i <= n; i++)
if (c[i] == 1)
indepSet[++s] = i;
return indepSet;
}