MorphoGraph and Imagery - Practical session 2

from an original subject in French by Michel Couprie, Gilles Bertrand

1. Preliminaries

First of all, get the file GraphesTP1.tgz and uncompress it:

    tar zxvf GraphesTP1.tgz
    rm GraphesTP1.tgz
    cd GraphesTP1; ls

1.1 First Graphs

1.1.1 Create and print a graph

In an ordinary file, enter the data of an arbitrary graph as follows:

<number_of_vertices> <number_of_arcs> 
arcs
<initial_vertex> <final_vertex>
<initial_vertex> <final_vertex>
...

For instance (see the file k5.graph) :

5 10
arcs
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

Edit the files exo111.c, exo112.c and read them. Compile the library:

    make

    make exo111.exe
    make exo112.exe

    ./exo111.exe k5.graph
    ./exo112.exe k5.graph

The latter program creates a postscript file whose name extends the file name of the given graph (eg here: k5.graph.eps). You can view the PostScript file generated with ghostview, kghostview or display :

    display k5.graph.eps

1.1.2 Generate a random graph

Edit the file exo113.c, read it, compile it, and execute it. Visualize the results for several parameter values.

1.2 First algorithms

Before going any further, study the descrption of the data structure used to represent a graph by Γ (its successors map). Also remind to refer to the documentation of the source code, including:

• source of the definition of the main data structures (graphe, cell...)
• description of the basic functions to handle graphs (see in particular AjouteArc -meaning AddArc in French -, EstSuccesseur - meaning IsSuccessor in French)
• description of the functions to handle lists (LIFO) and Boolean arrays (see in particular CreeLifoVide - meaning CreateEmptyLifo in French-, EnsembleVide - meaning EmptySet in Frence)

1.2.1 Compute the symmetric of a graph

Edit the file exo121.c, read it, compile it, and execute it. Study the function Sym. Why isn't it efficient? What is the time complexity of the algorithm?

1.2.2 Measure of computation timesdu temps

Edit the file exo122.c, read it, compile it, and execute it. Note the computation times obtained for various sizes of graphs.

1.2.3 Linear-time algorithm for computing the symmetric of a graph

In the file exo122.c, change the function Sym to make the algorithm linear (for any help, see the slides of the first lecture). Find below how to traverse a list of successors:

  pcell p;
  ...
    /* for any successor y of x */
    for (p = g->gamma[x]; p != NULL; p = p->next) 
    {
      y = p->som;    
      ...

Measure the computation time with the new version and compare.

2. Friends

Imagine a group of seven friends: Rachel, Monica, Ross, Chandler, Janice, Joe, and Phoebe. They live in New York and plan to rent two cars to spend a vacation in Florida. However, spending together the 18 hours that take the trip can be problematic if the passengers of both vehicles are not carefully selected.

In fact, you should know that

• Rachel and Ross just broke up, it would not be wise to make them travel together.
• Joe has made proposals to Rachel, so there are tensions between him and Ross.
• But Phoebe seems to try to attract the attention of Joe, which cast a chill between her and Rachel.
• Chandler just took Joe's position as captain of the football team, the result is resentment.
• Monica and Chandler are jealous of Janice, because she is pregnant and they fail to have a baby.
• Finally, Monica thinks Joe is an idiot.

Formulate this problem in terms of graphs and give a solution for this particular case.

3. Bipartite graphs

We say that a graph G = (E, Γ) is bipartite if the set E of its vertices can be partitioned into two subsets E₁ and E₂ (ie, E₁ ∪ E₂ = E and E₁ ∩ E₂ = ∅) such that an arc of G cannot link two vertices of E₁, and cannot link two vertices of E₂ either. Consider for instance

We see that G₁ is a bipartite graph with E₁ = {1, 4, 5} and E₂ = {2, 3}, and that G₂ is not a bipartite graph. We can interpret the bi-partition of the graph vertices into two subsets E₁ and E₂ as a ``coloring'' of the vertices with two distinct colors (bi-coloring), one color for E₁ and the other for E₂.

In the following, for simplicity, we assume that G is connected.

3.1 Algorithm

Propose a linear time algorithm that indicates whether a given graph G is bipartite or not, and if so, that returns a bi-coloring of G. Getting inspired by the algorithm TRANS studied in course (see slide 21 of the lecture on connectivity) might be a successful idea.

3.2 Implementation

For the implementation of your algorithm you could learn from the implementation of algorithm TRANS and of that of algorithm SCC, found in the file scc.c. It will be probably easier to copy this code and modify it (you have to understand it before that!).

You can use the field v_sommets of the graphe structure to store the colors associated with the vertices, and the function AfficheValeursSommets to display the result in text mode.

To graphically visualize the results of your algorithm, you may refer to the program demo_couleurs.c located in your directory. This program draws a graph whose vertices are named (by a string) and valued (by the field v_sommets). These values, which are integers between 0 and 4, are interpreted as colors (white, black, red, green and blue for 0, 1, 2, 3, 4 respectively). The file demo_couleurs.graph contains an example.

Test your program on several graphs that are bipartite or not, including the one from section `` Friends.''

4. Bonus (extra-work to be done after the practical session)

4.1 Property

Prove that a graph is bipartite if and only if it has no cycle of odd length.

4.2 Detect odd cycles

Given a non bipartite graph, propose and implement a method to detect and display a cycle of odd length.

4.3 Find bipartite graphs

We can now imagine two strategies for finding a bipartite graph from a graph that is not: the idea is to detect and remove cycles of odd length, by deleting arcs, or by removing vertices. In our application "friends", the first strategy consists of neglecting one or more animosity relations, the second one is more radical because it excludes friends from the group. Implement one of these two strategies.