# Greedy Maximum Independent Set in C

An independent set of a graph is some subset of the vertices where no vertex in the subset is connected to another vertex in the subset. For example, in the graph shown below, the set of vertices (0, 2, 4) is an independent set, as is (1, 3, 5). The Maximimum Independent Set (MIS) problem is to find an independent set with the greatest cardinality in a graph. The problem is NP-complete, but a greedy algorithm gives a good approximation.

The algorithm is:

1. 1. Start with the set of vertices of the graph, $$V$$ and an empty set for the MIS, $$S$$
2. While $$V \ne \emptyset$$:
1. Find a vertex of minimum degree $$v \in V$$
2. Add it to $$S$$
3. Remove it and its neighbours from $$V$$

The following is an implementation in C;

#include <stdlib.h>

/* Graph edge */
typedef struct {
unsigned int first;
unsigned int second;
} edge;

/* State a vertex can be in */
typedef enum {
IN_GRAPH = 0,
IN_MIS = 1,
} vertex_state;

/* Vertex info */
typedef struct {
vertex_state state;
unsigned int degree;
} vertex_info;

/* Create and initialise the data structure for vertices */
static vertex_info *create_vertices(const edge *edges, unsigned int size,
unsigned int order)
{
unsigned int i;
vertex_info *vertices = malloc(order * sizeof(vertex_info));
if (vertices == NULL) {
return 0;
}
for (i = 0; i < order; i++) {
vertices[i].state = IN_GRAPH;
vertices[i].degree = 0;
}
for (i = 0; i < size; i++) {
vertices[edges[i].first].degree++;
vertices[edges[i].second].degree++;
}
return vertices;
}

/* Find a vertex with the lowest degree of any in the graph */
static int min_degree_vertex(const vertex_info *vertices, unsigned int order)
{
unsigned int min_degree = 0;
int min_vertex = -1;
unsigned int i;
for (i = 0; i < order; i++) {
if (vertices[i].state == IN_GRAPH
&& (min_degree == 0
|| vertices[i].degree < min_degree))
{
min_degree = vertices[i].degree;
min_vertex = i;
}
}
return min_vertex;
}

/* Move a vertex from the graph, adjusting the degrees of its neighbours */
static void move_vertex(vertex_info *vertices, unsigned int order, const edge *edges,
unsigned int size, unsigned int v, vertex_state state)
{
unsigned int e;
/* Remove vertex */
vertices[v].state = state;
/* Reduce the degrees of its neighbours */
for (e = 0; e < size; e++) {
if (edges[e].first == v
&& vertices[edges[e].second].state == IN_GRAPH)
{
vertices[edges[e].second].degree--;
}
else if (edges[e].second == v
&& vertices[edges[e].first].state == IN_GRAPH)
{
vertices[edges[e].first].degree--;
}
}
}

/* Create the MIS array from the vertices structure */
static unsigned int *create_mis(const vertex_info *vertices, unsigned int order,
unsigned int m)
{
unsigned int *mis = malloc(m * sizeof(unsigned int));
if (mis) {
unsigned int v, m = 0;
for (v = 0; v < order; v++) {
if (vertices[v].state == IN_MIS) {
mis[m++] = v;
}
}
}
return mis;
}

unsigned int maximum_independent_set(const edge *edges, unsigned int size,
unsigned int order, unsigned int **mis)
{
unsigned int m = 0;
vertex_info *vertices;
unsigned int finished = 0;
unsigned int i;

/* Create vertices structure */
vertices = create_vertices(edges, size, order);

/* Main algorithm */
while (!finished) {
/* Find a vertex of minimum degree */
int v = min_degree_vertex(vertices, order);
if (v != -1) {
/* Put it in the independent set */
move_vertex(vertices, order, edges, size, v, IN_MIS);
m++;
/* Remove its neighbours from the graph */
for (i = 0; i < size; i++) {
if (edges[i].first == v
&& vertices[edges[i].second].state == IN_GRAPH)
{
move_vertex(vertices, order, edges, size,
}
else if (edges[i].second == v
&& vertices[edges[i].first].state == IN_GRAPH)
{
move_vertex(vertices, order, edges, size,
}
}
}
else {
finished = 1;
}
}

/* Create and populate MIS array */
*mis = create_mis(vertices, order, m);
if (*mis == NULL) {
m = 0;
}

free(vertices);

return m;
}


An example program to find an MIS in the graph shown above:

#include <stdio.h>
#include <stdlib.h>

/* Create a wheel graph of order n */
unsigned int wheel_graph(unsigned int n, edge **edges)
{
const unsigned int size = 2 * n - 2;
*edges = malloc(size * sizeof(edge));
if (*edges != NULL) {
/* Create the rim */
unsigned int i;
for (i = 0; i < n - 2; i++) {
(*edges)[i].first = i;
(*edges)[i].second = i + 1;
}
(*edges)[i].first = n - 2;
(*edges)[i].second = 0;
/* Create the spokes */
for (i = 0; i < n - 1; i++) {
(*edges)[n + i - 1].first = i;
(*edges)[n + i - 1].second = n - 1;
}
}
return size;
}

static void print_mis(const unsigned int *mis, size_t m)
{
unsigned int i;
for (i = 0; i < m; i++) {
printf("%u ", mis[i]);
}
putchar('\n');
}

int main(void)
{
unsigned int order = 7; /* Vertices */
unsigned int *mis;
edge *edges;
unsigned int size = wheel_graph(order, &edges);
unsigned m = maximum_independent_set(edges, size, order, &mis);
print_mis(mis, m);
free(mis);
free(edges);
return 0;
}


The output:

0 2 4


# Greedy Set Cover in Python

In the Set Cover problem, we are given a universal set $$U$$ and a family of subsets $$S_1, \ldots, S_k \subseteq U$$. A set cover is a collection of subsets $$C$$ from $$S_1, \ldots, S_k$$ whose union is the universal set $$U$$. We would like to minimise $$\left\vert{C}\right\vert$$.

The problem of finding the optimum $$C$$ is NP-Complete, but a greedy algorithm can give an $$O(log_e n)$$ approximation to optimal solution.

The greedy algorithm selects the set $$S_i$$ containing the largest number of uncovered points at each step, until all of the points have been covered.

Below is an implementation in Python:

def set_cover(universe, subsets):
"""Find a family of subsets that covers the universal set"""
elements = set(e for s in subsets for e in s)
# Check the subsets cover the universe
if elements != universe:
return None
covered = set()
cover = []
# Greedily add the subsets with the most uncovered points
while covered != elements:
subset = max(subsets, key=lambda s: len(s - covered))
cover.append(subset)
covered |= subset

return cover

def main():
universe = set(range(1, 11))
subsets = [set([1, 2, 3, 8, 9, 10]),
set([1, 2, 3, 4, 5]),
set([4, 5, 7]),
set([5, 6, 7]),
set([6, 7, 8, 9, 10])]
cover = set_cover(universe, subsets)
print(cover)

if __name__ == '__main__':
main()


Output:

[set([1, 2, 3, 8, 9, 10]), set([4, 5, 7]), set([5, 6, 7])]


# Greedy HornSAT in Python

Consider this logic puzzle:

If Mr. Smith has a dog, then Mrs. Brown has a cat.
If Mr. Jones has a dog, then he has a cat too.
If Mr. Smith has a dog and Mr. Jones has a cat, then Mrs. Peacock has a dog.
If Mrs. Brown and Mr. Jones share a pet of the same species, then Mr. Smith has a cat
All the men have dogs.

What can we say about who has what kind of pet?

We can encode the problem as Boolean variables. We write s, j, b, p for Boolean variables that are true if Smith, Jones, Brown, or Peacock respectively have a dog, and S, J, B, P for Boolean variables that are true if they have a cat. The puzzle can then be exressed as the following logical formula:

$$\begin{matrix} (s & \Rightarrow & B) & \land \\ (j & \Rightarrow & J) & \land \\ ((s \land J) & \Rightarrow & p) & \land \\ ((b \land j) & \Rightarrow & S) & \land \\ ((B \land J) & \Rightarrow & S) & \land \\ & & (s) & \land \\ & & (j). & \end{matrix}$$

A formula that is a conjunction of implications in which no variable is complemented is called a Horn formula. To solve the puzzle, we need to find a satisfying truth assignment for the variables in the formula. While the problem of Boolean Satisfiability (SAT) is in general intractable, Boolean satisfiability for Horn clauses – HornSAT – can be solved in linear time using a greedy algorithm.

The algorithm works as follows:

1. Make a set of truth assignments for the variables, starting with them all set to False
2. Make a set W of all of the variables that appear on the right hand side of an empty implication
3. While W is not empty:
1. Remove an arbitrary element v from W
2. Set v to True
3. For each clause c where v appears on the left hand side:
1. Delete v from the left hand side of c
2. If this makes c and empty implication, add the variable on the right hand side of c to W, unless it is already there
4. Return the set of truth assignments

Here is the implementation in Python:

def greedy_hornsat(variables, clauses):
"""Take a list of variables and horn clauses and return a truth assignment
to the variables that satisfies all of them"""
assignment = dict((v, False) for v in variables)
working = set(t for t in clauses if not len(t))
while working:
v = working.pop()
assignment[v] = True
vclauses = [ c for c in clauses if v in c]
for vclause in vclauses:
vclause.remove(v)
if not vclause:

return assignment


An example program using the puzzle above:

def main():
variables = ['s', 'j', 'b', 'p', 'S', 'J', 'B', 'P']
clauses = [(['s'], 'B'),
(['j'], 'J'),
(['s', 'J'], 'p'),
(['b', 'j'], 'S'),
(['B', 'J'], 'S'),
([], 's'),
([], 'j')]
assignment = greedy_hornsat(variables, clauses)
print(assignment)

if __name__ == '__main__':
main()


The output:

{'b': False, 'P': False, 'J': True, 'j': True, 'S': True, 'p': True, 's': True, 'B': True}


So we know that Mr. Jones and Mr. Smith both have a dog and a cat, Mrs. Brown has a cat, and Mrs. Peacock has a dog. Mrs. Brown may also have a dog, and Mrs. Peacock may also have a cat, but we don’t know those.

Reference: Notes for CS 170

# Stable Marriages in C

The stable marriages problem is to take a set of men and an equally sized set of women, and their marriage preferences, and to find the set of marriages that ensures that no two individuals not married to each other both prefer the other to their current match. The problem can be solved by a greedy algorithm as follows:

1. Take the first unengaged man
2. He proposes to his most-preferred woman to whom he has not proposed before, regardless of whether she is already engaged
3. If she is unengaged or prefers him to her current fiance, they become engaged, and the current fiance, if any is dropped
4. Continue until there are no unengaged men (and consequently no unengaged women)

Here it is in C:

/* Check if woman prefers m to p */
unsigned int woman_prefers(unsigned int w, unsigned int m, unsigned int p,
int **women_preferences, size_t n)
{
int *preferences = women_preferences[w];
unsigned int i;
/* Return on the first one found with p winning a tie */
for (i = 0; i < n; i++) {
if (preferences[i] == p) {
return 1;
}
if (preferences[i] == m) {
return 0;
}
}
return 1;
}

void stable_marriages(int **men_preferences, int **women_preferences, int *fiances, size_t n)
{
unsigned int *next_proposals; /* Index in preference list for each man */
unsigned int *free_men;
unsigned int fm = n; /* Number of free men */
unsigned int i;

next_proposals = calloc(n, sizeof(unsigned int));
free_men = malloc(n * sizeof(unsigned int));
if (next_proposals == NULL || free_men == NULL) {
free(next_proposals);
free(free_men);
return;
}
memset(fiances, -1, n * sizeof(int));
for (i = 0; i < n; i++) {
free_men[i] = i;
}

while (fm > 0) {
unsigned int m = free_men;
unsigned int w = next_proposals[m];
/* Find out if w has a partner */
unsigned int p = fiances[w];
if (p == -1) {
/* m and w get engaged */
fiances[w] = m;
free_men = free_men[fm - 1];
fm--;
}
else {
/* Check if w prefers m to p */
if (woman_prefers(w, m, p, women_preferences, n)) {
/* Break off engagement with p */
free_men = p;
/* m and w get engaged */
fiances[w] = m;
}
}
/* Don't propose to w again */
next_proposals[m]++;
}
free(next_proposals);
free(free_men);
}


Example program:

#include <stdio.h>

#include <stable_marriage.h>

int main(void)
{
/* Preferences are ids in preference order */
int m0[] = {0, 1, 2};
int m1[] = {2, 1, 0};
int m2[] = {1, 0, 2};
int w0[] = {0, 2, 1};
int w1[] = {2, 0, 1};
int w2[] = {1, 2, 0};
int *men_preferences[] = {m0, m1, m2};
int *women_preferences[] = {w0, w1, w2};
int marriages;
const size_t n = 3;
unsigned int m;

stable_marriages(men_preferences, women_preferences, marriages, n);
for (m = 0; m < n; m++) {
printf("m%d -- w%d\n", m, marriages[m]);
}
return 0;
}


Output:

m0 -- w1
m1 -- w0
m2 -- w2


# Scheduling to minimise lateness in C

In this problem, we have a single resource that processes jobs one at a time. Each job has a time requirement to complete, and a due time. The goal is to schedule the jobs so as to minimise the maximum lateness, i.e. to minimise the lateness of the latest job. This can be solved using a simple greedy algorithm:

1. Sort the jobs by due time
2. Schedule them in that order

Here is the algorithm implemented in C. It returns the lateness of the latest job, and populates an array with the order of the jobs.

#include <stdlib.h>
#include <string.h>

typedef struct  {
unsigned int time;
unsigned int due;
unsigned int index;
} job;

/* Compare jobs by due time */
static int compare_jobs(const job *job1, const job *job2)
{
if (job1->due < job2->due) {
return -1;
}
if (job1->due == job2->due) {
return 0;
}
return 1;
}

unsigned int minimise_lateness(const unsigned int *times, unsigned int *dues,
unsigned int *schedule, size_t len)
{
unsigned int i;
job *jobs;
unsigned int max_lateness = 0;
unsigned int t = 0;

jobs = malloc(len * sizeof(job));
if (jobs == NULL) {
return 0;
}
for (i = 0; i < len; i++) {
jobs[i].time = times[i];
jobs[i].due = dues[i];
jobs[i].index = i;
}
/* Sort the jobs by due time */
qsort(jobs, len, sizeof(job), (int(*)(const void *, const void *))compare_jobs);
/* Schedule them in that order and find max lateness */
for (i = 0; i < len; i++) {
schedule[i] = jobs[i].index;
t += jobs[i].time;
if (t > jobs[i].due && t - jobs[i].due > max_lateness) {
max_lateness = t - jobs[i].due;
}
}
free(jobs);
return max_lateness;
}


Example program:

#include <stdio.h>
#include <stdlib.h>

static void print_schedule(const unsigned int *schedule, const unsigned int *times,
const unsigned int *dues, size_t len)
{
unsigned int i;
unsigned int t = 0;
for (i = 0; i < len; i++) {
unsigned int finish = t + times[schedule[i]];
printf("Job %u starting at %u and finishing at %u with lateness %u\n", i,
t, finish, finish > dues[schedule[i]] ?
finish - dues[schedule[i]] : 0);
t = finish;
}
}

int main(void)
{
unsigned int times[] = {3, 2, 1, 4, 3, 2};
unsigned int dues[] = {6, 8, 9, 9, 14, 15};
const size_t len = sizeof(times) / sizeof(times);
unsigned int *schedule = malloc(len * sizeof(unsigned int));
unsigned int max_lateness = minimise_lateness(times, dues, schedule, len);
printf("Max lateness is %u\n", max_lateness);
print_schedule(schedule, times, dues, len);
free(schedule);
return 0;
}


Output:

Max lateness is 1
Job 0 starting at 0 and finishing at 3 with lateness 0
Job 1 starting at 3 and finishing at 5 with lateness 0
Job 2 starting at 5 and finishing at 6 with lateness 0
Job 3 starting at 6 and finishing at 10 with lateness 1
Job 4 starting at 10 and finishing at 13 with lateness 0
Job 5 starting at 13 and finishing at 15 with lateness 0


# Interval Scheduling in C

In the interval scheduling problem, we have a set of jobs J, each of which has a start time an end time. The goal is to find the largest subset of jobs that can be scheduled such that they don’t overlap. This can be solved using a greedy algorithm:

1. Sort the set of jobs J by finishing time
2. Begin with an empty set S of scheduled jobs
3. For each job in J, add it to S if it is compatible with all of the other jobs in S

A job is compatible with another if they don’t overlap in time. Since we have already sorted by finish time, a job will be compatible with all of the jobs in S as long as its start time is greater than the finish time of the last job added to S.

typedef struct {
unsigned int start;
unsigned int finish;
unsigned int index;
} job;

/* Compare jobs by finishing time */
int compare_jobs(const job *job1, const job *job2)
{
if (job1->finish < job2->finish) {
return -1;
}
if (job1->finish == job2->finish) {
return 0;
}
return 1;
}

unsigned int interval_scheduling(const unsigned int *starts, const unsigned int *finishes,
unsigned int *schedule, size_t len)
{
unsigned int i;
job *jobs;
job *last;
unsigned int count = 0;

jobs = malloc(len * sizeof(job));
if (jobs == NULL) {
return 0;
}
for (i = 0; i < len; i++) {
jobs[i].start = starts[i];
jobs[i].finish = finishes[i];
jobs[i].index = i;
}
/* Sort the jobs by finishing time */
qsort(jobs, len, sizeof(job), (int(*)(const void *, const void *))compare_jobs);
memset(schedule, 0, len * sizeof(unsigned int));
for (i = 0; i < len; i++) {
/* A job is compatible if its start time >= the last added job's finish time */
if (i == 0 || jobs[i].start >= last->finish) {
schedule[jobs[i].index] = 1;
last = &(jobs[i]);
count++;
}
}
free(jobs);
return count;
}



An example program:

void print_schedule(const unsigned int *schedule, const unsigned int *starts,
const unsigned int *finishes, size_t len)
{
unsigned int i;
for (i = 0; i < len; i++) {
if (schedule[i]) {
printf("Job %u starting at %u and finishing at %u\n", i,
starts[i], finishes[i]);
}
}
}

int main(void)
{
unsigned int starts[] = {0, 1, 3, 4, 5, 6, 8};
unsigned int finishes[] = {6, 4, 5, 8, 7, 9, 10, 11};
const size_t len = sizeof(starts) / sizeof(starts);
unsigned int *schedule = malloc(len * sizeof(unsigned int));
unsigned int jobs = interval_scheduling(starts, finishes, schedule, len);
printf("There are %d jobs:\n", jobs);
print_schedule(schedule, starts, finishes, len);
free(schedule);
return 0;
}


Output:

There are 3 jobs:
Job 1 starting at 1 and finishing at 4
Job 4 starting at 5 and finishing at 7
Job 6 starting at 8 and finishing at 10


# Fractional Knapsack in C

The fractional knapsack problem is to fill a knapsack of given capacity with unique items of a given weight and value so as to maximise the value of the knapsack, with breaking items up being permitted. This last relaxation of the usual conditions means that we can use a greedy algorithm to solve the problem:

1. Sort the items in decreasing order of value / weight
2. Take as much as you can of each item until the knapsack is at capacity

Only the last item can need to be broken up because the sorting by value / weight guarantees that the current item is the optimum one to take, so we should take as much as it as we can, which until the knapsack cannot contain it, will be the whole item. When the knapsack cannot contain it we enough of it to fill the remaining capacity and so are at the last item.

This is the algorithm in C. I have assumed that value / weight is always a whole number for simplicity, but one could easily modify it for continuous values.

typedef struct {
unsigned int value;
unsigned int weight;
unsigned int index;
} item;

/* Compare items by greater value / weight */
int compare_items(const item *item1, const item *item2)
{
unsigned int vw1 = item1->value / item1->weight;
unsigned int vw2 = item2->value / item2->weight;
if (vw1 > vw2) {
return -1;
}
else if (vw1 == vw2) {
return 0;
}
return 1;
}

unsigned int fractional_knapsack(const unsigned int *values, const unsigned int *weights,
unsigned int *knapsack, size_t len, unsigned int capacity)
{
unsigned int i;
unsigned int remaining = capacity;
unsigned int value = 0;
item *items;

items = malloc(len * sizeof(item));
if (items == NULL) {
return 0;
}
for (i = 0; i < len; i++) {
items[i].value = values[i];
items[i].weight = weights[i];
items[i].index = i;
}
/* Sort items in descending order by value / weight */
qsort(items, len, sizeof(item), (int(*)(const void *, const void *))compare_items);
for (i = 0; i < len && remaining > 0; i++) {
if (items[i].weight < remaining) {
/* Take all of this item */
value += items[i].value;
knapsack[items[i].index] = items[i].weight;
remaining -= items[i].weight;
}
else {
/* Take a fraction of this item */
value += (items[i].value * remaining) / items[i].weight;
knapsack[items[i].index] = remaining;
remaining = 0;
}
}
free(items);

return value;
}


Example program:

void print_knapsack(const unsigned int *knapsack, const unsigned int * values,
const unsigned int *weights, size_t len)
{
unsigned int i;
for (i = 0; i < len; i++) {
if (knapsack[i] > 0) {
if (knapsack[i] == weights[i]) {
printf("1 ");
}
else {
printf("%u/%u ", knapsack[i], weights[i]);
}
printf("of item %u (weight %u value %u)\n", i, weights[i], values[i]);
}
}
}

int main(void)
{
unsigned int values[] = { 200, 240, 140, 150 };
unsigned int weights[] = { 1, 3, 2, 5 };
const size_t len = sizeof(values) / sizeof(unsigned int);
unsigned int *knapsack;
const unsigned int capacity = 5;
unsigned int value;

knapsack = calloc(len, sizeof(unsigned int));
value = fractional_knapsack(values, weights, knapsack, len, capacity);
printf("Value is %d\n", value);
print_knapsack(knapsack, values, weights, len);
free(knapsack);

return 0;
}


Output:

Value is 510
1 of item 0 (weight 1 value 200)
1 of item 1 (weight 3 value 240)
1/2 of item 2 (weight 2 value 140)


# Greedy algorithm for making change in C

Making change for a canonical coin system is one of the simplest greedy algorithms, and one with which everyone is familiar. The algorithm is simply:

1. Start with a list of coin values to use (the system), and the target value
2. Find the largest coin that we can use
3. Use as many of it as we can, subtracting their value from the total
4. Stop when the remaining total is 0

Here is what it looks like in C:

unsigned int make_change(unsigned int *system, unsigned int *solution, size_t n,
unsigned int amount)
{
unsigned int coin;
int remaining = amount;

coin = 0;

/* Main loop */
while (remaining > 0 && coin < n) {
/* Find out if we can use this coin */
if (remaining >= system[coin]) {
/* Use as many of this coin as we can */
solution[coin] = remaining / system[coin];
remaining = remaining % system[coin];
}
/* Move to next coin */
coin++;
}
if (remaining > 0) {
/* This means the coin system is not sensible */
return 0;
}
return 1;
}


An example program:

#include <stdio.h>
#include <stdlib.h>

void print_solution(const unsigned int *system, const unsigned int *coins, size_t n, FILE *fout)
{
unsigned int coin;
/* Print the number of each coin type used */
for (coin = 0; coin < n; coin++) {
if (coins[coin]) {
fprintf(fout, "%d x %d\n", coins[coin], system[coin]);
}
}
}

int main(void)
{
unsigned int system[] = {200, 100, 50, 20, 10, 5, 2, 1};
const size_t n = sizeof(system) / sizeof(unsigned int);

unsigned int *coins = calloc(n, sizeof(unsigned int));
const unsigned int amount = 1741;
unsigned int result = make_change(system, coins, n, amount);
if (result) {
print_solution(system, coins, n, stdout);
}
else {
printf("No solution!\n");
}
free(coins);
return 0;
}


Output:

8 x 200
1 x 100
2 x 20
1 x 1