Functions to analyze vertex order in a static graph. More...

Functions
void	get_bfs_order (const StaticGraph &graph, std::vector< verti > &perm)

void	get_dfs_order (const StaticGraph &graph, std::vector< verti > &perm)

edgei	count_ordered_edges (const StaticGraph &g, int dir)

edgei	count_forward_edges (const StaticGraph &g)

edgei	count_backward_edges (const StaticGraph &g)

edgei	counts_self_edges (const StaticGraph &g)

Detailed Description

Functions to analyze vertex order in a static graph.

This file declares functions that are useful to determine the ordering of vertices in a graph, and find ways to reorder them (for example, to obtain mostly forward-oriented edges).

See also: ParityGame::shuffle

Definition in file GraphOrdering.h.

Function Documentation

◆ count_backward_edges()

edgei count_backward_edges ( const StaticGraph & g )

inline

Returns the number of edges (i,j) such that i > j

Definition at line 45 of file GraphOrdering.h.

◆ count_forward_edges()

edgei count_forward_edges ( const StaticGraph & g )

inline

Returns the number of edges (i,j) such that i < j

Definition at line 40 of file GraphOrdering.h.

◆ count_ordered_edges()

edgei count_ordered_edges	(	const StaticGraph &	g,
		int	dir
	)

Count the number of edges with a specific ordering of vertices. An edge (i,j) is counted if sign(j - i) == sign(dir).

Definition at line 15 of file GraphOrdering.cpp.

◆ counts_self_edges()

edgei counts_self_edges ( const StaticGraph & g )

inline

Returns the number of edges (i,j) such that i = j

Definition at line 50 of file GraphOrdering.h.

◆ get_bfs_order()

void get_bfs_order	(	const StaticGraph &	graph,
		std::vector< verti > &	perm
	)

Traverses the graph in breadth-first search order, and returns the result in perm, such that perm[v] = i if v is the i-th visited vertex.

Definition at line 30 of file GraphOrdering.cpp.

◆ get_dfs_order()

void get_dfs_order	(	const StaticGraph &	graph,
		std::vector< verti > &	perm
	)

Traverses the graph in depth-first search order, and returns the result in perm, such that perm[v] = i if v is the i-th visited vertex.

Definition at line 60 of file GraphOrdering.cpp.