+void Vertex::add_leaving_edge(Edge *e) {
+ e->next_leaving_edge = leaving_edges;
+ e->pred_leaving_edge = 0;
+ if(leaving_edges) { leaving_edges->pred_leaving_edge = e; }
+ leaving_edges = e;
+}
+
+void Vertex::del_leaving_edge(Edge *e) {
+ if(e == leaving_edges) {
+ leaving_edges = e->next_leaving_edge;
+ }
+ if(e->pred_leaving_edge) {
+ e->pred_leaving_edge->next_leaving_edge = e->next_leaving_edge;
+ }
+ if(e->next_leaving_edge) {
+ e->next_leaving_edge->pred_leaving_edge = e->pred_leaving_edge;
+ }
+}
+
+//////////////////////////////////////////////////////////////////////
+
+static int compare_vertex(const void *v1, const void *v2) {
+ return (*((Vertex **) v1))->last_change - (*((Vertex **) v2))->last_change;
+}
+
+MTPGraph::MTPGraph(int nb_vertices, int nb_edges,
+ int *vertex_from, int *vertex_to,
+ int source, int sink) {
+ _nb_vertices = nb_vertices;
+ _nb_edges = nb_edges;
+
+ _edges = new Edge[_nb_edges];
+ _vertices = new Vertex[_nb_vertices];
+ _heap = new Vertex *[_nb_vertices];
+ _dp_order = new Vertex *[_nb_vertices];
+
+ _source = &_vertices[source];
+ _sink = &_vertices[sink];
+
+ for(int e = 0; e < nb_edges; e++) {
+ _vertices[vertex_from[e]].add_leaving_edge(_edges + e);
+ _edges[e].occupied = 0;
+ _edges[e].origin_vertex = _vertices + vertex_from[e];
+ _edges[e].terminal_vertex = _vertices + vertex_to[e];
+ }
+
+ for(int v = 0; v < _nb_vertices; v++) {
+ _heap[v] = &_vertices[v];
+ _vertices[v].heap_position = &_heap[v];
+ }
+
+ paths = 0;
+ nb_paths = 0;
+
+ if(is_dag()) {
+ // Here the last_change field of every vertex tells us how many
+ // iterations of DP we need to reach it. Hence we only have to
+ // process the vertex in that order.
+ for(int v = 0; v < _nb_vertices; v++) { _dp_order[v] = &_vertices[v]; }
+ qsort(_dp_order, _nb_vertices, sizeof(Vertex *), compare_vertex);
+ } else {
+ cerr << __FILE__ << ": This graph is not a DAG." << endl;
+ abort();
+ }