graphs.h

Go to the documentation of this file.

 
#ifndef GRAPHS_H
#define GRAPHS_H
 
 /*   ____                 _          */
 /*  / ___|_ __ __ _ _ __ | |__  ___  */
 /* | |  _| '__/ _` | '_ \| '_ \/ __| */
 /* | |_| | | | (_| | |_) | | | \__ \ */
 /*  \____|_|  \__,_| .__/|_| |_|___/ */
 /*                 |_|               */
 
#include "type_abr.h"
#include "type_basic.h"
#include "type_binheap.h"
#include "type_dequeue.h"
#include "type_partitions.h"
#include <stdarg.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    uint size;       
    dequeue** edges; 
} graph;

typedef struct {
    uint size_graph;  
    uint size_alpha;  
    dequeue*** edges; 
} lgraph;
 

typedef struct {
    uint size_graph; 
    uint size_alpha; 
    uint** edges;    
    uint* storage;   
} dgraph;
 
 
/**************/
/* Allocation */
/**************/

graph* create_graph_noedges(uint 
);

graph* create_graph_selfloops(uint 
);

void delete_graph(graph* //<! The graph that needs to be freed.
);

graph* copy_graph(graph* g 
);

lgraph* create_lgraph_noedges(uint, 
    uint 
);

void delete_lgraph(lgraph* //<! The graph that needs to be freed.
);

lgraph* copy_lgraph(lgraph* g 
);

dgraph* create_dgraph_noedges(uint, 
    uint 
);

void delete_dgraph(dgraph* //<! The graph that needs to be freed.
);
 

dgraph* copy_dgraph(dgraph* g 
);
 
/*******************/
/* Basic functions */
/*******************/

int graph_nb_edges(graph* //<! The graph.
);

int lgraph_nb_edges(lgraph* //<! The graph.
);

int dgraph_nb_edges(dgraph* //<! The graph.
);
 
/**************/
/*+ Products +*/
/**************/

dgraph* dgraph_direct_product(dgraph* g1, 
    dgraph* g2 
);
 
 
/***********/
/* Mirrors */
/***********/

graph* graph_mirror(graph* //<! The graph.
);

lgraph* lgraph_mirror(lgraph* //<! The graph.
);

lgraph* dgraph_mirror(dgraph* //<! The graph.
);
 
 
/************/
/* Searches */
/************/

typedef enum {
    DFS,
    BFS,
} graph_stype;

void graph_search_update(graph_stype, 
    graph*,     
    dequeue*,   
    bool*       
);

dequeue* graph_search(graph_stype, 
    graph*,     
    dequeue*,   
    bool*       
);

void lgraph_search_update(graph_stype, 
    lgraph*,    
    dequeue*,   
    bool*,      
    bool*       
);

dequeue* lgraph_search(graph_stype, 
    lgraph*,    
    dequeue*,   
    bool*,      
    bool*       
);

void dgraph_search_update(graph_stype, 
    dgraph*,    
    dequeue*,   
    bool*,      
    bool*       
);

dequeue* dgraph_search(graph_stype, 
    dgraph*,    
    dequeue*,   
    bool*,      
    bool*       
);
 
 

void twin_dgraph_search_update(graph_stype, 
    dgraph*,    
    dgraph*,    
    dequeue*,   
    bool*,      
    bool*       
);

dequeue* twin_dgraph_search(graph_stype, 
    dgraph*,    
    dgraph*,    
    dequeue*,   
    bool*,      
    bool*       
);
 

dgraph* dgraph_paths(dgraph* G, 
    uint start 
);
 
 
 
/********************************/
/*+ Disjoint merging of graphs +*/
/********************************/

graph* merge_graphs(uint*, 
    uint,   
    ...     
);

lgraph* merge_lgraphs(uint*, 
    uint, 
    ... 
);
 
/**************************************************/
/*+ Merging graphs with the same set of vertices +*/
/**************************************************/

graph* ldgraphs_to_graph(uint, 
    uint, 
    uint, 
    uint, 
    ...   
);

lgraph* ldgraphs_to_lgraph(uint, 
    uint, 
    uint, 
    ...   
);

lgraph* dgraph_to_lgraph(dgraph* 
);

graph* lgraph_to_graph(lgraph* 
);

graph* lgraph_to_graph_alpha(lgraph*, 
    bool* 
);
 

graph* dgraph_to_graph(dgraph* 
);

graph* dgraph_to_graph_alpha(dgraph*, 
    bool* 
);
 
 
/***************************************/
/*+ Computation of adjacents vertices +*/
/***************************************/

dequeue* lgraph_reachable(lgraph*,  
    dequeue*, 
    uint       
);
 
 
 
 
 
#endif