Discussion :

[The Void]

Bonjour,

J'ai déjà codé un certain nombre d'algorithmes classiques sur les graphes en C++, en gros la plupart de ceux du Cormen: Dijkstra, Prim, Ford-Fulkerson, couplage max, et pas mal d'autres (~1500 lignes).

Mon but est d'avoir quelque chose de réutilisable, robuste, rapide, facile à maintenir, en POO, et qui soit utilisable pour écrire des algorithmes pour des sites/concours comme ACM/ICPC, Project Euler...

J'aimerais avoir votre avis sur la représentation que j'ai choisie (je me suis inspiré de Algorithms in C++: Graph Algorithms: Amazon.fr: Robert Sedgewick, Christopher J. Van Wyk: Livres en anglais@@AMEPARAM@@http://ecx.images-amazon.com/images/I/51W6TWK6V7L.@@AMEPARAM@@51W6TWK6V7L)

Je stock des pointeurs pour éviter des copies de gros objets, pensez vous que c'est une bonne idée?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
 
template<typename type_wt = int> class Edge_Base
{ 
	const int v_,w_; type_wt wt_; 
public:
	Edge_Base(): v_(0), w_(0), wt_(0) { };
	/// Crée une arête de v à w et de poids wt
	Edge_Base(int v, int w, type_wt wt): v_(v), w_(w), wt_(wt) { };
	inline int v() const { return v_; } 
	inline int w() const { return w_; } 
	inline type_wt wt() const { return wt_; } 
	/// Renvoie l'extremité autre que u
	inline int other(int u) const 
	{
		if(u==v_) return w_;
		if(u==w_) return v_;
	}
	inline bool from (int v) const 
	{ return v_ == v; } 
	bool operator==(const Edge_Base &e) const
	{
		return (e.v() == v_ && e.w() == w_) || (e.w() == v_ && e.v() == w_);
	}
	bool operator<(const Edge_Base &e) const
	{
		return wt < e.wt;
	}
};
 
template<class Edge = Edge_Base<> > class Graph_list 
{ 
	int Vcnt, Ecnt; bool digraph;
	struct node
	{ Edge* e; node* next; node* last; 
	node(Edge* e, node* next, node* last): e(e), next(next), last(last) {};
	~node() {}
	};
public:
	vector <node*> adj;
	/// Crée un graphe à V sommets par liste d'adjacence
	/// digraph : si true, le graphe est orienté
	Graph_list(int V, bool digraph = false) : adj(V, (node*)0), Vcnt(V), Ecnt(0), digraph(digraph) { }
	~Graph_list() { }
	int deg(int v) const
	{
		iterator it(*this, v);
		int res;
		for(res = 0, it.beg(); !it.end(); res++, it.nxt());
		   return res;
	}
	/// Détruit tous les nodes* et Edge*
	void destroy_ptr()
	{
		for(int i = 0; i < adj.size(); i++)
		{
			node *cur = adj[i], *nxt = 0;
			while(cur != 0) 
			{
				nxt = cur->next;
				if(digraph || cur->e->from(i)) // Evite d'avoir des pointeurs invalides
					delete cur->e;
				delete cur;
				cur = nxt;
			}
			adj[i] = 0;
		}
	}
	void resize(int V_)
	{
		Vcnt = V_;
		adj.resize(Vcnt, (node*)0);
	}
	inline int V() const { return Vcnt; }
	inline int E() const { return Ecnt; }
	inline bool directed() const { return digraph; }
	/// Si !directed : les deux arêtes ajoutées correspondent au même pointeur si sameEdgePtr, 
	/// sinon on crée un nouveau Edge* pour l'arête réciproque
	void insert(Edge *e, bool sameEdgePtr = true)
	{ 
		node * tmp = adj[e->v()];
		adj[e->v()] = new node(e, tmp, 0);
		if(tmp)
			tmp->last = adj[e->v()];
		if (!digraph) 
		{
			node * tmp_ = adj[e->w()];
			if(sameEdgePtr) // warning : ne pas écrire adj[e->w()] = adj[e->v()]; car sinon les nodes sont les mêmes!
				adj[e->w()] = new node(e, tmp_, 0);  
			else
				adj[e->w()] = new node(new Edge(*e), tmp_, 0); 
			if(tmp_)
				tmp_->last = adj[e->w()];
		}
		Ecnt++;
	} 
	inline void remove(int v)
	{
		node *cur = adj[v], *nxt = 0;
		while(cur != 0) 
		{
			nxt = cur->next;
			Edge *e = cur->e;
			if(!digraph)
				remove(*e, e->other(v));
			delete cur->e;
			delete cur;
			cur = nxt;
		}
		adj[v] = 0; // important
	}
	// remove l'Edge e dans adj[v]
	inline void remove(Edge e, int v)
	{
		for(node *cur = adj[v]; cur; cur = cur->next)
			if(*cur->e == e)
				remove_node(cur, v);
	}
	/// Appelle remove_node sur le(s) node* associé(s) à e, en utilisant == 
	inline void remove(Edge e)
	{
		remove(e, e.v());
		remove(e, e.w());
	}
	/// Supprime t dans adj[posInAdj]
	inline void remove_node(node *t, int posInAdj)
	{
		assert(t);
		if(!t->last)
		{
			if(!t->next) 
				adj[posInAdj] = 0;
			else {
				t->next->last = 0;	
				adj[posInAdj] = t->next;
			}
		}
		else 
		{
			if(!t->next) 
				t->last->next = 0;
			else
			{
				t->last->next = t->next;
				t->next->last = t->last;
			}
		}
	}
 
	class iterator;
	friend class iterator;
	class iterator_all;
	friend class iterator_all;
};
template<class Edge = Edge_Base<> > class Graph_list<Edge>::iterator
{ 
	const Graph_list<Edge> &G;
	int v;
	node* t;
public:
	/// Crée un iterateur sur les arêtes dont une extremité est v
	iterator(const Graph_list<Edge> &G, int v) : G(G), v(v), t(0) {}
	  inline Edge* beg()
	  { t = G.adj[v]; return t ? t->e : 0; }
	  inline Edge* nxt()
	  { if (t) t = t->next; return t ? t->e : 0; }
	  /// Renvoie true ssi il n'y plus d'arête à parcourir
	  inline bool end() { return t == 0; }
};

Un exemple important d'algorithme (parcours en largeur):
Je met un foncteur Proc qui doit s'appliquer sur chaque sommet et qui donne la condition de visite d'une arête, pensez vous que les performances sont trop diminuées? Que c'est vraiment utile? (je m'en sert par exemple dans Ford-Fulkerson en s'arrêtant dès qu'un sommet but est trouvé et en passant par une arête seulement si elle a une capacité non nulle) Faudrait-il mieux recoder le parcours à chaque fois?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template<class Edge = Edge_Base<>, class Proc = pr::Proc_Base<Edge>, class Graph = Graph_list<Edge> > class BFS
{
	const Graph &G;
	Proc &proc;
public:
	BFS(const Graph &G, Proc &proc) : G(G), proc(proc) {}
	/// Parcours en largeur à partir de source en appliquant proc à chaque sommet s, tant que proc(s) est faux
	/// et en visitant Edge *e en direction de v si proc(e, v) est vrai
	/// Renvoie vrai ssi un sommet v tel que proc(v) est rencontré
	bool operator()(int source = 0)
	{
		proc.init(source);
		queue<int> q;
		q.push(source);
		while(q.size())
		{
			int next = q.front();
			q.pop();
			if(proc.trait(next))
					return true;
			typename Graph::iterator it(G, next);
			for(Edge *e = it.beg(); !it.end(); e = it.nxt())
			{
				int other = e->other(next);
				if(!proc.toVisit(e, other)) continue;
				q.push(other);
			}
		}
		return false;
	}
};

Exemple de foncteur pouvant être passé à BFS:
(je suis pas très satisfait de pred[source] = reinterpret_cast<Edge*>(-1);, mais c'est pour éviter de le revisiter, et tenir un tableau de bool prendrait plus de mémoire...)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
namespace pr
{
template<class Edge = Edge_Base<> > class Proc_Base
{
public:
	int V;
	vector<Edge*> pred; // pred[v] : père de v 
	Proc_Base(int V) : V(V) { }
	void init(int source) 
	{
		pred.clear();
		pred.resize(V, reinterpret_cast<Edge*>(0));
		pred[source] = reinterpret_cast<Edge*>(-1); // choix discutable...
	}
	inline bool trait(int v) { return false; }
	bool toVisit(Edge *e, int toVertex)
	{ 
		if(pred[toVertex] != reinterpret_cast<Edge*>(0)) // pred[source] == -1;
			return false;
		pred[toVertex] = e; 
		return true; 
	}
};
template<class Edge = Edge_Base<> > class SearchVertex : public Proc_Base<Edge>
{
public:
	int target;
	SearchVertex(int V, int target) : Proc_Base<Edge>(V), target(target) { }
	inline bool trait(int v) { 
		return v == target; 
	}
};
}

Exemple d'utilisation plus générale:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
	Rdm_Graph<> G;
	io::show(G);
	Dijkstra<> dij(G);
	dij(0);
	Bellman<> bel(G);
	bel(0);
	cout<<"Dijkstra : "<<endl;
	for(int i = 0; i < dij.pred.size(); i++) {
		if(dij.pred[i] && dij.pred[i] != (edge*)(-1)) /// attention : pred[source] == (edge*)(-1)
			cout<<(*dij.pred[i])<<" ";
	}
	cout<<endl;
	cout<<"Bellman : "<<endl;
	for(int i = 0; i < bel.pred.size(); i++) {
		if(bel.pred[i] && bel.pred[i] != (edge*)(-1))
		cout<<(*bel.pred[i])<<" ";
	}
	cout<<endl<<endl;
 
	Rdm_Graph<int, flow> R;
	io_flow::show_cap(R);
	pr::NoNullCap<> nonull(R.V(), 1);
	typedef pr::NoNullCap<flow> type_proc_dfs;
	typedef DFS<type_proc_dfs, flow> type_ful_dfs;
	type_proc_dfs proc_dfs(R.V(), 1);
	Fulkerson<int, flow> ful(R, nonull);
	Fulkerson<int, flow, type_proc_dfs, Rdm_Graph<int, flow>, type_ful_dfs> ful_dfs(R, proc_dfs);
	ful_dfs(0, 1);
	io_flow::show_flow(R);
	cout<<endl;
	ful(0, 1);
	io_flow::show_flow(R);
	cout<<"maxflow avec bfs: "<<ful.get_outflow(0)<<endl;
	cout<<"maxflow avec dfs: "<<ful_dfs.get_outflow(0)<<endl<<endl;
	Cut<flow> cut(R);
	cut(0);
	cout<<"Min cut : "<<endl;
	int mincut_val = 0;
	for(list<flow*>::iterator it = cut.cut.begin(); it != cut.cut.end(); ++it)
	{
		cout<<**it<<" ";
		mincut_val += (*it)->cap();
	}
	cout<<"valeur : "<<mincut_val<<endl;

Merci d'avance pour vos remarques (si vous voulez voir plus de code c'est possible)