cugra/graph.h: Graph Struct and Primitives
[cugra: A Small Graph Library]

Data Structures
struct	cugra_graph
struct	cugra_graph_with_arcset
struct	cugra_vertex
struct	cugra_adjlink
struct	cugra_arc
Defines
#define	CUGRA_GFLAG_UNDIRECTED   1
#define	CUGRA_GFLAG_LOOPFREE   2
#define	CUGRA_GFLAG_SIMPLEARCED   4
#define	CUGRAP_ARC_ADJLINK_LINK_OFFSET(dir)
#define	cugra_vertex_for_inarcs(a, v)
#define	cugra_vertex_for_outarcs(a, v)
#define	cugra_vertex_for_arcs(dir, a, v)
#define	cugra_vertex_for_inoutarcs(dir, a, v)
#define	cugra_graph_for_vertices(v, G)
Enumerations
enum	cugra_direction_t { cugra_direction_BEGIN, cugra_direction_out = 0, cugra_direction_in = 1, cugra_direction_END }
Functions
void	cugra_graph_init (cugra_graph_t G, unsigned int gflags)
cugra_graph_t	cugra_graph_new (unsigned int gflags)
void	cugra_graph_merge (cugra_graph_t G_dst, cugra_graph_t G_src)
cu_bool_t	cugra_graph_is_directed (cugra_graph_t G)
cu_bool_t	cugra_graph_is_simplearced (cugra_graph_t G)
void	cugra_graph_vertex_init (cugra_graph_t G, cugra_vertex_t v)
cugra_vertex_t	cugra_graph_vertex_new (cugra_graph_t G)
cugra_vertex_t	cugra_graph_vertex_new_mem (cugra_graph_t G, size_t size)
cugra_vertex_t	cugra_graph_vertex_new_ptr (cugra_graph_t G, void *ptr)
void *	cugra_vertex_mem (cugra_vertex_t v)
void *	cugra_vertex_ptr (cugra_vertex_t v)
cu_bool_t	cugra_vertex_is_isolated (cugra_vertex_t v)
cu_bool_t	cugra_vertex_is_sink (cugra_vertex_t v)
cu_bool_t	cugra_vertex_is_source (cugra_vertex_t v)
cu_bool_t	cugra_vertex_is_convergency (cugra_vertex_t v)
cu_bool_t	cugra_vertex_is_divergency (cugra_vertex_t v)
cu_bool_t	cugra_vertex_outdegree_leq_1 (cugra_vertex_t v)
cu_bool_t	cugra_vertex_indegree_leq_1 (cugra_vertex_t v)
cu_bool_t	cugra_vertex_has_loop (cugra_vertex_t v)
cu_bool_t	cugra_connect_custom (cugra_graph_t G, cugra_vertex_t tail, cugra_vertex_t head, size_t arc_size, cugra_arc_t *arc_out)
cu_bool_t	cugra_connect (cugra_graph_t G, cugra_vertex_t tail, cugra_vertex_t head)
int	cugra_disconnect (cugra_graph_t G, cugra_vertex_t tail, cugra_vertex_t head)
void	cugra_erase_arc (cugra_graph_t G, cugra_arc_t arc)
cugra_arc_t	cugra_graph_arc_new (cugra_vertex_t tail, cugra_vertex_t head) CU_ATTR_DEPRECATED
cugra_arc_t	cugra_graph_arc_new_mem (cugra_vertex_t tail, cugra_vertex_t head, size_t size) CU_ATTR_DEPRECATED
cugra_arc_t	cugra_graph_arc_new_ptr (cugra_vertex_t tail, cugra_vertex_t head, void *ptr) CU_ATTR_DEPRECATED
void	cugra_erase_vertex (cugra_graph_t G, cugra_vertex_t v)
	cu_clos_edec (cugra_erase_vertex_clos, cu_prot(void, cugra_vertex_t),(cugra_graph_t G;))
void	cugra_eliminate_vertex (cugra_graph_t G, cugra_vertex_t v)
void	cugra_vertex_erase_loops (cugra_graph_t G, cugra_vertex_t v)
void	cugra_graph_erase_loops (cugra_graph_t G)
void *	cugra_arc_mem (cugra_arc_t a)
void *	cugra_arc_ptr (cugra_arc_t a)
cugra_vertex_t	cugra_arc_adjacent (cugra_direction_t dir, cugra_arc_t e)
cugra_vertex_t	cugra_arc_head (cugra_arc_t e)
cugra_vertex_t	cugra_arc_tail (cugra_arc_t e)
cu_bool_t	cugra_arc_connects (cugra_arc_t a, cugra_vertex_t vT, cugra_vertex_t vH)
cu_bool_t	cugra_arc_unord_connects (cugra_arc_t a, cugra_vertex_t v0, cugra_vertex_t v1)
cu_bool_t	cugra_arc_is_loop (cugra_arc_t a)
cugra_arc_t	cugra_vertex_arcs_begin (cugra_direction_t dir, cugra_vertex_t v)
cugra_arc_t	cugra_vertex_arcs_end (cugra_direction_t dir, cugra_vertex_t v)
cugra_arc_t	cugra_vertex_arcs_next (cugra_direction_t dir, cugra_arc_t e)
cugra_arc_t	cugra_vertex_outarcs_begin (cugra_vertex_t v)
cugra_arc_t	cugra_vertex_outarcs_end (cugra_vertex_t v)
cugra_arc_t	cugra_vertex_outarcs_next (cugra_arc_t e)
cugra_arc_t	cugra_vertex_inarcs_begin (cugra_vertex_t v)
cugra_arc_t	cugra_vertex_inarcs_end (cugra_vertex_t v)
cugra_arc_t	cugra_vertex_inarcs_next (cugra_arc_t e)
cugra_vertex_t	cugra_graph_vertices_begin (cugra_graph_t G)
cugra_vertex_t	cugra_graph_vertices_end (cugra_graph_t G)
cugra_vertex_t	cugra_graph_vertices_next (cugra_vertex_t v)
cugra_arc_t	cugra_graph_arcs_begin (cugra_graph_t G)
cugra_arc_t	cugra_graph_arcs_end (cugra_graph_t G)
cugra_arc_t	cugra_graph_arcs_next (cugra_graph_t G, cugra_arc_t a)

---

Detailed Description

This defines a directed graph with access to both input and output arcs for each vertex, using doubly linked lists. Thus single arc updates is O(1) and single vertex updates is linear in the number of incident arcs.

The structure can quite easily be used for undirected graphs, as well, using the io/out generic methods. This is done by iterating over the cugra_direction_t argument before iterating over the incident arcs

 cugra_direction_t dir;
 cugra_arc_t e;
 for (dir = 0; dir < 2; ++dir)
 for (e = cugra_vertex_arcs_begin(dir, v);
      e != cugra_vertex_arcs_end(dir, v);
      e = cugra_vertex_arcs_next(dir, e))
     process(e);

---

Define Documentation

#define CUGRA_GFLAG_LOOPFREE   2

Unused. The graph has no loops.

#define CUGRA_GFLAG_SIMPLEARCED   4

All arcs are simple.

#define CUGRA_GFLAG_UNDIRECTED   1

Graph is undirected.

#define cugra_graph_for_vertices	(	v,
		G		)

Value:

for (v = cugra_graph_vertices_begin(G);                         \
         v != cugra_graph_vertices_end(G);                              \
         v = cugra_graph_vertices_next(v))

#define cugra_vertex_for_arcs	(	dir,
		a,
		v		)

Value:

for (a = cugra_vertex_arcs_begin(dir, v);                               \
         a != cugra_vertex_arcs_end(dir, v);                            \
         a = cugra_vertex_arcs_next(dir, a))

#define cugra_vertex_for_inarcs	(	a,
		v		)

Value:

for (a = cugra_vertex_inarcs_begin(v);                          \
         a != cugra_vertex_inarcs_end(v);                               \
         a = cugra_vertex_inarcs_next(a))

#define cugra_vertex_for_inoutarcs	(	dir,
		a,
		v		)

Value:

for (dir = cugra_direction_BEGIN; dir < cugra_direction_END; ++dir)     \
    for (a = cugra_vertex_arcs_begin(dir, v);                           \
         a != cugra_vertex_arcs_end(dir, v);                            \
         a = cugra_vertex_arcs_next(dir, a))

#define cugra_vertex_for_outarcs	(	a,
		v		)

Value:

for (a = cugra_vertex_outarcs_begin(v);                         \
         a != cugra_vertex_outarcs_end(v);                              \
         a = cugra_vertex_outarcs_next(a))

#define CUGRAP_ARC_ADJLINK_LINK_OFFSET

(

dir

)

Value:

( offsetof(struct cugra_arc, adj[0])            \
      + sizeof(struct cugra_adjlink)*(dir)              \
      + offsetof(struct cugra_adjlink, link) )

---

Enumeration Type Documentation

enum cugra_direction_t

Enumerator:

cugra_direction_out	Index for accessing out-arcs of a vertex.
cugra_direction_in	Index for accessing in-arcs of a vertex.

---

Function Documentation

cugra_vertex_t cugra_arc_adjacent	(	cugra_direction_t	dir,
		cugra_arc_t	e
	)

Given that we are iterating over incedent arcs of direction dir from a vertex v, this returns the vertex adjacent to v due to e.

cu_bool_t cugra_arc_connects	(	cugra_arc_t	a,
		cugra_vertex_t	vT,
		cugra_vertex_t	vH
	)

True iff a points from vH to vT.

cugra_vertex_t cugra_arc_head

(

cugra_arc_t

e

)

The head of e.

cu_bool_t cugra_arc_is_loop

(

cugra_arc_t

a

)

True iff a is a loop (head = tail).

void* cugra_arc_mem

(

cugra_arc_t

a

)

A pointer to the slot of a.

void* cugra_arc_ptr

(

cugra_arc_t

a

)

Assume the slot of a contains a pointer and return it.

cugra_vertex_t cugra_arc_tail

(

cugra_arc_t

e

)

The tail of e.

cu_bool_t cugra_arc_unord_connects	(	cugra_arc_t	a,
		cugra_vertex_t	v0,
		cugra_vertex_t	v1
	)

True iff joins vertices v0 and v1 in any direction.

cu_bool_t cugra_connect	(	cugra_graph_t	G,
		cugra_vertex_t	tail,
		cugra_vertex_t	head
	)

Connects tail to head. If the graph has simple arcs and an arc from tail to head exists, then returns false, otherwise returns true.

cu_bool_t cugra_connect_custom	(	cugra_graph_t	G,
		cugra_vertex_t	tail,
		cugra_vertex_t	head,
		size_t	arc_size,
		cugra_arc_t *	arc_out
	)

Connects tail to head with a custom arc type of size arc_size which is returned in *out_arc. If the graph has simple arcs and an arc from tail to head exists, then returns false and sets *arc_out to the found arc. Otherwise, returns true.

int cugra_disconnect	(	cugra_graph_t	G,
		cugra_vertex_t	tail,
		cugra_vertex_t	head
	)

Removes all arcs from tail to head, and returns the number removed.

void cugra_eliminate_vertex	(	cugra_graph_t	G,
		cugra_vertex_t	v
	)

Make arcs from each in-neightbour of v to each out-neighbour of v, and erase v and all its incident arcs.

void cugra_erase_arc	(	cugra_graph_t	G,
		cugra_arc_t	arc
	)

Erases arc.

void cugra_erase_vertex	(	cugra_graph_t	G,
		cugra_vertex_t	v
	)

Erase v and all incident arcs from G.

cugra_arc_t cugra_graph_arc_new	(	cugra_vertex_t	tail,
		cugra_vertex_t	head
	)

Insert an arc from tail to head and return a reference to it.

cugra_arc_t cugra_graph_arc_new_mem	(	cugra_vertex_t	tail,
		cugra_vertex_t	head,
		size_t	size
	)

Insert an arc from tail to head with slot size size and return it.

cugra_arc_t cugra_graph_arc_new_ptr	(	cugra_vertex_t	tail,
		cugra_vertex_t	head,
		void *	ptr
	)

Insert an arc from tail to head with slot initialised to ptr and return it.

cugra_arc_t cugra_graph_arcs_begin

(

cugra_graph_t

G

)

The first of the sequence of all arcs of G.

cugra_arc_t cugra_graph_arcs_end

(

cugra_graph_t

G

)

The end marker of the sequence of all arcs of G.

cugra_arc_t cugra_graph_arcs_next	(	cugra_graph_t	G,
		cugra_arc_t	a
	)

The arc after a in the sequence of all arcs of G.

void cugra_graph_erase_loops

(

cugra_graph_t

G

)

Erase loops on all vertices of G.

void cugra_graph_init	(	cugra_graph_t	G,
		unsigned int	gflags
	)

Construct G as an empty graph. This constructor does not support the CUGRA_GFLAG_SIMPLEARCED flag, use cugra_graph_new in that case.

cu_bool_t cugra_graph_is_directed

(

cugra_graph_t

G

)

True iff G was created without the CUGRA_GFLAG_UNDIRECTED flag, i.e. it's a directed graph.

cu_bool_t cugra_graph_is_simplearced

(

cugra_graph_t

G

)

True iff G was created with the CUGRA_GFLAG_SIMPLEARCED flag, i.e. all arcs are kept simple by the graph methods.

void cugra_graph_merge	(	cugra_graph_t	G_dst,
		cugra_graph_t	G_src
	)

Moves all vertices and arcs from G_src into G_dst.

cugra_graph_t cugra_graph_new

(

unsigned int

gflags

)

Return an empty graph.

void cugra_graph_vertex_init	(	cugra_graph_t	G,
		cugra_vertex_t	v
	)

Construct and insert v into G. This variant is useful when v is inherited in another struct, otherwise see cugra_graph_vertex_new.

cugra_vertex_t cugra_graph_vertex_new

(

cugra_graph_t

G

)

Insert a vertex into G and return a referece to it. If you need to store data on the vertex, use cugra_graph_vertex_new_mem or cugra_graph_vertex_new_ptr.

cugra_vertex_t cugra_graph_vertex_new_mem	(	cugra_graph_t	G,
		size_t	size
	)

Insert a vertex into G with slot size size and return it.

cugra_vertex_t cugra_graph_vertex_new_ptr	(	cugra_graph_t	G,
		void *	ptr
	)

Insert a vertex into G, with ptr stored in its slot, and return it.

cugra_vertex_t cugra_graph_vertices_begin

(

cugra_graph_t

G

)

The first of the sequence of all vertices of G.

cugra_vertex_t cugra_graph_vertices_end

(

cugra_graph_t

G

)

An end marker of the sequence of all vertices in G.

cugra_vertex_t cugra_graph_vertices_next

(

cugra_vertex_t

v

)

The vertex after v in the sequence of all vertices of a graph.

cugra_arc_t cugra_vertex_arcs_begin	(	cugra_direction_t	dir,
		cugra_vertex_t	v
	)

The first incident arc with direction dir from v.

cugra_arc_t cugra_vertex_arcs_end	(	cugra_direction_t	dir,
		cugra_vertex_t	v
	)

A past-the-end mark for incident arcs with direction dir from v.

cugra_arc_t cugra_vertex_arcs_next	(	cugra_direction_t	dir,
		cugra_arc_t	e
	)

The next incident arc with direction dir from the terminal of e where e has direction dir.

void cugra_vertex_erase_loops	(	cugra_graph_t	G,
		cugra_vertex_t	v
	)

Erase all loops on v.

cu_bool_t cugra_vertex_has_loop

(

cugra_vertex_t

v

)

True iff v has a loop.

cugra_arc_t cugra_vertex_inarcs_begin

(

cugra_vertex_t

v

)

The first in-arc of v.

cugra_arc_t cugra_vertex_inarcs_end

(

cugra_vertex_t

v

)

An end-of-list marker for the in-arcs of v.

cugra_arc_t cugra_vertex_inarcs_next

(

cugra_arc_t

e

)

The next in-arc to the head of e.

cu_bool_t cugra_vertex_indegree_leq_1

(

cugra_vertex_t

v

)

True iff v is a source or a divergency.

cu_bool_t cugra_vertex_is_convergency

(

cugra_vertex_t

v

)

True iff v has out-degree 1.

cu_bool_t cugra_vertex_is_divergency

(

cugra_vertex_t

v

)

True iff v has in-degree 1.

cu_bool_t cugra_vertex_is_isolated

(

cugra_vertex_t

v

)

True iff v is isolated.

cu_bool_t cugra_vertex_is_sink

(

cugra_vertex_t

v

)

True iff v is a sink, that is, it has out-degree 0.

cu_bool_t cugra_vertex_is_source

(

cugra_vertex_t

v

)

True iff v is a source, that is, it has in-degree 0.

void* cugra_vertex_mem

(

cugra_vertex_t

v

)

A pointer to the slot of v.

cugra_arc_t cugra_vertex_outarcs_begin

(

cugra_vertex_t

v

)

The first out-arc of v.

cugra_arc_t cugra_vertex_outarcs_end

(

cugra_vertex_t

v

)

An end-of-list marker for the out-arcs of v.

cugra_arc_t cugra_vertex_outarcs_next

(

cugra_arc_t

e

)

The next out-arc from the tail of e.

cu_bool_t cugra_vertex_outdegree_leq_1

(

cugra_vertex_t

v

)

True iff v is a sink or a convergency.

void* cugra_vertex_ptr

(

cugra_vertex_t

v

)

Return an assumed pointer stored in the slot of v.