Erreur de segmentation (core dumped) avant int main ()
alena20
Messages postés
24
Statut
Membre
-
Utilisateur anonyme -
Utilisateur anonyme -
Bonjour,
j'ai une erreur de segmentation meme avant la fonction int main() . Donc je ne peux le tracer. En fait c'est juste quand je definis le #define V 2000 ou plus, cette erreur s'apparaisse. Si je definis #define V 10 ca marche tres bien. Cette code vient de https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ Je l'ai juste un petit peu modifié. S'il faut les data fichiers je peux les fournir. Merci par avance!
j'ai une erreur de segmentation meme avant la fonction int main() . Donc je ne peux le tracer. En fait c'est juste quand je definis le #define V 2000 ou plus, cette erreur s'apparaisse. Si je definis #define V 10 ca marche tres bien. Cette code vient de https://www.geeksforgeeks.org/minimum-cut-in-a-directed-graph/ Je l'ai juste un petit peu modifié. S'il faut les data fichiers je peux les fournir. Merci par avance!
// C++ program for finding minimum cut using Ford-Fulkerson
#include <iostream>
#include<fstream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
// Number of vertices in given graph
#define V 2080
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
int bfs(int rGraph[V][V], int s, int t, int parent[])
{
cout << "int bfs no error" << endl ;
// Create a visited array and mark all vertices as not visited
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex
// as visited
queue <int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty())
{
int u = q.front();
q.pop();
for (int v=0; v<V; v++)
{
if (visited[v]==false && rGraph[u][v] > 0)
{
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return
// true, else false
return (visited[t] == true);
}
// A DFS based function to find all reachable vertices from s. The function
// marks visited[i] as true if i is reachable from s. The initial values in
// visited[] must be false. We can also use BFS to find reachable vertices
void dfs(int rGraph[V][V], int s, bool visited[])
{
visited[s] = true;
for (int i = 0; i < V; i++)
if (rGraph[s][i] && !visited[i])
dfs(rGraph, i, visited);
}
// Prints the minimum s-t cut
void minCut(int graph[V][V], int s, int t)
{
int u, v;
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
int rGraph[V][V]; // rGraph[i][j] indicates residual capacity of edge i-j
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and to store path
// Augment the flow while tere is path from source to sink
while (bfs(rGraph, s, t, parent))
{
// Find minimum residual capacity of the edhes along the
// path filled by BFS. Or we can say find the maximum flow
// through the path found.
int path_flow = INT_MAX;
for (v=t; v!=s; v=parent[v])
{
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges
// along the path
for (v=t; v != s; v=parent[v])
{
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
cout << "v=" << v << endl ; cin.get() ;
}
}
// Flow is maximum now, find vertices reachable from s
bool visited[V];
memset(visited, false, sizeof(visited));
dfs(rGraph, s, visited);
// Print all edges that are from a reachable vertex to
// non-reachable vertex in the original graph
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++)
if (visited[i] && !visited[j] && graph[i][j])
cout << i+1 << " - " << j+1 << endl;
return;
}
// Driver program to test above functions
int main()
{
cout << "no error " << endl ;
ifstream fileCrowD ("crowDist.dat") ;
float dist = 0 ;
if ( ! fileCrowD.is_open() )
cout <<" Failed to open fileCrowD" << endl;
else
cout <<"fileCrowD Opened OK" << endl;
/*while (!fileCrowD.eof()) {
fileCrowD >> dist ;
cout << dist << endl ;
}*/
int graph[V][V] ;
for (int i=0; i < V; i++) {
for (int j = 0; j < V ; j++) {
fileCrowD >> dist ; //cout << dist << " j=" << j << endl; cin.get() ;
if (dist <= 500 and dist > 0) {
graph [i][j] = 1 ; //cout << "i=" << i << " j=" << j << " graph [i][j]=" << graph [i][j] << endl ;
}
else {
graph [i][j] = 0 ;
//cout << "i=" << i << " j=" << j << " graph [i][j]=" << graph [i][j] << endl ;
}
}
//cout << "line" << i << endl ;
}
cout << "no error " << endl ;
// Let us create a graph shown in the above example
/*int graph[V][V] = { {0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};*/
minCut(graph, 0, 9) ;
return 0;
}
1 réponse
-
Salut,
Effectivement, le problème se produit avant la fonctionmain
, lors de l'allocation mémoire, sur la pile, des variables locales demain
.
Il se trouve que tu asint graph[V][V];
.
Le typeint
faisant sûrement 4 octets, et sachant#define V 2080
, tu te retrouves avec une variable de taille 2080*2080*4 = 17'305'600 octets soit plus de 16,5 Mio, ce qui est très probablement bien plus que ne peut supporter ta pile.
Alloue sur le tas (opérateurnew
) pour contourner le problème.