Computation of Articulation Points (APs) on undirected graphs. More...

Namespaces
namespace	detail

namespace	utils

Classes
class	AbstractGraph
	Abstract class for representing graphs. More...

class	AdjacencyData
	Data for an undirected graph. More...

class	BFS

class	BruteForceColouring
	For colouring vertices in a single connected component of a graph. More...

class	ColouringPriority
	Use some simple heuristics (quite fast) to try to find a good vertex order for our attempted colouring, which will then be done by brute force (the slow part). More...

class	CompleteGraph

class	DFS

class	DirectedGraph
	DirectedGraph instances are loop-free directed graphs. More...

class	DirectedGraphBase

class	EdgeDoesNotExistError

struct	GraphColouringResult
	The calculated colouring for a graph. More...

struct	GraphColouringRoutines
	It's expected that more routines will be added over time! More...

struct	GraphRoutines
	General easily reusable routines related to graphs. More...

struct	LargeCliquesResult
	Try to find large cliques in a single connected component of a graph. More...

class	NodeDoesNotExistError

class	NodesNotConnected
	Exception thrown because two nodes are disconnected from one another. More...

struct	WeightedEdge
	Weighted edge. More...

Typedefs
template<typename T >
using	UndirectedConnGraph = typename DirectedGraph< T >::UndirectedConnGraph

using	dist_vec = std::vector< std::size_t >

Functions
template<typename T >
std::set< T >	get_subgraph_aps (const UndirectedConnGraph< T > &graph, const UndirectedConnGraph< T > &subgraph)
	Given a graph and a subgraph, returns the subgraph APs, as defined in the introduction above.

template std::set< UnitID >	get_subgraph_aps (const UndirectedConnGraph< UnitID > &graph, const UndirectedConnGraph< UnitID > &subgraph)

template std::set< Node >	get_subgraph_aps (const UndirectedConnGraph< Node > &graph, const UndirectedConnGraph< Node > &subgraph)

template<typename Graph , typename PMap >
BFS< Graph, PMap >	run_bfs (utils::vertex< Graph > root, Graph &&g, PMap &pmap)

template<typename Graph >
BFS< Graph >	run_bfs (utils::vertex< Graph > root, Graph &&g)

template<typename Graph , typename PMap >
DFS< Graph, PMap >	run_dfs (utils::vertex< Graph > root, Graph &&g, PMap &pmap)

template<typename Graph >
DFS< Graph >	run_dfs (utils::vertex< Graph > root, Graph &&g)

template<typename Graph , typename Visitor >
DFS< Graph >	run_dfs_with_visitor (utils::vertex< Graph > root, Graph &&g, Visitor vis)

template<typename Graph >
std::vector< utils::vertex< Graph > >	longest_simple_path (const Graph &g, std::size_t cutoff_length=0)

Detailed Description

Computation of Articulation Points (APs) on undirected graphs.

This problem is of interest as we can use APs to maintain connectivity requirements in Architectures and QubitGraphs. The BGL already provides an implementation of this, but it does not quite satisfy our needs – only a loser definition of connectivity matters to us. The following will give more details.

Articulation Points (APs) are vertices in a graph that cannot be removed without breaking the graph connectivity. This concept is closely linked to biconnected components, i.e. connected subgraphs in which removing any vertex will not affect the subgraph connectivity.

For a given graph G, we can then define a map belong_to_comp that maps any vertex to the set of biconnected components it belongs to. Note that any vertex v will belong to at least one biconnected component (which in the worst case will contain a single vertex). It is a well-known graph theoretical result that APs can equivalently be characterised as the vertices that belong to more than one biconnected component. APs (and biconnected components) can be efficiently computed in linear time O(V + E).

For our needs, we replace the connectivity requirements in the definition of APs to only consider subgraph connectivity: given a subgraph, we say that the graph is subgraph-connected iff any two vertices of the subgraph are connected in the graph G. I.e. instead of "vanilla" APs, we are only interested in APs that break subgraph connectivity when removed: we call them subgraph APs. Remark that i) the subgraph APs are necessarily contained in the set of all APs of the graph, as our connectivity requirements are strictly weaker. ii) the subgraph APs will not be elements of the subgraph in general

BGL implementation: https://www.boost.org/doc/libs/1_75_0/libs/graph/doc/biconnected_components.html These functions only work for the UndirectedConnGraph graph type (typedef in ArticulationPoints_impl.hpp) i.e. undirected graphs of DirectedGraph objects They are not defined for BGL graphs in general

The reason for this is that we need the vertices to have a UnitID property to identify vertices from the main graph and the subgraph Implementation specific details (in particular the class detail::BicomponentGraph is in the file ArticulationPoints_impl.hpp

Typedef Documentation

◆ dist_vec

using tket::graphs::dist_vec = typedef std::vector<std::size_t>

Definition at line 26 of file Utils.hpp.

◆ UndirectedConnGraph

template<typename T >

using tket::graphs::UndirectedConnGraph = typedef typename DirectedGraph<T>::UndirectedConnGraph

Definition at line 26 of file ArticulationPoints_impl.hpp.

Function Documentation

◆ get_subgraph_aps() [1/3]

template std::set< Node > tket::graphs::get_subgraph_aps	(	const UndirectedConnGraph< Node > &	graph,
		const UndirectedConnGraph< Node > &	subgraph
	)

◆ get_subgraph_aps() [2/3]

template<typename T >

std::set< T > tket::graphs::get_subgraph_aps	(	const UndirectedConnGraph< T > &	graph,
		const UndirectedConnGraph< T > &	subgraph
	)

Given a graph and a subgraph, returns the subgraph APs, as defined in the introduction above.

Definition at line 208 of file ArticulationPoints.cpp.

◆ get_subgraph_aps() [3/3]

template std::set< UnitID > tket::graphs::get_subgraph_aps	(	const UndirectedConnGraph< UnitID > &	graph,
		const UndirectedConnGraph< UnitID > &	subgraph
	)

◆ longest_simple_path()

template<typename Graph >

std::vector< utils::vertex< Graph > > tket::graphs::longest_simple_path	(	const Graph &	g,
		std::size_t	cutoff_length = `0`
	)

Definition at line 98 of file TreeSearch.hpp.

◆ run_bfs() [1/2]

template<typename Graph >

BFS< Graph > tket::graphs::run_bfs	(	utils::vertex< Graph >	root,
		Graph &&	g
	)

Definition at line 67 of file TreeSearch.hpp.

◆ run_bfs() [2/2]

template<typename Graph , typename PMap >

BFS< Graph, PMap > tket::graphs::run_bfs	(	utils::vertex< Graph >	root,
		Graph &&	g,
		PMap &	pmap
	)

Definition at line 61 of file TreeSearch.hpp.

◆ run_dfs() [1/2]

template<typename Graph >

DFS< Graph > tket::graphs::run_dfs	(	utils::vertex< Graph >	root,
		Graph &&	g
	)

Definition at line 79 of file TreeSearch.hpp.

◆ run_dfs() [2/2]

template<typename Graph , typename PMap >

DFS< Graph, PMap > tket::graphs::run_dfs	(	utils::vertex< Graph >	root,
		Graph &&	g,
		PMap &	pmap
	)

Definition at line 73 of file TreeSearch.hpp.

◆ run_dfs_with_visitor()

template<typename Graph , typename Visitor >

DFS< Graph > tket::graphs::run_dfs_with_visitor	(	utils::vertex< Graph >	root,
		Graph &&	g,
		Visitor	vis
	)

Definition at line 85 of file TreeSearch.hpp.

Namespaces

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ dist_vec

◆ UndirectedConnGraph

Function Documentation

◆ get_subgraph_aps() [1/3]

◆ get_subgraph_aps() [2/3]

◆ get_subgraph_aps() [3/3]

◆ longest_simple_path()

◆ run_bfs() [1/2]

◆ run_bfs() [2/2]

◆ run_dfs() [1/2]

◆ run_dfs() [2/2]

◆ run_dfs_with_visitor()