SimGrid  3.13
Versatile Simulation of Distributed Systems
graph.c File Reference
#include "xbt/sysdep.h"
#include "xbt/log.h"
#include "xbt/graph.h"
#include "graph_private.h"
#include "xbt/dict.h"
#include "xbt/heap.h"
#include "xbt/str.h"
#include "xbt/file.h"
#include <errno.h>
#include <stdlib.h>

Macros

#define D(u, v)   d[(u)*n+(v)]
 
#define P(u, v)   p[(u)*n+(v)]
 

Functions

 XBT_LOG_NEW_DEFAULT_SUBCATEGORY (xbt_graph, xbt,"Graph")
 
xbt_graph_t xbt_graph_new_graph (unsigned short int directed, void *data)
 Constructor. More...
 
xbt_node_t xbt_graph_new_node (xbt_graph_t g, void *data)
 add a node to the given graph More...
 
xbt_edge_t xbt_graph_new_edge (xbt_graph_t g, xbt_node_t src, xbt_node_t dst, void *data)
 add an edge to the given graph More...
 
xbt_edge_t xbt_graph_get_edge (xbt_graph_t g, xbt_node_t src, xbt_node_t dst)
 Get the edge connecting src and dst. More...
 
voidxbt_graph_node_get_data (xbt_node_t node)
 Get the user data associated to a node. More...
 
void xbt_graph_node_set_data (xbt_node_t node, void *data)
 Set the user data associated to a node. More...
 
voidxbt_graph_edge_get_data (xbt_edge_t edge)
 Get the user data associated to a edge. More...
 
void xbt_graph_edge_set_data (xbt_edge_t edge, void *data)
 Set the user data associated to a edge. More...
 
void xbt_graph_free_graph (xbt_graph_t g, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function, void_f_pvoid_t graph_free_function)
 Destructor. More...
 
xbt_dynar_t xbt_graph_get_nodes (xbt_graph_t g)
 Retrieve the graph's nodes as a dynar. More...
 
xbt_dynar_t xbt_graph_get_edges (xbt_graph_t g)
 Retrieve the graph's edges as a dynar. More...
 
xbt_node_t xbt_graph_edge_get_source (xbt_edge_t e)
 Retrieve the node at the source of the given edge. More...
 
xbt_node_t xbt_graph_edge_get_target (xbt_edge_t e)
 Retrieve the node being the target of the given edge. More...
 
xbt_dynar_t xbt_graph_node_get_outedges (xbt_node_t n)
 Retrieve the outgoing edges of the given node. More...
 
void xbt_graph_edge_set_length (xbt_edge_t e, double length)
 Set the weight of the given edge. More...
 
double xbt_graph_edge_get_length (xbt_edge_t edge)
 Get the length of a edge. More...
 
void xbt_floyd_algorithm (xbt_graph_t g, double *adj, double *d, xbt_node_t *p)
 Floyd-Warshall algorithm for shortest path finding. More...
 
void xbt_graph_export_graphviz (xbt_graph_t g, const char *filename, const char *(node_name)(xbt_node_t), const char *(edge_name)(xbt_edge_t))
 Export the given graph in the GraphViz formatting for visualization. More...
 

Macro Definition Documentation

#define D (   u,
 
)    d[(u)*n+(v)]
#define P (   u,
 
)    p[(u)*n+(v)]

Function Documentation

XBT_LOG_NEW_DEFAULT_SUBCATEGORY ( xbt_graph  ,
xbt  ,
"Graph"   
)
void xbt_floyd_algorithm ( xbt_graph_t  g,
double *  adj,
double *  d,
xbt_node_t p 
)

Floyd-Warshall algorithm for shortest path finding.

From wikipedia:

The Floyd–Warshall algorithm takes as input an adjacency matrix representation of a weighted, directed graph (V, E). The weight of a path between two vertices is the sum of the weights of the edges along that path. The edges E of the graph may have negative weights, but the graph must not have any negative weight cycles. The algorithm computes, for each pair of vertices, the minimum weight among all paths between the two vertices. The running time complexity is Θ(|V|3).