[Algoritmi] An algorithm for finding Hamilton Cyciles in Random Directed Graphs(A.M Frieze)

[mikael2]

Dove posso trovare il codice sorgente di questo algoritmo??

[Luc@s]

Google è tuo amico.
http://goo.gl/WNAxT (il primo risultato (il PDF) )

[apatriarca]

Non c'è alcuna garanzia che il codice di un articolo sia in qualche modo disponibile. Anzi, normalmente non lo è..

[Luc@s]

"apatriarca":Non c'è alcuna garanzia che il codice di un articolo sia in qualche modo disponibile. Anzi, normalmente non lo è..

ma l'abstract almeno ti da un idea

[mikael2]

grazie, però non ci capisco niente qualcuno potrebbe aiutarmi a capire come funziona ed passo passo ad implementare qualcosa in c?

[apatriarca]

Implementare un algoritmo da un paper che non si è mai letto, senza aver mai visto molti dei risultati e della teoria che è descritta non è un lavoro da poco. Aiutarti a scrivere questo algoritmo significa in pratica dovercelo fare anche noi il tuo lavoro. A meno di trovarti qualcuno che ha già visto qualcosa di quell'articolo dubito che troverai qualcuno disposto a farlo.

Puoi iniziare a leggerti qualcosa come il seguente se non hai idea di come iniziare: http://codecapsule.com/2012/01/18/how-to-implement-a-paper/

[mikael2]

grazie per l'aiuto, spero che ci sia qualcuno che ha già visto qualcosa di quell'articolo

[apatriarca]

Si tratta di una specie di compito? Oppure ne hai bisogno per qualcos'altro?

[mikael2]

Mi serve per un progetto diciamo, dovrei cercare di capire ed implementare una possibile versione dell'algoritmo in C, ma mi sembra una cosa impossibile da fare

[apatriarca]

Ma hai già qualcosa da cui partire? Per esempio come è rappresentato il grafo?

[mikael2]

ho solo il documento in inglese dell'algoritmo e basta

[apatriarca]

Ma cosa deve fare esattamente il programma? Al di fuori dell'algoritmo..

[mikael2]

è un progetto per la tesi che mi ha chiesto di provare a fare un Prof

[apatriarca]

Hai provato allora a chiedere consiglio/aiuto al professore o a qualche suo assistente/dottorando? Forse loro conoscono questo algoritmo un po' meglio di noi.. e sanno darti qualche indicazione in più.

[mikael2]

magari, assistenti non ne ha ed il prof non l'ha mai implementato o provato ad implementare.

[apatriarca]

Però spero che almeno lo conosca.. O neanche quello?

[mikael2]

mi sa tanto di no

[apatriarca]

... qual'è l'argomento della tua tesi?

[mikael2]

diciamo questo. Come posso scrivere in C cicli da combinare???

[apatriarca]

Credo che ci siano domande più importanti da rispondere prima, come quale rappresentazione del grafo vuoi usare nel tuo codice. Dopodiché ovviamente è necessario pensare a come rappresentare un ciclo.. Ma credo ci si possa accontentare del metodo più semplice: una semplice lista di archi collegati tra di loro.

[mikael2]

Leggere in input un grafo orientato G=(V,E) ed una sequenza S di vertici di G. Verifica se S e' un ciclo hamiltoniano,
Il grafo G è rappresentato utilizzando la struttura dati delle liste di adiacenza,sequenza S è rappresentata mediante una lista.
Va bene Così???

#include <stdlib.h>
#include <stdio.h>

#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<n; 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<n; i++) {
    printf("Lista di adiacenza del vertice %d\n", i);
    l[i] = 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<n; i++)
    visitato[i] = 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<n && flag==1; i++)
    flag = visitato[i];
  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);
}