## Graphs Module

This module provides some generel algorithms on (directed) graphs, where the graphs are usually represented as maps where a node is mapped to the set of its successor nodes. In case of directed acyclic graphs, one may optionally specify the set of root nodes to avoid that computation.

### Functions and values

 Function or value Description  CheckGeneralizedSeriesParallel rel  Full Usage: CheckGeneralizedSeriesParallel rel Parameters: rel : Set<'a * 'a> Returns: ('a * Map<'a, Set<'a>>) list * Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>> 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. rel : Set<'a * 'a> Returns: ('a * Map<'a, Set<'a>>) list * Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>>  CheckReducible rel  Full Usage: CheckReducible rel Parameters: rel : Set<'a * 'a> Returns: ('a * Map<'a, Set<'a>>) list * Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>> 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. rel : Set<'a * 'a> Returns: ('a * Map<'a, Set<'a>>) list * Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>>  CheckSeriesParallel rel  Full Usage: CheckSeriesParallel rel Parameters: rel : Set<'a * 'a> Returns: ('a * Map<'a, Set<'a>>) list * Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>> 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. rel : Set<'a * 'a> Returns: ('a * Map<'a, Set<'a>>) list * Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>>  CondensedGraphSCC graph sccS  Full Usage: CondensedGraphSCC graph sccS Parameters: graph : Map<'a, Set<'a>> sccS : Set> Returns: Map<'a, Set<'a>> * Map<'a, 'a> * Map<'a, Set<'a>> Compute condensed acyclic graph of the SCCs of a graph where each SCC is represented by its minimal element graph : Map<'a, Set<'a>> sccS : Set> Returns: Map<'a, Set<'a>> * Map<'a, 'a> * Map<'a, Set<'a>>  DirectedGraph2Dot ostr printNode mSuc  Full Usage: DirectedGraph2Dot ostr printNode mSuc Parameters: ostr : TextWriter printNode : 'a -> string mSuc : Map<'a, Set<'a>> ostr : TextWriter printNode : 'a -> string mSuc : Map<'a, Set<'a>>  DominatorMap rootNode suc  Full Usage: DominatorMap rootNode suc Parameters: rootNode : 'a suc : Map<'a, Set<'a>> Returns: Map<'a, Set<'a>> * Map<'a, Set<'a>> 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. rootNode : 'a suc : Map<'a, Set<'a>> Returns: Map<'a, Set<'a>> * Map<'a, Set<'a>>  LevelizeAcyclicRel rootsOpt mSuc  Full Usage: LevelizeAcyclicRel rootsOpt mSuc Parameters: rootsOpt : Set<'a> option mSuc : Map<'a, Set<'a>> Returns: Map<'a, int> * Set<'a>[] 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. rootsOpt : Set<'a> option mSuc : Map<'a, Set<'a>> Returns: Map<'a, int> * Set<'a>[]  Map2Rel sort mSuc  Full Usage: Map2Rel sort mSuc Parameters: sort : bool mSuc : Map<'a, Set<'a>> Returns: Set<'a * 'a> 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) sort : bool mSuc : Map<'a, Set<'a>> Returns: Set<'a * 'a>  MaximalBipartiteMatching bgraph  Full Usage: MaximalBipartiteMatching bgraph Parameters: bgraph : Set<'node * 'node> Returns: Set<'node * 'node> 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. bgraph : Set<'node * 'node> Returns: Set<'node * 'node>  MaximumFlow graph source target  Full Usage: MaximumFlow graph source target Parameters: graph : Set<'node * int * 'node> source : 'node target : 'node Returns: int * Map<('node * 'node), int> 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. graph : Set<'node * int * 'node> source : 'node target : 'node Returns: int * Map<('node * 'node), int>  MinimumNumberOfVertexDisjointPath graph  Full Usage: MinimumNumberOfVertexDisjointPath graph Parameters: graph : Set<'node * 'node> Returns: Set<'node * 'node> * Set<'node list> 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. graph : Set<'node * 'node> Returns: Set<'node * 'node> * Set<'node list>  ReachableRel x0 x1 rel  Full Usage: ReachableRel x0 x1 rel Parameters: x0 : 'a x1 : 'a rel : Map<'a, Set<'a>> Returns: bool Given a partial order relation rel, and two elements x0 and x1, the function checks whether x1 can be reached from x0. x0 : 'a x1 : 'a rel : Map<'a, Set<'a>> Returns: bool  Rel2AdjMap rel  Full Usage: Rel2AdjMap rel Parameters: rel : Set<'a * 'a> Returns: Set<'a> * Map<'a, Set<'a>> 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 rel : Set<'a * 'a> Returns: Set<'a> * Map<'a, Set<'a>>  Rel2Map rel  Full Usage: Rel2Map rel Parameters: rel : Set<'a * 'a> Returns: Map<'a, Set<'a>> convert a binary relation given as set of pairs to a map mSuc that maps elements to their successors rel : Set<'a * 'a> Returns: Map<'a, Set<'a>>  Rel2Maps rel  Full Usage: Rel2Maps rel Parameters: rel : Set<'a * 'a> Returns: Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>> 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 rel : Set<'a * 'a> Returns: Set<'a> * Map<'a, Set<'a>> * Map<'a, Set<'a>>  TarjanSCC graph  Full Usage: TarjanSCC graph Parameters: graph : Map<'a, Set<'a>> Returns: Set> 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. graph : Map<'a, Set<'a>> Returns: Set>  TotalOrderRel rootsOpt mSuc  Full Usage: TotalOrderRel rootsOpt mSuc Parameters: rootsOpt : Set<'a> option mSuc : Map<'a, Set<'a>> Returns: 'a[] 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. rootsOpt : Set<'a> option mSuc : Map<'a, Set<'a>> Returns: 'a[]  TransHullRel rel  Full Usage: TransHullRel rel Parameters: rel : Set<'a * 'a> Returns: Set<'a * 'a> rel : Set<'a * 'a> Returns: Set<'a * 'a>  TransHullRelMap suc  Full Usage: TransHullRelMap suc Parameters: suc : Map<'a, Set<'a>> Returns: Map<'a, Set<'a>> suc : Map<'a, Set<'a>> Returns: Map<'a, Set<'a>>  TransReduceRel rootsOpt mSuc  Full Usage: TransReduceRel rootsOpt mSuc Parameters: rootsOpt : Set<'a> option mSuc : Map<'a, Set<'a>> Returns: Map<'a, Set<'a>> 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. rootsOpt : Set<'a> option mSuc : Map<'a, Set<'a>> Returns: Map<'a, Set<'a>>  UndirectedGraph2Dot ostr printNode rel  Full Usage: UndirectedGraph2Dot ostr printNode rel Parameters: ostr : TextWriter printNode : 'a -> string rel : Set<'a * 'a> ostr : TextWriter printNode : 'a -> string rel : Set<'a * 'a>  getSvgGraph dotExe dotGraphWriter  Full Usage: getSvgGraph dotExe dotGraphWriter Parameters: dotExe : string dotGraphWriter : StreamWriter -> unit Returns: string 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. dotExe : string dotGraphWriter : StreamWriter -> unit Returns: string