SimGrid  3.10
Versatile Simulation of Distributed Systems
 All Data Structures Functions Variables Typedefs Enumerations Enumerator Groups Pages
General purpose graph library

A graph data type with several interesting algorithms. More...

Functions

xbt_graph_t xbt_graph_new_graph (unsigned short int directed, void *data)
 Constructor.
xbt_node_t xbt_graph_new_node (xbt_graph_t g, void *data)
 add a node to the given graph
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
void * xbt_graph_node_get_data (xbt_node_t node)
 Get the user data associated to a node.
void xbt_graph_node_set_data (xbt_node_t node, void *data)
 Set the user data associated to a node.
void * xbt_graph_edge_get_data (xbt_edge_t edge)
 Get the user data associated to a edge.
void xbt_graph_edge_set_data (xbt_edge_t edge, void *data)
 Set the user data associated to a edge.
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.
void xbt_graph_edge_set_length (xbt_edge_t e, double length)
 Set the weight of the given edge.
double xbt_graph_edge_get_length (xbt_edge_t e)
 Get the length of a edge.
double * xbt_graph_get_length_matrix (xbt_graph_t g)
 construct the adjacency matrix corresponding to the given graph
void xbt_graph_free_node (xbt_graph_t g, xbt_node_t n, void_f_pvoid_t node_free_function, void_f_pvoid_t edge_free_function)
 remove the given node from the given graph
void xbt_graph_free_edge (xbt_graph_t g, xbt_edge_t e, void_f_pvoid_t free_function)
 remove the given edge from the given graph
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.
xbt_dynar_t xbt_graph_get_nodes (xbt_graph_t g)
 Retrieve the graph's nodes as a dynar.
xbt_dynar_t xbt_graph_get_edges (xbt_graph_t g)
 Retrieve the graph's edges as a dynar.
xbt_dynar_t xbt_graph_node_get_outedges (xbt_node_t n)
 Retrieve the outgoing edges of the given node.
xbt_node_t xbt_graph_edge_get_source (xbt_edge_t e)
 Retrieve the node at the source of the given edge.
xbt_node_t xbt_graph_edge_get_target (xbt_edge_t e)
 Retrieve the node being the target of the given edge.
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.
void xbt_graph_export_graphxml (xbt_graph_t g, const char *filename, const char *(node_name)(xbt_node_t), const char *(edge_name)(xbt_edge_t), const char *(node_data_print)(void *), const char *(edge_data_print)(void *))
 Export the given graph in the GraphXML format.
xbt_graph_t xbt_graph_load (const char *filename)
 Load a graph from a file (in the SimGrid Graph format)
void xbt_graph_save (xbt_graph_t span, const char *filename, const char *(nname)(xbt_node_t), const char *(ename)(xbt_edge_t))
 Save a graph from a file (in the SimGrid Graph format)
xbt_node_t * xbt_graph_shortest_paths (xbt_graph_t g)
 computes all-pairs shortest paths
xbt_node_t * xbt_graph_topo_sort (xbt_graph_t g)
 transforms the network structure of a directed acyclic graph given into a linear structure
xbt_edge_t * xbt_graph_spanning_tree_prim (xbt_graph_t g)
 Extract a spanning tree of the given graph.

Detailed Description

A graph data type with several interesting algorithms.

Function Documentation

xbt_graph_t xbt_graph_new_graph ( unsigned short int  directed,
void *  data 
)

Constructor.

Returns
a new graph
double* xbt_graph_get_length_matrix ( xbt_graph_t  g)

construct the adjacency matrix corresponding to the given graph

The weights are the distances between nodes

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.

Parameters
g,:poor victim
node_free_function,:function to use to free data associated to each node
edge_free_function,:function to use to free data associated to each edge
graph_free_function,:function to use to free data associated to g

Free the graph structure.

xbt_node_t* xbt_graph_topo_sort ( xbt_graph_t  g)

transforms the network structure of a directed acyclic graph given into a linear structure

Returns
: an array containing the nodes of the graph sorted in order reverse to the path of exploration if a cycle is detected an exception is raised

transforms the network structure of a directed acyclic graph given into a linear structure

From wikipedia:

In graph theory, a topological sort of a directed acyclic graph (DAG) is a linear ordering of its nodes which is compatible with the partial order R induced on the nodes where x comes before y (xRy) if there's a directed path from x to y in the DAG. An equivalent definition is that each node comes before all nodes to which it has edges. Every DAG has at least one topological sort, and may have many.