2 * Common use interference graph.
3 * Originally written by Sebastian Hack. Refactored into a seperate
4 * source file and header by Kimon Hoffmann.
5 * @author Sebastian Hack
11 typedef struct _be_if_graph_t be_if_graph_t;
12 typedef struct _be_if_node_t be_if_node_t;
13 typedef struct _be_if_edge_t be_if_edge_t;
16 * Creates a new interference graph with the specified number of
18 * @param slots the initial number of slots used for hashing.
19 * Must be greater than 0.
20 * @return the created, empty interference graph.
22 be_if_graph_t* be_ifg_new(int slots);
25 * Frees the passed interference graph an all contained nodes.
26 * @param graph the interference graph that shall be freed. Please note
27 * that after a call to this function all pointers to the graph,
28 * its edges or its nodes are invalid.
30 void be_ifg_free(be_if_graph_t* graph);
33 * Adds a new undirected interference edge between the two nodes
34 * specified by their node numbers. If the corresponding nodes do
35 * not yet exist in the iunterference grpah they are created pririor
36 * to creation of the edge.
37 * @param graph the graph to add the interference edge to.
38 * @param source the key of the source node.
39 * @param target the key of the target node.
41 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target);
44 * Returns the set of all edges within the specified
46 * @param graph the graph the return the set of edges of.
47 * @return A set of all edges within the specified graph as
48 * be_if_edge_t instances.
50 set* be_get_ifg_edges(const be_if_graph_t* graph);
53 * Returns the set of all nodes within the specified
55 * @param graph the graph the return the set of nodes of.
56 * @return A set of all nodes within the specified graph as
57 * be_if_node_t instances.
59 set* be_get_ifg_nodes(const be_if_graph_t* graph);
62 * Returns whether the specified graph alreadz contains an undirected
63 * edge between the two passed nodes.
64 * @param graph the graph to which containment both nodes @p n1 and
66 * @param n1 the one end of the edge to query the graph for.
67 * @param n2 the other end of the edge.
68 * @return TRUE if the graph contains an edge between @p n1 and @p n2,
71 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2);
73 #define be_ifn_get_degree(ifnode) \
74 pset_count(ifnode->neighb)
76 #define be_ifn_foreach_neighbour(ifnode, curr) \
77 for (curr = pset_first(ifnode->neighb); curr; curr = pset_next(ifnode->neighb))