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