Overlap Graph

Graph showing the overlap of segments. More...

Data Structures
struct	edge_entry
	List entry for edges. More...
struct	vertex_entry
	List entry for segments. More...
Typedefs
typedef struct overlap_graph	overlap_graph_t
	Opaque type for overlap graph.
Functions
int	overlap_graph_new (overlap_graph_t **g, size_t capacity)
	Creates an new overlap graph.
int	overlap_graph_free (overlap_graph_t *g)
	Frees an overlap graph.
int	overlap_graph_add_segment (overlap_graph_t *g, segment_t *seg, off_t mapping)
	Adds a segment to an overlap graph.
int	overlap_graph_remove_cycles (overlap_graph_t *g)
	Removes cycles from the graph.
int	overlap_graph_get_removed_edges (overlap_graph_t *g, list_t **edges)
	Gets the edges removed from the graph.
int	overlap_graph_get_vertices_topo (overlap_graph_t *g, list_t **vertices)
	Gets the vertices in topological order.
int	overlap_graph_export_dot (overlap_graph_t *g, int fd)
	Exports an overlap graph to the dot format.

---

Detailed Description

Graph showing the overlap of segments.

See doc/devel/buffer_save.txt for more information.

---

Function Documentation

int overlap_graph_add_segment	(	overlap_graph_t *	g,
		segment_t *	seg,
		off_t	mapping
	)

Adds a segment to an overlap graph.

Parameters:

	g	the overlap graph to add the segment to
	seg	the segment to add
	mapping	the mapping of the segment in its buffer

Returns:

the operation error code

Definition at line 291 of file overlap_graph.c.

References calculate_overlap(), capacity, vertex::head, vertex::in_degree, vertex::mapping, edge::next, vertex::out_degree, overlap_graph_add_edge(), vertex::segment, segment_copy(), segment_free(), segment_get_size(), segment_get_start(), vertex::self_loop_weight, size, tail, vertices, and vertex::visited.

Referenced by create_overlap_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

int overlap_graph_export_dot	(	overlap_graph_t *	g,
		int	fd
	)

Exports an overlap graph to the dot format.

Parameters:

	g	the overlap graph to export
	fd	the file descriptor to write the data to

Returns:

the operation error code

Definition at line 496 of file overlap_graph.c.

References edge::dst_id, vertex::head, vertex::in_degree, edge::next, vertex::out_degree, edge::removed, vertex::self_loop_weight, size, edge::src_id, tail, vertices, and edge::weight.

int overlap_graph_free

(

overlap_graph_t *

g

)

Frees an overlap graph.

This function does not free the segments associated with the overlap graph.

Parameters:

g

the overlap graph to free

Returns:

the operation error code

Definition at line 259 of file overlap_graph.c.

References vertex::head, edge::next, vertex::segment, segment_free(), size, tail, and vertices.

Referenced by bless_buffer_save(), and create_overlap_graph().

Here is the call graph for this function:

Here is the caller graph for this function:

int overlap_graph_get_removed_edges	(	overlap_graph_t *	g,
		list_t **	edges
	)

Gets the edges removed from the graph.

Parameters:

	g	the overlap graph containing removed the edges
[out]	edges	the list containing entries of type struct edge_entry

Returns:

the operation error code

Definition at line 551 of file overlap_graph.c.

References edge::dst_id, vertex::head, list_entry, list_for_each_safe, list_free(), list_head(), list_insert_before(), list_new, list_tail(), vertex::mapping, edge::next, edge::removed, vertex::segment, size, tail, vertices, and edge::weight.

Referenced by bless_buffer_save().

Here is the call graph for this function:

Here is the caller graph for this function:

int overlap_graph_get_vertices_topo	(	overlap_graph_t *	g,
		list_t **	vertices
	)

Gets the vertices in topological order.

The overlap graph must have no cycles for this to work. You can use overlap_graph_remove_cycles() to remove them.

Parameters:

	g	the overlap graph to get the vertices from
[out]	vertices	a list of struct vertex_entry topologically sorted

Returns:

the operation error code

Definition at line 625 of file overlap_graph.c.

References list_entry, list_for_each_safe, list_free(), list_head(), list_new, size, topo_visit(), vertices, and vertex::visited.

Referenced by bless_buffer_save().

Here is the call graph for this function:

Here is the caller graph for this function:

int overlap_graph_new	(	overlap_graph_t **	g,
		size_t	capacity
	)

Creates an new overlap graph.

Parameters:

[out]	g	the created overlap graph
	capacity	the initial capacity (number of vertices) of the graph

Returns:

the operation error code

Definition at line 223 of file overlap_graph.c.

References capacity, edge::next, size, tail, and vertices.

Referenced by create_overlap_graph().

Here is the caller graph for this function:

int overlap_graph_remove_cycles

(

overlap_graph_t *

g

)

Removes cycles from the graph.

This algorithm doesn't change the graph apart from marking the edges as included or not in the graph.

Parameters:

g

the graph to remove the cycles of

Returns:

the operation error code

Definition at line 377 of file overlap_graph.c.

References disjoint_set_find(), disjoint_set_free(), disjoint_set_new(), disjoint_set_union(), vertex::head, vertex::in_degree, edge::next, vertex::out_degree, priority_queue_add(), priority_queue_free(), priority_queue_get_size(), priority_queue_new(), priority_queue_remove_max(), edge::removed, size, tail, vertices, and edge::weight.

Referenced by bless_buffer_save().

Here is the call graph for this function:

Here is the caller graph for this function: