Graph Algorithms Handout

graph.md

Graph Algorithms Hand-Out

Terms

• graph: G = (V, E)
  • V = vertices, nodes
  • E = edges, i.e., pairs (n, m) of nodes; [directed] links between nodes
• node n is adjacent to node m if there is an edge (n, m) or (m, n)
  • generally there are multiple nodes adjacent to a node n
  • for a node it is possible to get iterators for the adjacent nodes
• edge e = (n, m) is incident to nodes n and m
  • source node n and target node m can be access directly
  • for a node it is possible get iterator for the incident edges
• nodes and edges may have properties:
  • nodes may, e.g., have a _position, a supply, a demand, a color, etc.
  • edges may, e.g., have a weight, a capacity, a length, a flow, a color, etc.

Abstraction

Graph Structure

Not all of the functions need to modelled for all algorithms

Expression	Type	Semantics
g	G	G is a type modelling the Graph concept and g is an instance thereof
vit	using VI = typename G::vertex_iterator	an iterator over all vertices and instances there of
v = *vit	using V = typename G::vertex_descriptor	a handle to access a specific node
eit	using EI = typename G::edge_iterator	an iterator over all edges and instances thereof
e = *eit	using E = typename G::edge_descriptor	a handle to access a specific edge
ait	using AI = typename G::adjacency_iterator	an iterator over adjacent nodes
v = *ait	typename G::vertex_descriptor	access to the adjacent node
oit	using II = typename G::out_edge_iterator	an iterator over incident edges (in edge direction)
e = *oit	typename G::edge_descriptor	access to the incident edge
iit	using II = typename G::in_edge_iterator	an iterator over incident edges (against edge direction)
e = *oit	typename G::edge_descriptor	access to the incident edge
s = source(e, g)	V	source node incident to e
t = target(e, g)	V	target node incident to e
vertices(g)	pair<VI, VI>	begin/end iterator for the range of nodes
edges(g)	pair<EI, EI>	begin/end iterator for the range of edges
adjacent_vertices(v, g)	pair<AI, AI>	access to iterators for the nodes adjacent to v
out_edges(v, g)	pair<OI, OI>	begin/end iterator for the range of edges incident to v leading from v
in_edges(v, g)	pair<II, II>	begin/end iterator for the range of edges incident to v leading to v

Property Map

Access to a property associated with a node or an edge. The key is a vertex descriptor to access a node property or an edge descriptor to access an edge property

Expression	Type	Semantics
pm	PM	a class modelling a property map and an instance thereof
p = get(pm, key)	typename PM::type	read the value of the property for the object key
put(pm, key, p)		set the value of the property for th object key to p
pm[key]	typename PM::reference	lvalue access to the property type