module Inter_graph:`sig`

..`end`

Interference and preference graphs

`type `

graph

type of interference and preference graphs

`val empty : ``graph`

**Returns**the empty graph

`val add_reg : ``graph -> Register.reg -> graph`

add a register as a node of the graph

`val remove_reg : ``graph -> Register.reg -> graph`

remove a register of the graph, removing all edges comming out this register

`val add_interference : ``Register.reg -> Register.reg -> graph -> graph`

add an interference edge between two register

`val add_preference : ``Register.reg -> Register.reg -> graph -> graph`

add a preference edge between two register

`val remove_preferences : ``graph -> Register.reg -> graph`

remove all preference edges comming out a register

`val join_nodes : ``graph ->`

Register.reg -> Register.reg -> graph * Register.reg

`join_nodes g a b`

joins the two nodes `a`

and `b`

into a new node `a|b`

**Returns**the resulting graph and the joined register

`val is_empty : ``graph -> bool`

**Returns**`true`

iff the graph is empty

`val degree : ``graph -> Register.reg -> int`

`val neighbour : ``graph -> Register.reg -> Register.reg -> bool`

`neighbour g a b`

returns `true`

iff there is a interference edge between `a`

and `b`

in `g`

`val prefer_out : ``graph -> Register.reg -> bool`

`prefer_out g r`

returns `true`

iff there is at least one preference edge comming out `r`

in `g`

`val find_register : ``(Register.reg -> bool) -> graph -> Register.reg option`

`find_register p g`

returns a pseudo-register of `g`

satisfying a predicate `p`

**Returns**`Some r`

if such a**pseudo**-register`r`

exists,`None`

else (even if a real register satisfies`p`

)

`val find_preference : ``(Register.reg -> Register.reg -> bool) ->`

graph -> (Register.reg * Register.reg) option

`find_preference p g`

returns a preference edge of `g`

satisfying a predicate `p`

, at least one of the nodes is assumed to be a pseudo-register, not a real register

**Returns**`Some (a,b)`

if there exists a preference edge between`a`

and`b`

satisfying`p a b`

with at least`a`

or`b`

a**pseudo**-register,`None`

else

`val neighbours : ``graph -> Register.reg -> Register.reg list`

`neighbours g a`

returns the list of nodes of `g`

that interfers with `a`

`val choose : ``graph -> Register.reg`

`choose g`

returns some node of `g`

(pseudo or real register)

**Raises**`Invalid_argument`

if the graph is empty

`val print_graph : ``graph -> unit`

opens a Firefox window with a graphical representation of the graph

`val print_graph_coloring : ``graph -> Coloring.coloring -> unit`

same as `Inter_graph.print_graph`

, but with a (partial) coloring