Check whether a graph is a generalized series-parallel graph as defined by [Korn94] which is done by successively removing nodes x that have single predecessors and no successors a->x and also by using the reduction rule of series-parallel graphs [Korn94]. It does not matter which nodes are the source and sink nodes for this reduction.

Check whether a graph is reducible in the sense of reducible control flow graphs as defined by Hecht et. al [HeUl72,HeUl72a,HeUl74]. The function applies Hecht's reductions T1 and T2 which remove self-loops and remove nodes x with a single predecessor by forwarding the predecessor to the successors of x.

Check whether an undirected graph is a series-parallel graph which is done by successively removing nodes x that have exactly two neighbors p and s, i.e., p--x--s with an edge p--s from the predecessor to the successor according to [Duff65]. It does not matter which nodes are the source and sink nodes for this reduction.

Compute condensed acyclic graph of the SCCs of a graph where each SCC is represented by its minimal element

Compute the dominator relation; the function returns a pair (dom,idom) where dom maps each vertex to the set of its dominators and where idom maps each vertex to its immediate dominator which is uniquely defined except for the root.

Given an acyclic relation mSuc as a map that maps an element x to the set of elements xSuc which are in relation to x, and optionally the set of root elements, i.e., elements which are in no set mSuc[x] for any x, the function computes a map levelMap that assigns the elements x of the relation a level of type int, such that the level is the minimum of the predecessors of x plus 1. Moreover, it partitions the elements of the relation into an array of levels levels. In terms of scheduling, the function computes therefore an ASAP schedule since elements are given the minimal levels.

given a successor map mSuc which maps elements x to its successors m[x], this function converts it to a set of pairs (x,y) that are in relation (note that the function applies to directed and undirected graphs if the adjacency map associating neighboring nodes is used)

MaximalBipartiteMatching computes a maximal matching of a bipartite graph using the MaximumFlow algorithm: The bipartite graph is endowed with additional single source and target nodes that are connected to all left hand side and right hand side states, respectively. Since all edges have capacity 1, a maximum flow tries to select from each left hand side node at most one outgoing edge to a right hand side node, and will try to select one such edge for each left hand side node, hence, it will select a maximal matching this way. The function returns the set of edges of the given bipartite graph that forms the computed maximal matching. See [CLRS09,chapter 26.3] and [KlTa06, chapter 7.5], for instance.

This algorithm implements the well-known Ford-Fulkerson algorithm to compute the maximum flow of a network. The network is thereby given as a set of edges (v,c,v') from vertex v to v' with capacity c, and the unique source and target vertices, respectively. The computed flow is a mapping from edges to an integer less than or equal to the capacity, and such that the sum of flows of all incoming edges is equal to that of all outgoing edges for each vertex. It is a maximum flow, i.e., the outgoing flows of the source, or equivalent the incoming flows at the target vertex are maximal. See [CLRS09,chapter 26] and [KlTa06, chapter 7], for further details. The type of nodes has been kept polymorphic.

This function computes a cover of a directed acyclic graph by a minimal set of vertex-disjoint paths. This is done by a reduction to computing a maximal matching of a bipartite graph where the left hand side nodes are the nodes having outgoing edges, and the right hand side nodes are the nodes having ingoing edges (and edges are just the edges of the graph between these). Note that one and the same node may occur in the generated bipartite matching problem on both sides. The result is a pair (gEdges,paths) where gEdges is the set of selected edges, and paths is the set of vertex-disjoint paths.

Given a partial order relation rel, and two elements x0 and x1, the function checks whether x1 can be reached from x0.

convert a binary relation given as set of pairs to a map that maps each element to the elements in relation to it (predecessors and successors); the function also returns the set of all nodes

convert a binary relation given as set of pairs to a map mSuc that maps elements to their successors

convert a binary relation given as set of pairs to maps mSuc and mPre that map elements to their successors and predecessors; the function also returns the set of all nodes

Computing strongly connected components by Tarjan's algorithm using a depth-first traversal of the graph. The function returns the set of SCCs of the given graph.

Given a partial order relation mSuc, and optionally its root elements, this function embeds the given partial order in a total order. It therefore returns a map totalRel like the given partial order mSuc which is a strict total order that includes mSuc.

Given a partial order relation mSuc, and optionally its root elements, this function removes order contraints which are implied by transitivity of the remaining constraints. It therefore returns a directed acyclic graph partialRel which is a map like the given relation whose transitive hull is the given partial order.

getSvgGraph converts dot graphs to a svg graphic which is returned as a string. Expected arguments are dotExe which is the path of the executable of dot like "/usr/bin/dot" and dotGraphWriter which is a function that will write a dot graph to a stream like the function Graph2Dot.