Algoritmo in C

[mikael2]

Qualcuno di voi conosce questi Algoritmi :
1)Algoritmo for finding Hamilton Cycles in random directed graphs
2))Algoritmo for directed Hamilton Cycles Problem

dovrei implementarli in C partendo da questo pseudo codice, Qualcuno di voi sa farlo?

pseudo-codice:

INPUT Directed non complete graph G=(V,E) with |V|=n.
1 define matrix C as in Section 2.1 M:=1
2 define subcycle collection set W:=(insieme vuoto).
3 For s=1,...,n
4 Solve AP on istance matrix C with soution value g,AP solution
(v1,v2),(v2,vi2)...($v_(n-1)$,$v_(i n-1)$),($v_n$,$v_(i n)$) number of cycles k.
IF g>=M
then stop with no HC
else if k=1

then stop with HC being the AP solution.
Apply KSP to the cycles , and recive solution value h and complete cycle (w1,w2,...,wn,w1)
if h=0
then stop with HC (w1,w2,...wn,w1)
For t=1,..,n
$c_(vt)$,$v_(it)$=$c_(vt)$,$v_(it)$+1
M=n * MAx{$c_(i,j)$ $\epsilon$ E}+1
$c_(i,j)$=M for all (i,j) $notin$ E
Add each subcycle of AP solution to W.

ecc(ci sono altre linee)

[hamming_burst]

Ciao,

cosa non ti è chiaro in particolare di questi pseudo-codici per non riuscirli a tradurre in codice?

[mikael2]

non so proprio da dove partire e come tradurli in C, ho bisogno di qualcuno ke mi possa guidare

[vict85]

Che punto della traduzione ti blocca?

[mikael2]

tutto xkè nn so da dove partire e come partire

[apatriarca]

Ma il grafo è già implementato? Il codice per "solve AP" (non sono certo di capire a cosa si riferisca) è già implementato? Non si capisce molto sull'algoritmo da quello che hai scritto e ancora meno è chiaro che cosa tu debba esattamente implementare. Devi scrivere tutto da zero o solo una funzione utilizzando una qualche libreria già fatta?

[mikael2]

in questo link c è il documento x cui dovrei creare l agoritmo in C a partire da quanto descritto:
http://www.google.it/url?sa=t&rct=j&q=h ... LA&cad=rja
io non ci capisco niente

[apatriarca]

Hai compreso l'algoritmo? Hai idea di come implementare un grafo in C? Hai idea di come implementare i passaggi dell'algoritmo in C?

[mikael2]

No ,mi puoi spiegare un po di tutto ciò e guidarmi alla creazione dell'algoritmo

[vict85]

Quali sono le tue conoscenze del C? Perché devi implementare questo algoritmo?

[mikael2]

ho fatto c++, ultimamente programmo in c#, il c non l ho mai usato, è un compito ke devo cercare di svolgere

[apatriarca]

Come inizieresti a sviluppare questo tipo di esercizio in C++ o C# (mi è indifferente quale scegli perché li conosco entrambi anche se forse il C++ è un po' più simile al C)? La struttura generale del programma in C non è molto diversa da quella negli altri linguaggi e anche se non esistono le classi, è perfettamente possibile usare la programmazione ad oggetti se lo desideri.

[mikael2]

bisogna creare un funzione ke fa un grafo in modo casuale, dove l'utente deve inserire i vertici.Guarda questo pezzo di codice può essere migliorato in modo da corrispondere a quello ke mi serve?
/*
**
**
** Leggere in input un grafo orientato G=(V,E) ed una sequenza
** S di vertici di G. Verificare se S e' un ciclo hamiltoniano,
** ossia un ciclo semplice in G che consente di raggiungere
** tutti i vertici di G. Il grafo G deve essere rappresentato
** utilizzando la struttura dati delle liste di adiacenza, la
** sequenza S deve essere rappresentata mediante una lista.
**
*/

#include
#include

#define MAX 50

struct nodo {
int info;
struct nodo *next;
};

struct nodo *leggi_lista(void) {
struct nodo *p, *primo, *ultimo;
int a, i, n;

primo = NULL;
ultimo = NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
for (i=0; i scanf("%d", &a);
p = malloc(sizeof(struct nodo));
p->info = a;
p->next = NULL;
if (!primo)
primo = p;
if (ultimo)
ultimo->next = p;
ultimo = p;
}
return(primo);
}

int leggi_grafo(struct nodo *l[]) {
int i, n;

printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i printf("Lista di adiacenza del vertice %d\n", i);
l = leggi_lista();
}
return(n);
}

int adiacente(int u, int v, struct nodo *l[]) {
struct nodo *p;

p = l;
while (p!=NULL && p->info != v)
p = p->next;
if (p == NULL)
return(0);
else
return(1);
}

int hamiltoniano(struct nodo *primo, struct nodo *l[], int n) {
int visitato[MAX], i, flag;
struct nodo *p;

for (i=0; i visitato = 0;
p = primo;
visitato[p->info] = 1;
while (p->next != NULL && !visitato[p->next->info] && adiacente(p->info, p->next->info, l)) {
visitato[p->next->info] = 1;
p = p->next;
}
flag = 1;
for (i=0; i flag = visitato;
return(flag);
}

int main(void) {
struct nodo *lista[MAX], *primo;
int n;

n = leggi_grafo(lista);
primo = leggi_lista();
if (hamiltoniano(primo, lista, n))
printf("La sequenza di vertici e' un ciclo hamiltoniano in G.\n");
else
printf("La sequenza di vertici non e' un ciclo hamiltoniano.\n");
return(1);
}

[hamming_burst]

Guarda questo pezzo di codice può essere migliorato in modo da corrispondere a quello ke mi serve?

@mikael ascolta: abbiamo buona volontà qui sul forum (molto dipendente dagli impegni). Ma se non è corrisposta da chi chiede aiuto, dubito che qualcuno si prenda la briga di modificare, leggere, studiare un qualcosa che te non vuoi nemmeno prenderne parte.

Non è tanto una critica, ma cerca di capire chi sta dall'altra parte del computer; vedere che dobbiamo spiegarti noi tutto e come risolvere il tuo problema non è molto gradevole.

Fai così, prima di addentrarti nell'algoritmo e nella scrittura che è l'ultima cosa da fare, prendi il testo che hai linkato: studialo, spezzalo, se non comprendi un passaggio scrivi qui sul forum. E' inutile scrivere un algoritmo se non comprendi cosa e coma calcola.

Se per te il testo è troppo difficile, cercane altri su google-scholar (o chiedine un altro al tuo docente).