graphes.h

Aller à la documentation de ce fichier.

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

#define TYP_VARC long
#define TYP_VSOM long
#ifndef HUGE
#define HUGE HUGE_VAL
#endif
#define SHRT_MIN -32767 
#define SHRT_MAX +32767 
#define USHRT_MAX 65535 
#define INT_MIN -32767 
#define INT_MAX +32767 
#define UINT_MAX 65535 
#define LONG_MIN -2147483647 
#define LONG_MAX +2147483647
#define ULONG_MAX 4294967295
#define M_PI     3.14159265358979323846
#define max(X,Y) ((X)>=(Y)?(X):(Y))
#define min(X,Y) ((X)<=(Y)?(X):(Y))

/* ================================================ */
/* types publics */
/* ================================================ */

typedef struct cell {
  int som;
  TYP_VARC v_arc; 
  struct cell * next; 
} cell;

typedef cell * pcell; 


typedef struct graphe {

  /* informations globales */

  int nsom;         
  int nmaxarc;      
  int narc;         

  /* representation par listes chainees de successeurs (application gamma) */

  pcell reserve;    
  pcell libre;      
  pcell * gamma;    

  /* representation par liste d'arcs 
     (vecteurs tete (sommet initial), queue (sommet final)) */

  int *tete;        
  int *queue;       

  /* informations additionelles ajoutees aux arcs */

  TYP_VARC *v_arcs;

  /* informations additionelles ajoutees aux sommets */

  TYP_VSOM *v_sommets;

  double *x;        
  double *y;        
  char **nomsommet; 
} graphe;

/* ================================================ */
/* prototypes */
/* ================================================ */

extern void AfficheEnsemble(boolean *s, int n);
extern void AfficheListe(pcell p);
extern void AfficheSuccesseurs(graphe * g) ;
extern void AfficheArcs(graphe * g);
extern void AfficheValeursSommets(graphe * g);
extern void PSGraphe(graphe * g, char *filename, double r, double t, double marge);
void EPSGraphe(graphe * g, char *filename, double r, double t, double marge, int noms_sommets, int v_sommets, int col_sommets, int v_arcs);

/* ====================================================================== */
/* ====================================================================== */
/* FONCTIONS DE PLONGEMENT DE GRAPHES DANS LE PLAN */
/* ====================================================================== */
/* ====================================================================== */

extern void AutoNomsSommets(graphe * g, int mode);
extern void PlongementCirculaire(graphe * g, double r);
extern void PlongementRadial(graphe * g, int c);

/* ====================================================================== */
/* ====================================================================== */
/* FONCTIONS SUR LES LISTES CHAINEES DE SOMMETS */
/* ====================================================================== */
/* ====================================================================== */

extern pcell AlloueCell(pcell * plibre);
extern void LibereCell(pcell * plibre, pcell p);
extern void RetireTete(pcell * plibre, pcell * pliste);
extern void AjouteTete(pcell * plibre, pcell * pliste, int a, TYP_VARC v);
extern int EstDansListe(pcell p, int a);

/* ====================================================================== */
/* ====================================================================== */
/* FONCTIONS D'ALLOCATION / LIBERATION POUR UN GRAPHE */
/* ====================================================================== */
/* ====================================================================== */

extern graphe * InitGraphe(int nsom, int nmaxarc);
extern void TermineGraphe(graphe * g);
extern graphe * ReadGraphe(char * filename);

/* ====================================================================== */
/* ====================================================================== */
/* FONCTIONS DE MANIPULATION DES ARCS (APPLICATION GAMMA UNIQUEMENT) */
/* ====================================================================== */
/* ====================================================================== */

extern void AjouteArc(graphe * g, int i, int s);
extern void AjouteArcValue(graphe * g, int i, int s, TYP_VARC v);
extern void RetireArc(graphe * g, int i, int s);
extern int PopSuccesseur(graphe *g, int i);
extern int EstSuccesseur(graphe *g, int i, int s);

/* ====================================================================== */
/* ====================================================================== */
/* FONCTIONS DE GENERATION DE GRAPHES */
/* ====================================================================== */
/* ====================================================================== */

extern graphe * GrapheAleatoire(int nsom, int narc);

/* ====================================================================== */
/* ====================================================================== */
/* OPERATEURS DE BASE SUR LES GRAPHES */
/* ====================================================================== */
/* ====================================================================== */

extern graphe * Symetrique(graphe * g);