unix/fb_arc_set

fb_arc_set

The aim of these 2 modules is to implement an algorithm which removes cycles in a directed graph by removing the least edges possible. A set of edges which must be removed to make a graph acyclic is also called a feedback arc set; and the set with the least edges is a minimal feedback arc set.

Algorithm

A simple randomized algorithm for this problem generates a feedback arc set by executing following steps:

• Order the vertices of the graph randomly, i.e. generate a random permutation of the set of vertices.
• Select all edges ( u, v ) for which u > v in the ordering. These edges form a feedback arc set.

generator

The generator program takes a graph as input. The program repeatedly generates a random solution to the problem as described above and writes its result to a circular buffer. It repeats this procedure until it is notified by the supervisor to terminate.

SYNOPSIS
generator EDGE1...
EXAMPLE
generator 0-1 1-2 1-3 1-4 2-4 3-6 4-3 4-5 6-0

supervisor

The supervisor sets up the shared memory and the semaphores and initializes the circular buffer required for the communication with the generators. It then waits for the generators to write solutions to the circular buffer. The supervisor program takes no arguments. Once initialization is complete, the supervisor reads the solutions from the circular buffer and remem- bers the best solution so far, i.e. the solution with the least edges. Every time a better solution than the previous best solution is found, the supervisor writes the new solution to standard output. If a generator writes a solution with 0 edges to the circular buffer, then the graph is acyclic and the supervisor terminates. Otherwise the supervisor keeps reading results from the circular buffer until it receives a SIGINT or a SIGTERM signal. Before terminating, the supervisor notifies all generators that they should terminate as well. This can be done by setting a variable in the shared memory, which is checked by the generator processes before writing to the buffer. The supervisor then unlinks all shared resources and exits

Note: The description is from the task I got from TU.