cugra/graph_algo.h: Graph Algorithms
[cugra: A Small Graph Library]

Functions
void	cugra_graph_copy (cugra_graph_t G_src, cugra_graph_t G_dst, cucon_pmap_t vsrc_to_vdst, cucon_pmap_t vdst_to_vsrc)
cu_bool_t	cugra_graph_is_acyclic (cugra_graph_t G)
void	cugra_graph_erase_isolated (cugra_graph_t G)
void	cugra_erase_vertex_to_vsetcompl_arcs (cugra_graph_t G, cugra_vertex_t v, cucon_pmap_t V)
void	cugra_move_induced_subgraph (cucon_pmap_t V_move, cugra_graph_t G_src, cugra_graph_t G_dst)
void	cugra_identify_MSC (cugra_graph_t G, cucon_stack_t KV, cucon_pmap_t M) CU_ATTR_DEPRECATED
void	cugra_move_MSC_subgraphs (cugra_graph_t G, cucon_stack_t KG) CU_ATTR_DEPRECATED
void	cugra_graph_fwrite_dot (cugra_graph_t G, cu_clop(vertex_label, cu_str_t, cugra_vertex_t), cu_clop(arc_label, cu_str_t, cugra_arc_t), FILE *fout)
cu_bool_t	cugra_graph_save_dot (cugra_graph_t G, cu_clop(vertex_label, cu_str_t, cugra_vertex_t), cu_clop(arc_label, cu_str_t, cugra_arc_t), char const *path)
double	cugra_shortest_path (cugra_direction_t dir, cugra_vertex_t v_start, cu_clop(vertex_test, cu_bool_t, cugra_vertex_t), cu_clop(arc_distance, double, cugra_arc_t), cu_clop(notify_path_unwind, void, cugra_arc_t))

---

Function Documentation

void cugra_erase_vertex_to_vsetcompl_arcs	(	cugra_graph_t	G,
		cugra_vertex_t	v,
		cucon_pmap_t	V
	)

Erase all arcs which connect v to a vertex not in V.

void cugra_graph_copy	(	cugra_graph_t	G_src,
		cugra_graph_t	G_dst,
		cucon_pmap_t	vsrc_to_vdst,
		cucon_pmap_t	vdst_to_vsrc
	)

Copy G_src into G_dst, and insert into vsrc_to_vdst and vdst_to_vsrc, if non-NULL, the vertex-mappings.

void cugra_graph_erase_isolated

(

cugra_graph_t

G

)

Erase all isolated vertices in G.

void cugra_graph_fwrite_dot	(	cugra_graph_t	G,
		cu_clop(vertex_label, cu_str_t, cugra_vertex_t)	,
		cu_clop(arc_label, cu_str_t, cugra_arc_t)	,
		FILE *	fout
	)

Write G in Graphviz .dot format to fout, with labels for vertices and arcs as given by vertex_label and arc_label, repectively, unless cu_clop_null.

cu_bool_t cugra_graph_is_acyclic

(

cugra_graph_t

G

)

True iff G is acyclic.

cu_bool_t cugra_graph_save_dot	(	cugra_graph_t	G,
		cu_clop(vertex_label, cu_str_t, cugra_vertex_t)	,
		cu_clop(arc_label, cu_str_t, cugra_arc_t)	,
		char const *	path
	)

Write G in Graphviz .dot format to path, with labels for vertices and arcs as given by vertex_label and arc_label, respectively, unless cu_clop_null.

void cugra_identify_MSC	(	cugra_graph_t	G,
		cucon_stack_t	KV,
		cucon_pmap_t	M
	)

Finds the maximally connected subgraphs of G and report them in two ways as follows. If KV is non-NULL, push a cucon_pset_t for each subgraph where the keys are the vertices of the subgraph. If M is non-NULL, associate each vertex which is part of a loop with an index identifying the maximally connected subgraph to which it belongs.

Deprecated:

Use cugra_walk_SCC

void cugra_move_induced_subgraph	(	cucon_pmap_t	V_move,
		cugra_graph_t	G_src,
		cugra_graph_t	G_dst
	)

Move vertices in V_move from G_src to G_dst, cutting all arcs between V_move and its complement.

void cugra_move_MSC_subgraphs	(	cugra_graph_t	G,
		cucon_stack_t	KG
	)

Move all maximally connected subgraphs of G into separate graphs and push them onto KG.

Deprecated:

Use cugra_walk_SCC

double cugra_shortest_path	(	cugra_direction_t	dir,
		cugra_vertex_t	v_start,
		cu_clop(vertex_test, cu_bool_t, cugra_vertex_t)	,
		cu_clop(arc_distance, double, cugra_arc_t)	,
		cu_clop(notify_path_unwind, void, cugra_arc_t)
	)

Searches shortest path, according to distances given by arc_distance, from v_start to a vertex for which vertex_test returns true. If found, call notify_path_unwind with arcs of the shortest path in revese order and return the path's distance. Otherwise, return INFINITY.