Module SHGraph


module SHGraph: sig .. end
Oriented hypergraphs


Introduction

This module provides an abstract datatypes and functions for manipulating hypergraphs, that is, graphs where edges relates potentially more than 2 vertices. The considered hypergraphs are oriented: one distinguishes for a vertex incoming and outgoing hyperedges, and for an hyperedge incoming (or origin) and outgoing (or destination) vertices.

Origin and destination vertices of an hyperedge are ordered (by using arrays), in contrast with incoming and outgoing hyperedges of a vertex.

A possible use of such hypergraphs is the representation of a (fixpoint) equation system, where the unknown are the vertices and the functions the hyperedges, taking a vector of unknowns as arguments and delivering a vector of results.

A last note about the notion of connectivity, which is relevant for operations like depth-first-search, reachability and connex components notions. A destination vertex of an hyperedge is considered as reachable from an origin vertex through this hyperedge only if all origin vertices are reachable.

Generic (polymorphic) interface


type ('a, 'b, 'c, 'd, 'e) t 
The type of hypergraphs where
val create : int -> 'a -> ('b, 'c, 'd, 'e, 'a) t
create n data creates an hypergraph, using n for the initial size of internal hashtables, and data for the user information
val clear : ('a, 'b, 'c, 'd, 'e) t -> unit
Remove all vertices and hyperedges of the graph.
val is_empty : ('a, 'b, 'c, 'd, 'e) t -> bool
Is the graph empty ?

Statistics


val size_vertex : ('a, 'b, 'c, 'd, 'e) t -> int
Number of vertices in the hypergraph
val size_hedge : ('a, 'b, 'c, 'd, 'e) t -> int
Number of hyperedges in the hypergraph
val size_edgevh : ('a, 'b, 'c, 'd, 'e) t -> int
Number of edges (vertex,hyperedge) in the hypergraph
val size_edgehv : ('a, 'b, 'c, 'd, 'e) t -> int
Number of edges (hyperedge,vertex) in the hypergraph
val size : ('a, 'b, 'c, 'd, 'e) t -> int * int * int * int
size graph returns (nbvertex,nbhedge,nbedgevh,nbedgehv)

Information associated to vertives and edges


val attrvertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'c
attrvertex graph vertex returns the information associated to the vertex vertex
val attrhedge : ('a, 'b, 'c, 'd, 'e) t -> 'b -> 'd
attrhedge graph hedge returns the information associated to the hyperedge hedge
val info : ('a, 'b, 'c, 'd, 'e) t -> 'e
info g returns the user-information attached to the graph g

Membership tests


val is_vertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> bool
val is_hedge : ('a, 'b, 'c, 'd, 'e) t -> 'b -> bool

Successors and predecessors


val succhedge : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'b Sette.t
Successor hyperedges of a vertex
val predhedge : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'b Sette.t
Predecessor hyperedges of a vertex
val succvertex : ('a, 'b, 'c, 'd, 'e) t -> 'b -> 'a array
Successor vertices of an hyperedge
val predvertex : ('a, 'b, 'c, 'd, 'e) t -> 'b -> 'a array
Predecessor vertices of an hyperedge
val succ_vertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'a Sette.t
Successor vertices of a vertex by any hyperedge
val pred_vertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'a Sette.t
Predecessor vertices of a vertex by any hyperedge

Adding and removing elements


val add_vertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'c -> unit
Add a vertex
val add_hedge : ('a, 'b, 'c, 'd, 'e) t ->
'b -> 'd -> pred:'a array -> succ:'a array -> unit
Add an hyperedge. The predecssor and successor vertices should already exist in the graph. Otherwise, a Failure exception is raised.
val remove_vertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> unit
Remove the vertex from the graph, as well as all related hyperedges.
val remove_hedge : ('a, 'b, 'c, 'd, 'e) t -> 'b -> unit
Remove the hyperedge from the graph.

Iterators


val iter_vertex : ('a, 'b, 'c, 'd, 'e) t ->
('a -> 'c -> pred:'b Sette.t -> succ:'b Sette.t -> unit) -> unit
Iterates the function f vertex attrvertex succhedges predhedges to all vertices of the graph. succhedges (resp. predhedges) is the set of successor (resp. predecessor) hyperedges of the vertex
val iter_hedge : ('a, 'b, 'c, 'd, 'e) t ->
('b -> 'd -> pred:'a array -> succ:'a array -> unit) -> unit
Iterates the function f hedge attrhedge succvertices predvertices to all hyperedges of the graph. succvertices (resp. predvertices) is the set of successor (resp. predecessor) vertices of the hyperedge

Below are the fold versions of the previous functions.
val fold_vertex : ('a, 'b, 'c, 'd, 'e) t ->
('a -> 'c -> pred:'b Sette.t -> succ:'b Sette.t -> 'f -> 'f) -> 'f -> 'f
val fold_hedge : ('a, 'b, 'c, 'd, 'e) t ->
('b -> 'd -> pred:'a array -> succ:'a array -> 'f -> 'f) -> 'f -> 'f

Below are the map versions of the previous functions.
val map : ('a, 'b, 'c, 'd, 'e) t ->
('a -> 'c -> pred:'b Sette.t -> succ:'b Sette.t -> 'f) ->
('b -> 'd -> pred:'a array -> succ:'a array -> 'g) ->
('e -> 'h) -> ('a, 'b, 'f, 'g, 'h) t

Copy and Transpose


val copy : ('a -> 'b -> 'c) ->
('d -> 'e -> 'f) ->
('g -> 'h) ->
('a, 'd, 'b, 'e, 'g) t -> ('a, 'd, 'c, 'f, 'h) t
Copy an hypergraph, using the given functions to duplicate the attributes associated to the elements of the graph. The vertex and hedge identifiers are copied using the identity function.
val transpose : ('a -> 'b -> 'c) ->
('d -> 'e -> 'f) ->
('g -> 'h) ->
('a, 'd, 'b, 'e, 'g) t -> ('a, 'd, 'c, 'f, 'h) t
Similar to copy, but hyperedges are reversed: successor vertices and predecssor vertices are exchanged.

Algorithms


val min : ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t
Return the set of vertices without predecessor hyperedges
val max : ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t
Return the set of vertices without successor hyperedges

Topological sort


val topological_sort : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'a list
Topological sort of the vertices of the hypergraph starting from a root vertex. The graph supposed to be acyclic. Any hyperedge linking two vertices (which are resp. predecessor and successor) induces a dependency. The result contains only vertices reachable from the given root vertex. If the dependencies are cyclic, the result is meaningless.
val topological_sort_multi : 'a -> 'b -> ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t -> 'a list
Topological sort from a set of root vertices. The two first arguments are supposed to be yet unused vertex and hyperedge identifier.
val topological_sort_filter_multi : 'a ->
'b -> ('a, 'b, 'c, 'd, 'e) t -> ('b -> bool) -> 'a Sette.t -> 'a list
Variant of the previous function, where the Boolean function f hedge succ tells whether the given dependency should be taken into account or not in the sort.

Reachability and coreachability



The variants of the basic functions are similar to the variants described above.
val reachable : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'a Sette.t * 'b Sette.t
Returns the set of vertices and hyperedges that are *NOT* reachable from the given root vertex. Any dependency in the sense described above is taken into account to define the reachability relation. For instance, if one of the predecessor vertex of an hyperedge is reachable, the hyperedge is considered as reachable.
val reachable_multi : 'a ->
'b -> ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t -> 'a Sette.t * 'b Sette.t
val reachable_filter_multi : 'a ->
'b ->
('a, 'b, 'c, 'd, 'e) t ->
('b -> bool) -> 'a Sette.t -> 'a Sette.t * 'b Sette.t

Strongly Connected Components and SubComponents


val cfc : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'a list list
Decomposition of the graph into Strongly Connected Components,

cfc graph vertex returns a decomposition of the graph. The exploration is done from the initial vertex vertex, and only reachable vertices are included in the result. The result has the structure [comp1 comp2 comp3 ...] where each component is defined by a list of vertices. The ordering of component correspond to a linearization of the partial order between the components.

val cfc_multi : 'a -> 'b -> ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t -> 'a list list
idem, but from several initial vertices.

cfc dummy_vertex dummy_hedge graph setvertices returns a decomposition of the graph, explored from the set of initial vertices setvertices. dummy_vertex and dummy_hedge are resp. unused vertex and hyperedge identifiers.

val cfc_filter_multi : 'a ->
'b ->
('a, 'b, 'c, 'd, 'e) t -> ('b -> bool) -> 'a Sette.t -> 'a list list
idem, but with a filtering of dependencies
val cfc_priority_multi : 'a ->
'b ->
('a, 'b, 'c, 'd, 'e) t -> ('b -> int) -> 'a Sette.t -> 'a list list
idem, but with a priority of dependencies.

The priority function p:'b -> int filters out hyperedges b such that p b<0, and explores first hyperedges b with the highest priority.

val scfc : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'a Ilist.t
Decomposition of the graph into Strongly Connected Sub-Components,

scfc graph vertex returns a decomposition of the graph. The exploration is done from the initial vertex vertex, and only reachable vertices are included in the result. The result has the structure [comp1 comp2 comp3 ...] where each component is in turn decomposed into components.

val scfc_multi : 'a -> 'b -> ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t -> 'a Ilist.t
idem, but from several initial vertices.
val scfc_filter_multi : 'a ->
'b ->
('a, 'b, 'c, 'd, 'e) t -> ('b -> bool) -> 'a Sette.t -> 'a Ilist.t
idem, but with a filtering of dependencies
val scfc_priority_multi : 'a ->
'b ->
('a, 'b, 'c, 'd, 'e) t -> ('b -> int) -> 'a Sette.t -> 'a Ilist.t
idem, but with a priority of dependencies.

Printing


val print : (Format.formatter -> 'a -> unit) ->
(Format.formatter -> 'b -> unit) ->
(Format.formatter -> 'c -> unit) ->
(Format.formatter -> 'd -> unit) ->
(Format.formatter -> 'e -> unit) ->
Format.formatter -> ('a, 'b, 'c, 'd, 'e) t -> unit
Print a graph in textual format on the given formatter, using the given functions to resp. print: vertices ('a), hedges ('b), vertex attributes ('c), hedge attributes ('d), and the user information ('e).
val print_dot : ?titlestyle:string ->
?vertexstyle:string ->
?hedgestyle:string ->
?title:string ->
(Format.formatter -> 'a -> unit) ->
(Format.formatter -> 'b -> unit) ->
(Format.formatter -> 'a -> 'c -> unit) ->
(Format.formatter -> 'b -> 'd -> unit) ->
Format.formatter -> ('a, 'b, 'c, 'd, 'e) t -> unit
Output the graph in DOT format on the given formatter, using the given functions to resp print:

The optional arguments allows to customize the style. The default setting corresponds to:

print_dot ~titlestyle="shape=ellipse,style=bold,style=filled,fontsize=20" ~vertexstyle="shape=box,fontsize=12" ~hedgestyle="shape=ellipse,fontsize=12" ~title="" ....

val escaped : ?linebreak:char -> string -> string
Escape a string, replacing line breaks by linebreak (default '\n'). When used for DOT output, '\l' and '\r' produces respectively left or righjt justified lines, instead of center justified lines.

Parameter module for the functor version


module type T = sig .. end

Signature of the functor version



All functions have the same signature as the polymorphic version, except the functions XXX_multi which does not need any more a dummy value of type vertex (resp. hedge).
module type S = sig .. end

Functor


module Make: 
functor (T : T) -> S with type vertex=T.vertex and type hedge=T.hedge and module SetV=T.SetV and module SetH=T.SetH