/* informação nas ligações (peso?) */
typedef int Info;

/* obs.: se existir informação associada aos vértices,
   esta terá de ser armazenada num vector à parte. */



/* Matriz de adjacência */
#define MaxVert 100
typedef struct AMGraph_t {
  int nVert;
  Info arco[MaxVert][MaxVert];
} AMGraph;



/* Listas de adjacência */
typedef struct ALNode_t {
  int vert;	// índice do vértice
  Info info;	// inf. (peso)
  struct ALNode_t *next;
} ALNode;

typedef struct ALGraph_t {
  int nVert;
  ALNode * adjL[MaxVert];
} ALGraph;


/* funções para manipular LISTAS (DE ADJACÊNCIA) */
void showList(ALNode *node);
ALNode* addList(ALNode *list, int node, Info p);
ALNode* findList(ALNode *list, int node);
ALNode* dupList(ALNode *list);
void freeList(ALNode *list);

/* MATRIZ DE ADJACÊNCIA */
// Inicializa estrutura de um grafo
AMGraph init_am(int n);
// Visualiza grafo
void show_am(AMGraph g);
// calcula predecessores
ALNode* preds_am(AMGraph g, int node);
// calcula sucessores
ALNode* sucs_am(AMGraph g, int node);
// calcula converso de um grafo (inverte)
AMGraph converse_am(AMGraph g);

/* LISTAS DE ADJACÊNCIA */
// Inicializa estrutura de um grafo
ALGraph init_al(int n);
// Visualiza informação do grafo
void show_al(ALGraph g);
// calcula sucessores
ALNode* sucs_al(ALGraph g, int node);
// calcula predecessores
ALNode* preds_al(ALGraph g, int node);
// determina (se existir) caminho entre dois vértices
ALNode* daCaminho_al(ALGraph g, int orig, int dest);


/* CONVERSÃO DE REPRESENTAÇÕES... */
// Converte representação baseada em Matrizes de Adjacência
// para Listas de Adjacência.
ALGraph am2al(AMGraph g1);
// Converte representação baseada em Listas de Adjacência
// para Matrizes de Adjacência
AMGraph al2am(ALGraph g1);