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.

type 'a priority =

| Filter of ('a -> bool)

| Priority of ('a -> int) (* Filtering or priority function (used by SHGraph.topological_sort, SHGraph.cfc, SHGraph.scfc, SHGraph.topological_sort_multi, SHGraph.cfc_multi, SHGraph.scfc_multi).
Filter p specifies p as a filtering function for hyperedges: only those satisfying p are taken into account.
Priority p specifies p as a priority function. Hyperedges h with p h < 0 are not taken into account. Otherwise, hyperedges with highest priority are explored first.
*)

type ('a, 'b) compare = {

   hashv : 'a Hashhe.compare;

   hashh : 'b Hashhe.compare;

   comparev : 'a -> 'a -> int;

   compareh : 'b -> 'b -> int;
}
type ('a, 'b) vertex_n = {

   attrvertex : 'b;

   mutable predhedge : 'a Sette.set;

   mutable succhedge : 'a Sette.set;
}
type ('a, 'b) hedge_n = {

   attrhedge : 'b;

   predvertex : 'a array;

   succvertex : 'a array;
}
type ('a, 'b, 'c, 'd, 'e) graph = {

   vertex : ('a, ('b, 'c) vertex_n) Hashhe.hashtbl;

   hedge : ('b, ('a, 'd) hedge_n) Hashhe.hashtbl;

   info : 'e;
}

Generic (polymorphic) interface

val stdcompare : ('a, 'b) compare

type ('a, 'b, 'c, 'd, 'e) t = ('a, 'b, 'c, 'd, 'e) graph

The type of hypergraphs where

'a : type of vertices
'b : type of hedges
'c : information associated to vertices
'd : information associated to hedges
'e : user-information associated to an hypergraph

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 predecessor and successor vertices should already exist in the graph. Otherwise, a Failure exception is raised.

val replace_attrvertex : ('a, 'b, 'c, 'd, 'e) t -> 'a -> 'c -> unit

Change the attribute of an existing vertex

val replace_attrhedge : ('a, 'b, 'c, 'd, 'e) t -> 'b -> 'd -> unit

Change the attribute of an existing hyperedge

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 -> 'f) ->
       ('b -> 'd -> '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 predecessor 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 : ?priority:'a priority ->
       ('b, 'a, 'c, 'd, 'e) t -> 'b -> 'b 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 ->
       ?priority:'b priority ->
       ('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.

Reachability and coreachability

The variants of the basic functions are similar to the variants described above.

val reachable : ?filter:('a -> bool) ->
       ('b, 'a, 'c, 'd, 'e) t -> 'b -> 'b Sette.t * 'a 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 ->
       ?filter:('b -> bool) ->
       ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t -> 'a Sette.t * 'b Sette.t

Strongly Connected Components and SubComponents

val cfc : ?priority:'a priority ->
       ('b, 'a, 'c, 'd, 'e) t -> 'b -> 'b 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 ->
       ?priority:'b priority ->
       ('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 scfc : ?priority:'a priority ->
       ('b, 'a, 'c, 'd, 'e) t -> 'b -> 'b 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 ->
       ?priority:'b priority ->
       ('a, 'b, 'c, 'd, 'e) t -> 'a Sette.t -> 'a Ilist.t

idem, but from several initial vertices.

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 : ?style:string ->
       ?titlestyle:string ->
       ?vertexstyle:string ->
       ?hedgestyle:string ->
       ?fvertexstyle:('a -> string) ->
       ?fhedgestyle:('b -> 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:

vertex identifiers (in the DOT file)
hedge identifiers (in the DOT file).
BE CAUTIOUS. as the DOT files vertices and hedges are actually nodes, the user should take care to avoid name conflicts between vertex and hedge names.
vertex attributes.
BE CAUTIOUS: the output of the function will be enclosed bewteen quotes. If ever the output contains line break, or other special characters, it should be escaped. A possible scheme to do this is to first output to Format.str_formatter with a standard printing function, then to escape the resulting string and to output the result. This gives something like:
print_attrvertex Format.str_formatter vertex attr;
Format.pp_print_string fmt (String.escaped (Format.flush_str_formatter ()));.
Concerning the escape function, you may use String.escaped, which will produce center justified line breaks, or Print.escaped which allows also to choose between center, left and right justified lines.
hedge atributes (same comment as for vertex attributes).

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

print_dot ~style="ranksep=0.1; size=\"7,10\";" ~titlestyle="shape=ellipse,style=bold,style=filled,fontsize=20" ~vertexstyle="shape=box,fontsize=12" ~hedgestyle="shape=ellipse,fontsize=12" ~title="" ....

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
			and module HashV=T.HashV
			and module HashH=T.HashH

Compare interface

module Compare: sig .. end

	`hashv : 'a Hashhe.compare;`
	`hashh : 'b Hashhe.compare;`
	`comparev : 'a -> 'a -> int;`
	`compareh : 'b -> 'b -> int;`

	`attrvertex : 'b;`
	`mutable predhedge : 'a Sette.set;`
	`mutable succhedge : 'a Sette.set;`

	`attrhedge : 'b;`
	`predvertex : 'a array;`
	`succvertex : 'a array;`

	`vertex : ('a, ('b, 'c) vertex_n) Hashhe.hashtbl;`
	`hedge : ('b, ('a, 'd) hedge_n) Hashhe.hashtbl;`
	`info : 'e;`