graph.h

Go to the documentation of this file.

 
#ifndef GRAPH_H
#define GRAPH_H
 
#include <stdbool.h>
#include "../set/set.h"
 
typedef struct Graph Graph;
 
typedef enum edgeType {
    TREE,
    CROSS,
    FORWARD,
    BACK,
} EdgeType;
 
static inline const char* graph_edge_type_name(EdgeType edge_type) {
    switch (edge_type) {
    case TREE: return "TREE";
    case CROSS: return "CROSS";
    case FORWARD: return "FORWARD";
    case BACK: return "BACK";
    }
    return "?";
}
 

Graph* graph_create();

Graph* graph_undirected_create();

Graph* graph_tarjan_create(bool directed);

size_t graph_size(Graph *g);

bool graph_is_directed(Graph *g);

bool graph_is_weighted(Graph *g);

void graph_add_node(Graph *g, int node);

void graph_add_edge(Graph *g, int u, int v);

void graph_add_edge_with_weight(Graph *g, int u, int v, int weight);
 

int graph_get_edge_weight(Graph *g, int u, int v);
 

void graph_remove_edge(Graph *g, int u, int v);

void graph_remove_node(Graph *g, int node);

bool graph_has_edge(Graph *g, int u, int v);

bool graph_has_node(Graph *g, int u);

Set* graph_get_neighbors(Graph *g, int node);

void graph_free(Graph *g);

void graph_print(Graph *g);

void graph_export_to_dot(Graph *g, const char* filename);

Iterator* graph_bfs(Graph *g, int start_node);

Iterator* graph_dfs(Graph *g, int start_node);

Iterator* graph_nodes_iterator(Graph *g);

List* graph_edges(Graph *g);

List* graph_edges_ordered(Graph *g);

int graph_edges_sum(Graph *g);

int graph_max_node_id(Graph *g);

bool graph_acyclical(Graph *g);

bool graph_is_dag(Graph *g);

Graph* graph_tarjan(Graph *g);

int* graph_strong_components(Graph *g);

List* graph_topological_sort(Graph *g);

Graph* graph_dijkstra(Graph* g, int source);

Graph* graph_kruskal(Graph* g);

Graph* graph_prim(Graph* g, int start);

int graph_minimum_distance(Graph* g, int source, int destination);

List* graph_shortest_path(Graph* g, int source, int destination);
 
#endif /* GRAPH_H */