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:


Generated on Sun Nov 15 15:27:58 2009 for libbls by  doxygen 1.6.1