# Module Inter_graph

`module Inter_graph: `sig` .. `end``

Interference and preference graphs

`type graph `

type of interference and preference graphs

Construction of 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
Tests on graphs
`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
Printing functions within firefox
`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