Graph Class Reference

Class that represents a graph as a matrix (vector of vectors) of adjacencies. More...

#include <graph.hpp>

Public Member Functions
	Graph ()
	Default constructor. More...
	Graph (const std::vector< std::vector< int > > &&adjacencyMatrix)
	constructs graph from provided adjacency matrix More...
	Graph (std::istream &graphStream)
	constructs graph from data in a stream More...
	Graph (std::istream &&graphStream)
	constructs graph from data in a stream More...
auto	getVertexCount () const -> size_t
	Return vertex count. More...
auto	toDotLang () const -> std::string
	returns string in DOT language More...
auto	operator[] (size_t row) const -> std::vector< int >
	subscript operator, for convenience More...
auto	getSize () const -> size_t
	Returns graph size. More...
auto	metricDistanceTo (const Graph &rhs, AlgorithmAccuracy accuracy=AlgorithmAccuracy::EXACT) const -> size_t
	Returns distance to another graph. More...
auto	modularProduct (const Graph &rhs) -> Graph
	Returns modular product of two graphs. More...
auto	maxClique (AlgorithmAccuracy accuracy=AlgorithmAccuracy::EXACT) const -> std::vector< size_t >
	Finds the maximum clique of the graph using Bron-Kerbosch algorithm. More...
auto	modifiedMaxClique (AlgorithmAccuracy accuracy=AlgorithmAccuracy::EXACT) const -> std::vector< size_t >
	modidfied max clique algorithm for finding maximum induced subgraphs. More...
auto	maxSubgraph (const Graph &rhs, AlgorithmAccuracy accuracy=AlgorithmAccuracy::EXACT) -> Graph
	Returns maximum induced subgraph of two graphs. More...
auto	maxCliqueGraph (AlgorithmAccuracy accuracy) const -> Graph
	Graph of max clique. More...
auto	subGraph (std::vector< size_t > &vertices) const -> Graph
	Gives the induced subgraph given by the vertices. More...

Static Public Member Functions
static auto	fromFilename (const std::string &filename) -> Graph
	constructs graph from data in specified filename More...

Friends
auto	operator<< (std::ostream &outputStream, const Graph &graph) -> std::ostream &
	for debugging convenience More...
auto	operator== (const Graph &lhs, const Graph &rhs) -> bool
	checks isomorphisms between 2 graphs More...

Detailed Description

Class that represents a graph as a matrix (vector of vectors) of adjacencies.

Constructor & Destructor Documentation

Graph() [1/4]

Graph::Graph ( )

inline

Default constructor.

Not sure if this should actually be default-constructible tho... And even then, should it be =default?

Graph() [2/4]

Graph::Graph ( const std::vector< std::vector< int > > &&  adjacencyMatrix )

explicit

constructs graph from provided adjacency matrix

Parameters

adjacencyMatrix

is the adjacencyMatrix from which graph will be constructed

Graph() [3/4]

Graph::Graph ( std::istream &  graphStream )

explicit

constructs graph from data in a stream

Parameters

graphStream

is the stream to be read from

Warning

throws invalid_argument if it fails to read the stream at any point

Graph() [4/4]

Graph::Graph ( std::istream &&  graphStream )

inlineexplicit

constructs graph from data in a stream

NB: This directly just calls the lvalue reference constructor
I can't remember if that's okay tbh

Parameters

graphStream

is the stream to be read from

Member Function Documentation

fromFilename()

auto Graph::fromFilename ( const std::string &  filename ) -> Graph

static

constructs graph from data in specified filename

This maayybe should be a constructor somehow? not sure

Parameters

filename

is the filename to stream from if the filename is "-", this will read from stdin

Returns

A new graph

Warning

throws invalid_argument if it couldn't open the file

Here is the caller graph for this function:

getSize()

auto Graph::getSize

(

)

const -> size_t

Returns graph size.

NB: This is NOT necessarily == vertex count nor edge count

Returns

The size of the graph, whichever way we end up defining it

getVertexCount()

auto Graph::getVertexCount ( ) const -> size_t

inline

Return vertex count.

Returns

Number of vertices in the graph.

maxClique()

auto Graph::maxClique

(

AlgorithmAccuracy

accuracy = AlgorithmAccuracy::EXACT

)

const -> std::vector<size_t>

Finds the maximum clique of the graph using Bron-Kerbosch algorithm.

Parameters

accuracy

decides whether to use a simple approximation instead

Returns

Vector of vertices that form the maximum clique.

maxCliqueGraph()

auto Graph::maxCliqueGraph

(

AlgorithmAccuracy

accuracy

)

const -> Graph

Graph of max clique.

Parameters

accuracy

Determines whether to return the approximation or exact solution.

Returns

Vector of vertices that form the maximum clique.

Here is the caller graph for this function:

maxSubgraph()

auto Graph::maxSubgraph	(	const Graph &	rhs,
		AlgorithmAccuracy	accuracy = AlgorithmAccuracy::EXACT
	)		-> Graph

Returns maximum induced subgraph of two graphs.

Parameters

rhs	is the graph with which the maximum induced subgrraph should be applied
accuracy	decides whether to just use a simple approximation instead

Returns

The maximum induced subgraph of the graphs

Here is the call graph for this function:

Here is the caller graph for this function:

metricDistanceTo()

auto Graph::metricDistanceTo	(	const Graph &	rhs,
		AlgorithmAccuracy	accuracy = AlgorithmAccuracy::EXACT
	)		const -> size_t

Returns distance to another graph.

Parameters

rhs	is the second argument of the metric
accuracy	is whether we should approximate the slower parts of the calculation, this parameter is optional

"Distance" in this case is defined by ,
where (for now) is
and checks for isomorphism between graphs and converts the
resulting bool to 0 or 1 respectively

Returns

The distance to the RHS

Here is the caller graph for this function:

modifiedMaxClique()

auto Graph::modifiedMaxClique

(

AlgorithmAccuracy

accuracy = AlgorithmAccuracy::EXACT

)

const -> std::vector<size_t>

modidfied max clique algorithm for finding maximum induced subgraphs.

Parameters

accuracy

decides whether to use a simple approximation instead

Returns

Vector of vertices that form the maximum clique.

Here is the caller graph for this function:

modularProduct()

auto Graph::modularProduct

(

const Graph &

rhs

)

-> Graph

Returns modular product of two graphs.

Parameters

rhs	is the graph with which the modular product should be applied

Returns

The modular product of the graphs

Here is the caller graph for this function:

operator[]()

auto Graph::operator[]

(

size_t

row

)

const -> std::vector<int>

subscript operator, for convenience

Parameters

row	the row number from the adjacency matrix

Returns

the row xd

subGraph()

auto Graph::subGraph

(

std::vector< size_t > &

vertices

)

const -> Graph

Gives the induced subgraph given by the vertices.

Parameters

vertices

of the subgraph.

Returns

Induced subgraph.

toDotLang()

auto Graph::toDotLang

(

)

const -> std::string

returns string in DOT language

Useful for generating visualization and stuff

Returns

dotLang string, just "digraph{[i->j]...}" with no attributes or any of the fancy language features used

See also

DOT language

Here is the caller graph for this function:

Friends And Related Function Documentation

operator<<

auto operator<< ( std::ostream &  outputStream, const Graph &  graph  ) -> std::ostream&

friend

for debugging convenience

Parameters

outputStream	the stream to write to
graph	the graph. (?)

Returns

the outputStream

operator==

auto operator== ( const Graph &  lhs, const Graph &  rhs  ) -> bool

friend

checks isomorphisms between 2 graphs

Parameters

lhs	the lhs of A == B
rhs	the rhs, lol

Returns

true iff the pair is isomorphic

---

The documentation for this class was generated from the following files:

• include/graph.hpp
• lib/graph.cpp