graph.h

Go to the documentation of this file.

 
#pragma once
#include "common.h"
#include "link_list.h"
 
typedef struct gnode {
    t_gen id;           
    int idx;            
    t_linklist *neigh;      
} t_gnode;
 
typedef struct gedge {
    t_gnode *node;          
    int weight;         
} t_gedge;
 
// fn ptr for adding weighted edge
typedef t_gen (*f_wedge)(t_gen, t_gen, t_gen, int); 
 
typedef struct graph {
    // graph info params
    char *name;         
    int count;          
    int max_size;           
    int total_edges;        
 
    // graph nodes
    t_gnode *nodes;         
 
    // graph routines
    f_gen2 add_vertex;      
    f_gen2 del_vertex;      
    f_gen3 add_edge;        
    f_gen3 del_edge;        
    f_gen3 add_edge_sym;        
    f_gen3 del_edge_sym;        
    f_wedge add_wedge;      
    f_wedge add_wedge_sym;      
    f_gen3 has_edge;        
    f_gen2 bfs;         
    f_gen2 dfs;         
    f_gen conn_comp;        
    f_gen topo_order_dag;       
    f_find find;            
    f_len len;          
    f_print print;          
    f_print wprint;         
    f_destroy destroy;      
    
    // routies for operating on data
    f_cmpr cmpr;
    f_swap swap;
    f_free free;
    f_print print_data;
} t_graph;
 
typedef struct bfs_info{
    t_gen parent;           
    int level;          
    int comp;           
} t_bfsinfo;
 
typedef struct dfs_info{
    t_gen parent;           
    int pre;            
    int post;           
    int comp;           
    int visited_neighbors;      
} t_dfsinfo;
 
typedef struct dag_info{
    t_gen node;         
    int longest_path;       
    int indegree;           
} t_daginfo;
 
typedef struct dist_info {
    t_gedge edge;           
    t_gnode *parent;        
} t_distinfo;
 
t_gen create_graph(char *name, int size, t_dparams *prm);
t_gen dijkstra(t_gen d, t_gen data);
t_gen bellman_ford(t_gen d, t_gen data);
t_gen prims_mst(t_gen d);
t_gen kruskals_mst(t_gen d);