C:Workshop:2015:D4

The MCQ web site is: http://rendu.infoprepa.epita.fr/intra

Introduction

Our is to implement graph algorithm, all this session will be based on types and data from algorithmic tutorial, you can use the support from [1], we will follow a similar structure.

Full Dynamics Graph Implementation

We use a C version of the algorithmic tutorial data structure (again here [2]):

// graph.h
 
# ifndef GRAPH_H_
# define GRAPH_H_
 
typedef struct s_som   *t_listsom;
typedef struct s_ladj  *t_listadj;
 
struct s_som {
  int           som;
  t_listadj     succ, pred;
  t_listsom     next;
};
 
struct s_ladj {
  int           nb;
  float         cost;
  t_listsom     vsom;
  t_listadj     next;
};
 
struct t_graph_dyn {
  unsigned      order;
  int           directed;
  t_listsom     lsom;
};
 
# endif /* GRAPH_H_ */

This translation try to keep the spirit of the original version, thus it uses typedef to define pointed type name.

Creating graph

We now need some operations to create a graph.

• Implement the following function

struct t_graph_dyn* build_graph(unsigned order, int directed);

This function create a graph with the provided order and directed flag. It will also initialize the vertices list (lsom list).

• Implement the following function

void add_edge(struct t_graph_dyn *g, int src, int dst, int nb, float cost);

This function add an edge to the graph. If the graph is directed, the edge will be added to the source vertex src in the successors list and added to the destination vertex dst in its predecessors list. If the graph is undirected, it will add the edge on both vertices (in the successors list.)

Loading a graph

In order to load a graph, we'll use the format from the Lasagne Project. This format is pretty simple: the first line contains the order of the graph, the next order lines give the degree of each vertex (useless for us) and finally it lists a series of edge, one per line, as a pair of integer with the source first.

Here is an example of graph:

7
0 1
1 3
2 3
3 3
4 2
5 1
6 1
0 1
1 2
1 3
2 4
2 5
3 4
3 6

• Write the following function:

struct t_graph_dyn* load_graph(char *fname);

This function load a graph from a file, and build it. The built graph is an undirected graph where all the cost on edge are 1.

Dot output

• Write the following function:

void print_dot(struct t_graph_dyn *g);

This function will output the graph in the dot format, like the following example:

graph G {
  0 -- 1;
  1 -- 2;
  1 -- 3;
  2 -- 4;
  2 -- 5;
  3 -- 4;
  3 -- 6;
}

You can generate an image with this file this way:

> dot -tpng mygraph.dot -O

Depth First Traversal

We now want to build a DFS that print the spanning tree (use information from the previous link.) We want to produce the spanning tree as a dot file, so your algorithm will print discovery edges (the one of the tree) using src -> dst; syntax.

• Implement the following functions

// the recursive function
void dfs_rec(t_listsom ps, int parent[]);
// The main function
void dfs_spanning_tree(struct t_graph_dyn *g, int src);

We don't need a complete traversal of the graph, only one dfs from the src vertex.

Breadth First

• Do the same as the previous function for the BFS traversal.