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
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

Tests on graphs
val is_empty : graph -> bool
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

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

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)

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