+/** @brief Extract a spanning tree of the given graph */
+xbt_edge_t* xbt_graph_spanning_tree_prim(xbt_graph_t g)
+{
+ int tree_size=0;
+ int tree_size_max=xbt_dynar_length(g->nodes)-1;
+ xbt_edge_t *tree = xbt_new0(xbt_edge_t,tree_size_max);
+ xbt_edge_t e,edge;
+ xbt_node_t node = NULL;
+ xbt_dynar_t edge_list = NULL;
+ xbt_heap_t heap = xbt_heap_new(10,NULL);
+ int cursor;
+
+ xbt_assert0(!(g->directed),
+ "Spanning trees do not make sense on directed graphs");
+
+ xbt_dynar_foreach(g->nodes, cursor, node) {
+ node->xbtdata = NULL;
+ }
+
+ node = xbt_dynar_getfirst_as(g->nodes,xbt_node_t);
+ node->xbtdata = (void*) 1;
+ edge_list = node->out;
+ xbt_dynar_foreach(edge_list, cursor, e)
+ xbt_heap_push(heap,e, -(e->length));
+
+ while((edge=xbt_heap_pop(heap))) {
+ if((edge->src->xbtdata) && (edge->dst->xbtdata)) continue;
+ tree[tree_size++]=edge;
+ if(!(edge->src->xbtdata)) {
+ edge->src->xbtdata = (void*) 1;
+ edge_list = edge->src->out;
+ xbt_dynar_foreach(edge_list, cursor, e) {
+ xbt_heap_push(heap,e, -(e->length));
+ }
+ } else {
+ edge->dst->xbtdata = (void*) 1;
+ edge_list = edge->dst->out;
+ xbt_dynar_foreach(edge_list, cursor, e) {
+ xbt_heap_push(heap,e, -(e->length));
+ }
+ }
+ if(tree_size==tree_size_max) break;
+ }
+
+ xbt_heap_free(heap);
+
+ return tree;
+}
+
+/** @brief Topological sort on the given graph
+ *
+ * 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.
+ */
+xbt_node_t* xbt_graph_topo_sort(xbt_graph_t g)
+{
+
+ xbt_node_t* sorted;
+ int cursor,idx;
+ xbt_node_t node;
+ unsigned long n;
+
+ n= xbt_dynar_length(g->nodes);
+ idx=n-1;
+
+ sorted=xbt_malloc(n*sizeof(xbt_node_t));
+ xbt_dynar_foreach(g->nodes,cursor , node)
+ {
+ node->xbtdata=xbt_new0(int,1);
+ }
+
+ xbt_dynar_foreach(g->nodes,cursor , node)
+ {
+ xbt_graph_depth_visit(g,node,sorted,&idx);
+ }
+ xbt_dynar_foreach(g->nodes, cursor, node)
+ {
+ node->xbtdata = NULL;
+ }
+ return sorted;
+}