src/overlap_graph.c File Reference

Overlap graph implementation. More...

#include "overlap_graph.h"
#include "disjoint_set.h"
#include "priority_queue.h"
#include "list.h"
#include "debug.h"
#include <errno.h>
#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>

Include dependency graph for overlap_graph.c:

Go to the source code of this file.

Data Structures
struct	edge
	An overlap graph edge. More...
struct	vertex
	An overlap graph vertex. More...
struct	overlap_graph
	An overlap graph. More...
Functions
static off_t	calculate_overlap (off_t start1, off_t size1, off_t start2, off_t size2)
	Calculates the overlap of two ranges.
static int	overlap_graph_add_edge (overlap_graph_t *g, size_t src_id, size_t dst_id, off_t weight)
	Adds an edge to the overlap graph.
static int	topo_visit (overlap_graph_t *g, size_t n, list_t *list)
	Visit depth-first the vertices of an overlap graph prepending them to the list as they finish.
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_export_dot (overlap_graph_t *g, int fd)
	Exports an overlap graph to the dot format.
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.

---

Detailed Description

Overlap graph implementation.

Definition in file overlap_graph.c.

---

Function Documentation

static off_t calculate_overlap	(	off_t	start1,
		off_t	size1,
		off_t	start2,
		off_t	size2
	)			[static]

Calculates the overlap of two ranges.

Parameters:

	start1	start of first range
	size1	size of first range
	start2	start of second range
	size2	size of second range

Returns:

the operation error code

Definition at line 87 of file overlap_graph.c.

Referenced by overlap_graph_add_segment().

Here is the caller graph for this function:

static int overlap_graph_add_edge	(	overlap_graph_t *	g,
		size_t	src_id,
		size_t	dst_id,
		off_t	weight
	)			[static]

Adds an edge to the overlap graph.

Parameters:

	g	the overlap graph
	src_id	the id of the source of the edge
	dst_id	the id of the destination of the edges
	weight	the weight of the edge

Returns:

the operation error code

Definition at line 124 of file overlap_graph.c.

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

Referenced by overlap_graph_add_segment().

Here is the caller graph for this function:

static int topo_visit	(	overlap_graph_t *	g,
		size_t	n,
		list_t *	list
	)			[static]

Visit depth-first the vertices of an overlap graph prepending them to the list as they finish.

Parameters:

	g	the overlap graph
	n	the vertex id of the vertex to visit
	list	the list to add the vertices

Returns:

the operation error code

Definition at line 169 of file overlap_graph.c.

References edge::dst_id, vertex::head, list_head(), list_insert_after(), vertex::mapping, edge::next, edge::removed, vertex::segment, vertex::self_loop_weight, overlap_graph::tail, overlap_graph::vertices, and vertex::visited.

Referenced by overlap_graph_get_vertices_topo().

Here is the call graph for this function:

Here is the caller graph for this function: