Inheritance diagram for Digikam::Graph< VertexProperties, EdgeProperties >:

Classes
class	DominatorTree

class	Edge

class	GraphSearch

class	Path

class	Vertex

Public Types
typedef graph_traits::adjacency_iterator	adjacency_iter

typedef std::pair< adjacency_iter, adjacency_iter >	adjacency_vertex_range_t

enum	AdjacencyFlags { OutboundEdges = 1 << 0 , InboundEdges = 1 << 1 , EdgesToLeaf = 1 << 2 , EdgesToRoot = 1 << 3 , AllEdges = InboundEdges \| OutboundEdges }

typedef boost::property_map< GraphContainer, edge_properties_t >::const_type	const_edge_property_map_t

typedef boost::property_map< GraphContainer, boost::vertex_index_t >::const_type	const_vertex_index_map_t

typedef boost::property_map< GraphContainer, vertex_properties_t >::const_type	const_vertex_property_map_t

typedef graph_traits::degree_size_type	degree_t

typedef graph_traits::edge_iterator	edge_iter

typedef boost::property_map< GraphContainer, edge_properties_t >::type	edge_property_map_t

typedef std::pair< edge_iter, edge_iter >	edge_range_t

typedef graph_traits::edge_descriptor	edge_t

typedef QPair< Edge, Edge >	EdgePair

typedef boost::graph_traits< GraphContainer >	graph_traits

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, boost::property< boost::vertex_index_t, int, boost::property< vertex_properties_t, VertexProperties > >, boost::property< edge_properties_t, EdgeProperties > >	GraphContainer

enum	GraphCopyFlags { CopyVertexProperties = 1 << 0 , CopyEdgeProperties = 1 << 1 , CopyAllProperties = CopyVertexProperties \| CopyEdgeProperties }

typedef graph_traits::in_edge_iterator	in_edge_iter

typedef boost::inv_adjacency_iterator_generator< GraphContainer, vertex_t, in_edge_iter >::type	inv_adjacency_iter

typedef std::pair< inv_adjacency_iter, inv_adjacency_iter >	inv_adjacency_vertex_range_t

typedef graph_traits::out_edge_iterator	out_edge_iter

typedef std::pair< out_edge_iter, out_edge_iter >	out_edge_range_t

enum	ReturnOrder { BreadthFirstOrder , DepthFirstOrder }

typedef boost::property_map< GraphContainer, boost::vertex_index_t >::type	vertex_index_map_t

typedef graph_traits::vertex_iterator	vertex_iter

typedef boost::property_map< GraphContainer, vertex_properties_t >::type	vertex_property_map_t

typedef std::pair< vertex_iter, vertex_iter >	vertex_range_t

typedef graph_traits::vertex_descriptor	vertex_t

typedef QMapForAdaptors< Vertex, int >	VertexIntMap

typedef boost::associative_property_map< VertexIntMap >	VertexIntMapAdaptor

typedef QPair< Vertex, Vertex >	VertexPair

typedef QMapForAdaptors< Vertex, Vertex >	VertexVertexMap

typedef boost::associative_property_map< VertexVertexMap >	VertexVertexMapAdaptor

Public Member Functions
Edge	addEdge (const Vertex &v1, const Vertex &v2)

Vertex	addVertex ()

Vertex	addVertex (const VertexProperties &properties)

QList< Vertex >	adjacentVertices (const Vertex &v, AdjacencyFlags flags=AllEdges) const

void	clear ()

Edge	edge (const Vertex &v1, const Vertex &v2) const

int	edgeCount () const

QList< VertexPair >	edgePairs () const

QList< Edge >	edges () const

QList< Edge >	edges (const Vertex &v, AdjacencyFlags flags=AllEdges) const

template<class T >
Vertex	findVertexByProperties (const T &value) const

const GraphContainer &	getGraph () const

	Graph (const Graph &g)

	Graph (MeaningOfDirection direction=ParentToChild)

bool	hasEdge (const Vertex &v1, const Vertex &v2) const

bool	hasEdges () const

bool	hasEdges (const Vertex &v, AdjacencyFlags flags=AllEdges) const

int	inDegree (const Vertex &v) const

bool	isConnected (const Vertex &v1, const Vertex &v2) const
	Does not care for direction. More...

bool	isEmpty () const

bool	isLeaf (const Vertex &v) const

bool	isRoot (const Vertex &v) const

QList< Vertex >	leaves () const

QList< Vertex >	leavesFrom (const Vertex &v) const

QList< Vertex >	longestPathTouching (const Vertex &v) const

template<typename LessThan >
QList< Vertex >	longestPathTouching (const Vertex &v, LessThan lessThan) const

MeaningOfDirection	meaningOfDirection () const

Graph &	operator= (const Graph &other)

int	outDegree (const Vertex &v) const

EdgeProperties &	properties (const Edge &e)

const EdgeProperties &	properties (const Edge &e) const

VertexProperties &	properties (const Vertex &v)

const VertexProperties &	properties (const Vertex &v) const

EdgeProperties	properties (const Vertex &v1, const Vertex &v2) const

void	remove (const Vertex &v)

QList< Vertex >	roots () const

QList< Vertex >	rootsOf (const Vertex &v) const

void	setProperties (const Edge &e, const EdgeProperties &props)

void	setProperties (const Vertex &v, const VertexProperties &props)

QMap< Vertex, int >	shortestDistancesFrom (const Vertex &v) const

QList< Vertex >	shortestPath (const Vertex &v1, const Vertex &v2) const

Vertex	source (const Edge &e) const

Vertex	target (const Edge &e) const

QList< Vertex >	topologicalSort () const

Graph	transitiveClosure (GraphCopyFlags flags=CopyAllProperties) const

Graph	transitiveReduction (QList< Edge > *removedEdges=0, GraphCopyFlags flags=CopyAllProperties) const

int	vertexCount () const
	NOTE: for "hasAdjacentVertices", simply use hasEdges(v, flags) More...

QList< Vertex >	vertices () const

QList< Vertex >	verticesBreadthFirst (const Vertex &givenRef=Vertex()) const

template<typename LessThan >
QList< Vertex >	verticesDepthFirstSorted (const Vertex &givenRef, LessThan lessThan) const

QList< Vertex >	verticesDominatedBy (const Vertex &v, const Vertex &root, const QList< Vertex > &presortedVertices) const

QList< Vertex >	verticesDominatedBy (const Vertex &v, const Vertex &root, ReturnOrder order=BreadthFirstOrder) const

template<typename LessThan >
QList< Vertex >	verticesDominatedByDepthFirstSorted (const Vertex &v, const Vertex &root, LessThan lessThan) const

virtual	~Graph ()

Static Public Member Functions
template<typename T >
static bool	alwaysFalse (const T &, const T &)

Protected Member Functions
void	copyProperties (Graph &other, GraphCopyFlags flags, const std::vector< vertex_t > &copiedVertices) const

QList< Edge >	edgeDifference (const Graph &other, const std::vector< vertex_t > &copiedVertices) const

QList< Vertex >	findZeroDegree (bool inOrOut) const

QList< Vertex >	findZeroDegreeFrom (const Vertex &v, bool inOrOut) const

QList< Vertex >	listPath (const Vertex &root, const Vertex &target, const VertexVertexMap &predecessors, MeaningOfDirection dir=ParentToChild) const

QList< Vertex >	mostRemoteNodes (const VertexIntMap &distances) const

QList< Vertex >	treeFromPredecessors (const Vertex &v, const VertexVertexMap &predecessors) const

void	treeFromPredecessorsRecursive (const Vertex &v, QList< Vertex > &vertices, const VertexVertexMap &predecessors) const

Static Protected Member Functions
template<typename range_t >
static bool	isEmptyRange (const range_t &range)

template<typename range_t >
static QList< Edge >	toEdgeList (const range_t &range)

template<typename Value , typename range_t >
static QList< Value >	toList (const range_t &range)

template<typename range_t >
static QList< Vertex >	toVertexList (const range_t &range)

Protected Attributes
MeaningOfDirection	direction

GraphContainer	graph

Detailed Description

template<class VertexProperties, class EdgeProperties>
class Digikam::Graph< VertexProperties, EdgeProperties >

The graph base class template

Member Typedef Documentation

◆ adjacency_iter

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::adjacency_iterator Digikam::Graph< VertexProperties, EdgeProperties >::adjacency_iter

◆ adjacency_vertex_range_t

template<class VertexProperties , class EdgeProperties >

typedef std::pair<adjacency_iter, adjacency_iter> Digikam::Graph< VertexProperties, EdgeProperties >::adjacency_vertex_range_t

◆ const_edge_property_map_t

template<class VertexProperties , class EdgeProperties >

typedef boost::property_map<GraphContainer, edge_properties_t>::const_type Digikam::Graph< VertexProperties, EdgeProperties >::const_edge_property_map_t

◆ const_vertex_index_map_t

template<class VertexProperties , class EdgeProperties >

typedef boost::property_map<GraphContainer, boost::vertex_index_t>::const_type Digikam::Graph< VertexProperties, EdgeProperties >::const_vertex_index_map_t

◆ const_vertex_property_map_t

template<class VertexProperties , class EdgeProperties >

typedef boost::property_map<GraphContainer, vertex_properties_t>::const_type Digikam::Graph< VertexProperties, EdgeProperties >::const_vertex_property_map_t

◆ degree_t

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::degree_size_type Digikam::Graph< VertexProperties, EdgeProperties >::degree_t

◆ edge_iter

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::edge_iterator Digikam::Graph< VertexProperties, EdgeProperties >::edge_iter

◆ edge_property_map_t

template<class VertexProperties , class EdgeProperties >

typedef boost::property_map<GraphContainer, edge_properties_t>::type Digikam::Graph< VertexProperties, EdgeProperties >::edge_property_map_t

◆ edge_range_t

template<class VertexProperties , class EdgeProperties >

typedef std::pair<edge_iter, edge_iter> Digikam::Graph< VertexProperties, EdgeProperties >::edge_range_t

◆ edge_t

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::edge_descriptor Digikam::Graph< VertexProperties, EdgeProperties >::edge_t

◆ EdgePair

template<class VertexProperties , class EdgeProperties >

typedef QPair<Edge, Edge> Digikam::Graph< VertexProperties, EdgeProperties >::EdgePair

◆ graph_traits

template<class VertexProperties , class EdgeProperties >

typedef boost::graph_traits<GraphContainer> Digikam::Graph< VertexProperties, EdgeProperties >::graph_traits

a bunch of graph-specific typedefs that make the long boost types manageable

◆ GraphContainer

template<class VertexProperties , class EdgeProperties >

typedef boost::adjacency_list< boost::vecS, boost::vecS, boost::bidirectionalS, boost::property<boost::vertex_index_t, int, boost::property<vertex_properties_t, VertexProperties> >, boost::property<edge_properties_t, EdgeProperties> > Digikam::Graph< VertexProperties, EdgeProperties >::GraphContainer

◆ in_edge_iter

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::in_edge_iterator Digikam::Graph< VertexProperties, EdgeProperties >::in_edge_iter

◆ inv_adjacency_iter

template<class VertexProperties , class EdgeProperties >

typedef boost::inv_adjacency_iterator_generator<GraphContainer, vertex_t, in_edge_iter>::type Digikam::Graph< VertexProperties, EdgeProperties >::inv_adjacency_iter

◆ inv_adjacency_vertex_range_t

template<class VertexProperties , class EdgeProperties >

typedef std::pair<inv_adjacency_iter, inv_adjacency_iter> Digikam::Graph< VertexProperties, EdgeProperties >::inv_adjacency_vertex_range_t

◆ out_edge_iter

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::out_edge_iterator Digikam::Graph< VertexProperties, EdgeProperties >::out_edge_iter

◆ out_edge_range_t

template<class VertexProperties , class EdgeProperties >

typedef std::pair<out_edge_iter, out_edge_iter> Digikam::Graph< VertexProperties, EdgeProperties >::out_edge_range_t

◆ vertex_index_map_t

template<class VertexProperties , class EdgeProperties >

typedef boost::property_map<GraphContainer, boost::vertex_index_t>::type Digikam::Graph< VertexProperties, EdgeProperties >::vertex_index_map_t

◆ vertex_iter

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::vertex_iterator Digikam::Graph< VertexProperties, EdgeProperties >::vertex_iter

◆ vertex_property_map_t

template<class VertexProperties , class EdgeProperties >

typedef boost::property_map<GraphContainer, vertex_properties_t>::type Digikam::Graph< VertexProperties, EdgeProperties >::vertex_property_map_t

◆ vertex_range_t

template<class VertexProperties , class EdgeProperties >

typedef std::pair<vertex_iter, vertex_iter> Digikam::Graph< VertexProperties, EdgeProperties >::vertex_range_t

◆ vertex_t

template<class VertexProperties , class EdgeProperties >

typedef graph_traits::vertex_descriptor Digikam::Graph< VertexProperties, EdgeProperties >::vertex_t

◆ VertexIntMap

template<class VertexProperties , class EdgeProperties >

typedef QMapForAdaptors<Vertex, int> Digikam::Graph< VertexProperties, EdgeProperties >::VertexIntMap

◆ VertexIntMapAdaptor

template<class VertexProperties , class EdgeProperties >

typedef boost::associative_property_map<VertexIntMap> Digikam::Graph< VertexProperties, EdgeProperties >::VertexIntMapAdaptor

◆ VertexPair

template<class VertexProperties , class EdgeProperties >

typedef QPair<Vertex, Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::VertexPair

◆ VertexVertexMap

template<class VertexProperties , class EdgeProperties >

typedef QMapForAdaptors<Vertex, Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::VertexVertexMap

◆ VertexVertexMapAdaptor

template<class VertexProperties , class EdgeProperties >

typedef boost::associative_property_map<VertexVertexMap> Digikam::Graph< VertexProperties, EdgeProperties >::VertexVertexMapAdaptor

Member Enumeration Documentation

◆ AdjacencyFlags

template<class VertexProperties , class EdgeProperties >

enum Digikam::Graph::AdjacencyFlags

Enumerator
OutboundEdges
InboundEdges
EdgesToLeaf	These resolve to one of the flags above, depending on MeaningOfDirection.
EdgesToRoot
AllEdges

◆ GraphCopyFlags

template<class VertexProperties , class EdgeProperties >

enum Digikam::Graph::GraphCopyFlags

Enumerator
CopyVertexProperties
CopyEdgeProperties
CopyAllProperties

◆ ReturnOrder

template<class VertexProperties , class EdgeProperties >

enum Digikam::Graph::ReturnOrder

Enumerator
BreadthFirstOrder
DepthFirstOrder

Constructor & Destructor Documentation

◆ Graph() [1/2]

template<class VertexProperties , class EdgeProperties >

Digikam::Graph< VertexProperties, EdgeProperties >::Graph ( MeaningOfDirection direction = ParentToChild )

inlineexplicit

◆ Graph() [2/2]

template<class VertexProperties , class EdgeProperties >

Digikam::Graph< VertexProperties, EdgeProperties >::Graph ( const Graph< VertexProperties, EdgeProperties > & g )

inline

◆ ~Graph()

template<class VertexProperties , class EdgeProperties >

virtual Digikam::Graph< VertexProperties, EdgeProperties >::~Graph ( )

inlinevirtual

Member Function Documentation

◆ addEdge()

template<class VertexProperties , class EdgeProperties >

Edge Digikam::Graph< VertexProperties, EdgeProperties >::addEdge	(	const Vertex &	v1,
		const Vertex &	v2
	)

inline

References Digikam::Graph< VertexProperties, EdgeProperties >::Edge::isNull().

Referenced by Digikam::ItemHistoryGraphData::addHistory(), and Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ addVertex() [1/2]

template<class VertexProperties , class EdgeProperties >

Vertex Digikam::Graph< VertexProperties, EdgeProperties >::addVertex ( )

inline

Referenced by Digikam::ItemHistoryGraphData::addHistory(), Digikam::ItemHistoryGraphData::addVertex(), and Digikam::ItemHistoryGraphData::applyProperties().

◆ addVertex() [2/2]

template<class VertexProperties , class EdgeProperties >

Vertex Digikam::Graph< VertexProperties, EdgeProperties >::addVertex ( const VertexProperties & properties )

inline

◆ adjacentVertices()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::adjacentVertices	(	const Vertex &	v,
		AdjacencyFlags	flags = `AllEdges`
	)		const

inline

References Digikam::ParentToChild.

Referenced by Digikam::operator<<().

◆ alwaysFalse()

template<class VertexProperties , class EdgeProperties >

template<typename T >

static bool Digikam::Graph< VertexProperties, EdgeProperties >::alwaysFalse	(	const T &	,
		const T &
	)

inlinestatic

◆ clear()

template<class VertexProperties , class EdgeProperties >

void Digikam::Graph< VertexProperties, EdgeProperties >::clear ( )

inline

◆ copyProperties()

template<class VertexProperties , class EdgeProperties >

void Digikam::Graph< VertexProperties, EdgeProperties >::copyProperties	(	Graph< VertexProperties, EdgeProperties > &	other,
		GraphCopyFlags	flags,
		const std::vector< vertex_t > &	copiedVertices
	)		const

inlineprotected

According to the given flags and based on the map, copies vertex and edge properties from this to the other graph

References Digikam::Graph< VertexProperties, EdgeProperties >::direction, Digikam::Graph< VertexProperties, EdgeProperties >::edge(), Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), Digikam::Graph< VertexProperties, EdgeProperties >::Edge::isNull(), and Digikam::Graph< VertexProperties, EdgeProperties >::setProperties().

◆ edge()

template<class VertexProperties , class EdgeProperties >

Edge Digikam::Graph< VertexProperties, EdgeProperties >::edge	(	const Vertex &	v1,
		const Vertex &	v2
	)		const

inline

Referenced by Digikam::Graph< VertexProperties, EdgeProperties >::copyProperties(), and Digikam::Graph< VertexProperties, EdgeProperties >::edgeDifference().

◆ edgeCount()

template<class VertexProperties , class EdgeProperties >

int Digikam::Graph< VertexProperties, EdgeProperties >::edgeCount ( ) const

inline

◆ edgeDifference()

template<class VertexProperties , class EdgeProperties >

QList<Edge> Digikam::Graph< VertexProperties, EdgeProperties >::edgeDifference	(	const Graph< VertexProperties, EdgeProperties > &	other,
		const std::vector< vertex_t > &	copiedVertices
	)		const

inlineprotected

Returns a list of edges of this graph that have been removed in other. copiedVertices maps the vertices of this graph to other.

References Digikam::Graph< VertexProperties, EdgeProperties >::edge(), Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), and Digikam::Graph< VertexProperties, EdgeProperties >::Edge::isNull().

◆ edgePairs()

template<class VertexProperties , class EdgeProperties >

QList<VertexPair> Digikam::Graph< VertexProperties, EdgeProperties >::edgePairs ( ) const

inline

Referenced by Digikam::ItemHistoryGraph::relationCloud(), and Digikam::ItemHistoryGraph::relationCloudParallel().

◆ edges() [1/2]

template<class VertexProperties , class EdgeProperties >

QList<Edge> Digikam::Graph< VertexProperties, EdgeProperties >::edges ( ) const

inline

Referenced by Digikam::ItemHistoryGraphData::categorize(), and Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ edges() [2/2]

template<class VertexProperties , class EdgeProperties >

QList<Edge> Digikam::Graph< VertexProperties, EdgeProperties >::edges	(	const Vertex &	v,
		AdjacencyFlags	flags = `AllEdges`
	)		const

inline

References Digikam::ParentToChild.

◆ findVertexByProperties()

template<class VertexProperties , class EdgeProperties >

template<class T >

Vertex Digikam::Graph< VertexProperties, EdgeProperties >::findVertexByProperties ( const T & value ) const

inline

References value.

Referenced by Digikam::ItemHistoryGraphData::addVertex(), and Digikam::ItemHistoryGraphData::addVertexScanned().

◆ findZeroDegree()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::findZeroDegree ( bool inOrOut ) const

inlineprotected

Finds vertex ids of all vertices with zero in- our out-degree.

◆ findZeroDegreeFrom()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::findZeroDegreeFrom	(	const Vertex &	v,
		bool	inOrOut
	)		const

inlineprotected

References Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::breadthFirstSearch(), Digikam::ChildToParent, and Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::vertices.

◆ getGraph()

template<class VertexProperties , class EdgeProperties >

const GraphContainer& Digikam::Graph< VertexProperties, EdgeProperties >::getGraph ( ) const

inline

Accessing vertices and edges

◆ hasEdge()

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::hasEdge	(	const Vertex &	v1,
		const Vertex &	v2
	)		const

inline

◆ hasEdges() [1/2]

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::hasEdges ( ) const

inline

Referenced by Digikam::ItemHistoryGraphData::categorize().

◆ hasEdges() [2/2]

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::hasEdges	(	const Vertex &	v,
		AdjacencyFlags	flags = `AllEdges`
	)		const

inline

References Digikam::ParentToChild.

◆ inDegree()

template<class VertexProperties , class EdgeProperties >

int Digikam::Graph< VertexProperties, EdgeProperties >::inDegree ( const Vertex & v ) const

inline

◆ isConnected()

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::isConnected	(	const Vertex &	v1,
		const Vertex &	v2
	)		const

inline

Does not care for direction.

◆ isEmpty()

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::isEmpty ( ) const

inline

Referenced by Digikam::operator<<(), and Digikam::ItemHistoryGraph::reduceEdges().

◆ isEmptyRange()

template<class VertexProperties , class EdgeProperties >

template<typename range_t >

static bool Digikam::Graph< VertexProperties, EdgeProperties >::isEmptyRange ( const range_t & range )

inlinestaticprotected

◆ isLeaf()

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::isLeaf ( const Vertex & v ) const

inline

Referenced by Digikam::ItemHistoryGraphData::categorize().

◆ isRoot()

template<class VertexProperties , class EdgeProperties >

bool Digikam::Graph< VertexProperties, EdgeProperties >::isRoot ( const Vertex & v ) const

inline

Referenced by Digikam::ItemHistoryGraphData::categorize().

◆ leaves()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::leaves ( ) const

inline

Returns all leaves, i.e. vertices with no children Takes the graph direction into account.

References Digikam::ParentToChild.

◆ leavesFrom()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::leavesFrom ( const Vertex & v ) const

inline

References Digikam::ParentToChild.

◆ listPath()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::listPath	(	const Vertex &	root,
		const Vertex &	target,
		const VertexVertexMap &	predecessors,
		MeaningOfDirection	dir = `ParentToChild`
	)		const

inlineprotected

Get a list of vertex ids for the path from root to target, using the given predecessors. Depending on MeaningOfDirection, the ids are listed inverted, from target to root.

References Digikam::ParentToChild.

◆ longestPathTouching() [1/2]

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::longestPathTouching ( const Vertex & v ) const

inline

Returns the longest path through the graph, starting from a vertex in roots(), ending on a vertex in leaves(), and passing vertex v. The returned list is given in that order, root - v - leave. If there is more than one candidate for root or leave, lessThan is used to determine the first candidate.

◆ longestPathTouching() [2/2]

template<class VertexProperties , class EdgeProperties >

template<typename LessThan >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::longestPathTouching	(	const Vertex &	v,
		LessThan	lessThan
	)		const

inline

References Digikam::ChildToParent, Digikam::Graph< VertexProperties, EdgeProperties >::Path::distances, Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), Digikam::Graph< VertexProperties, EdgeProperties >::Path::longestPath(), Digikam::ParentToChild, and Digikam::Graph< VertexProperties, EdgeProperties >::Path::predecessors.

◆ meaningOfDirection()

template<class VertexProperties , class EdgeProperties >

MeaningOfDirection Digikam::Graph< VertexProperties, EdgeProperties >::meaningOfDirection ( ) const

inline

◆ mostRemoteNodes()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::mostRemoteNodes ( const VertexIntMap & distances ) const

inlineprotected

Get the list of vertices with the largest value in the given distance map

◆ operator=()

template<class VertexProperties , class EdgeProperties >

Graph& Digikam::Graph< VertexProperties, EdgeProperties >::operator= ( const Graph< VertexProperties, EdgeProperties > & other )

inline

References Digikam::Graph< VertexProperties, EdgeProperties >::direction, and Digikam::Graph< VertexProperties, EdgeProperties >::graph.

Referenced by Digikam::ItemHistoryGraphData::operator=().

◆ outDegree()

template<class VertexProperties , class EdgeProperties >

int Digikam::Graph< VertexProperties, EdgeProperties >::outDegree ( const Vertex & v ) const

inline

Referenced by Digikam::operator<<().

◆ properties() [1/5]

template<class VertexProperties , class EdgeProperties >

EdgeProperties& Digikam::Graph< VertexProperties, EdgeProperties >::properties ( const Edge & e )

inline

References edge_properties.

◆ properties() [2/5]

template<class VertexProperties , class EdgeProperties >

const EdgeProperties& Digikam::Graph< VertexProperties, EdgeProperties >::properties ( const Edge & e ) const

inline

References edge_properties.

◆ properties() [3/5]

template<class VertexProperties , class EdgeProperties >

VertexProperties& Digikam::Graph< VertexProperties, EdgeProperties >::properties ( const Vertex & v )

inline

References vertex_properties.

◆ properties() [4/5]

template<class VertexProperties , class EdgeProperties >

const VertexProperties& Digikam::Graph< VertexProperties, EdgeProperties >::properties ( const Vertex & v ) const

inline

References vertex_properties.

Referenced by Digikam::ItemHistoryGraphData::applyProperties(), Digikam::ItemHistoryGraphData::categorize(), Digikam::operator<<(), Digikam::ItemHistoryGraph::relationCloud(), Digikam::ItemHistoryGraph::relationCloudParallel(), and Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ properties() [5/5]

template<class VertexProperties , class EdgeProperties >

EdgeProperties Digikam::Graph< VertexProperties, EdgeProperties >::properties	(	const Vertex &	v1,
		const Vertex &	v2
	)		const

inline

References Digikam::Graph< VertexProperties, EdgeProperties >::Edge::isNull().

◆ remove()

template<class VertexProperties , class EdgeProperties >

void Digikam::Graph< VertexProperties, EdgeProperties >::remove ( const Vertex & v )

inline

References Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull().

Referenced by Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ roots()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::roots ( ) const

inline

Returns all roots, i.e. vertices with no parents. Takes the graph direction into account.

References Digikam::ParentToChild.

◆ rootsOf()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::rootsOf ( const Vertex & v ) const

inline

Returns all roots of vertex v. Subset of roots(). I case any leaves have roots that are not roots of v, they will not be contained in this list.

References Digikam::ParentToChild.

◆ setProperties() [1/2]

template<class VertexProperties , class EdgeProperties >

void Digikam::Graph< VertexProperties, EdgeProperties >::setProperties	(	const Edge &	e,
		const EdgeProperties &	props
	)

inline

References edge_properties.

◆ setProperties() [2/2]

template<class VertexProperties , class EdgeProperties >

void Digikam::Graph< VertexProperties, EdgeProperties >::setProperties	(	const Vertex &	v,
		const VertexProperties &	props
	)

inline

References vertex_properties.

Referenced by Digikam::ItemHistoryGraphData::addHistory(), Digikam::Graph< VertexProperties, EdgeProperties >::copyProperties(), and Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ shortestDistancesFrom()

template<class VertexProperties , class EdgeProperties >

QMap<Vertex, int> Digikam::Graph< VertexProperties, EdgeProperties >::shortestDistancesFrom ( const Vertex & v ) const

inline

Returns the shortest distances from Vertex to all vertices in the graph. If the value is -1, a vertex is not reachable from v.

References Digikam::Graph< VertexProperties, EdgeProperties >::Path::distances, Digikam::ParentToChild, and Digikam::Graph< VertexProperties, EdgeProperties >::Path::shortestPath().

◆ shortestPath()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::shortestPath	(	const Vertex &	v1,
		const Vertex &	v2
	)		const

inline

Returns the shortestPath between id1 and id2. If s2 is not reachable from s1, the path is searched from s2 to s1. The returned list always starts with s1, contains the intermediate vertices, and ends with s2. If no path is available, an empty list is returned.

References Digikam::ChildToParent, Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), Digikam::Graph< VertexProperties, EdgeProperties >::Path::isReachable(), Digikam::Graph< VertexProperties, EdgeProperties >::Path::predecessors, and Digikam::Graph< VertexProperties, EdgeProperties >::Path::shortestPath().

◆ source()

template<class VertexProperties , class EdgeProperties >

Vertex Digikam::Graph< VertexProperties, EdgeProperties >::source ( const Edge & e ) const

inline

References Digikam::Graph< VertexProperties, EdgeProperties >::Edge::toEdge().

Referenced by Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ target()

template<class VertexProperties , class EdgeProperties >

Vertex Digikam::Graph< VertexProperties, EdgeProperties >::target ( const Edge & e ) const

inline

References Digikam::Graph< VertexProperties, EdgeProperties >::Edge::toEdge().

Referenced by Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ toEdgeList()

template<class VertexProperties , class EdgeProperties >

template<typename range_t >

static QList<Edge> Digikam::Graph< VertexProperties, EdgeProperties >::toEdgeList ( const range_t & range )

inlinestaticprotected

◆ toList()

template<class VertexProperties , class EdgeProperties >

template<typename Value , typename range_t >

static QList<Value> Digikam::Graph< VertexProperties, EdgeProperties >::toList ( const range_t & range )

inlinestaticprotected

Returns a list of vertex ids of vertices in the given range

◆ topologicalSort()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::topologicalSort ( ) const

inline

Returns the vertex ids of this graph, in topological order.

Referenced by Digikam::operator<<().

◆ toVertexList()

template<class VertexProperties , class EdgeProperties >

template<typename range_t >

static QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::toVertexList ( const range_t & range )

inlinestaticprotected

◆ transitiveClosure()

template<class VertexProperties , class EdgeProperties >

Graph Digikam::Graph< VertexProperties, EdgeProperties >::transitiveClosure ( GraphCopyFlags flags = CopyAllProperties ) const

inline

Returns a copy of this graph with all edges added to form the transitive closure

References Digikam::Graph< VertexProperties, EdgeProperties >::graph.

◆ transitiveReduction()

template<class VertexProperties , class EdgeProperties >

Graph Digikam::Graph< VertexProperties, EdgeProperties >::transitiveReduction	(	QList< Edge > *	removedEdges = `0`,
		GraphCopyFlags	flags = `CopyAllProperties`
	)		const

inline

Returns a copy of this graph, with edges removed so that the transitive reduction is formed. Optionally, a list of edges of this graph that have been removed in the returned graph is given.

References Digikam::Graph< VertexProperties, EdgeProperties >::graph.

◆ treeFromPredecessors()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::treeFromPredecessors	(	const Vertex &	v,
		const VertexVertexMap &	predecessors
	)		const

inlineprotected

◆ treeFromPredecessorsRecursive()

template<class VertexProperties , class EdgeProperties >

void Digikam::Graph< VertexProperties, EdgeProperties >::treeFromPredecessorsRecursive	(	const Vertex &	v,
		QList< Vertex > &	vertices,
		const VertexVertexMap &	predecessors
	)		const

inlineprotected

◆ vertexCount()

template<class VertexProperties , class EdgeProperties >

int Digikam::Graph< VertexProperties, EdgeProperties >::vertexCount ( ) const

inline

NOTE: for "hasAdjacentVertices", simply use hasEdges(v, flags)

◆ vertices()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::vertices ( ) const

inline

Referenced by Digikam::ItemHistoryGraphData::categorize(), Digikam::operator<<(), and Digikam::ItemHistoryGraphData::removeNextUnresolvedVertex().

◆ verticesBreadthFirst()

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::verticesBreadthFirst ( const Vertex & givenRef = Vertex() ) const

inline

Orders all vertices of the graph in a breadth-first manner. A single vertex is taken as reference to distinguish main root and side paths. Otherwise the first root is taken as reference.

References Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::breadthFirstSearch(), Digikam::ChildToParent, Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), and Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::vertices.

◆ verticesDepthFirstSorted()

template<class VertexProperties , class EdgeProperties >

template<typename LessThan >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::verticesDepthFirstSorted	(	const Vertex &	givenRef,
		LessThan	lessThan
	)		const

inline

Orders all vertices of the graph in a depth-first manner. When discovering a vertex, the adjacent vertices are sorted with the given lessThan. A single vertex is taken as starting point. If null, the first root is taken as reference.

References Digikam::ChildToParent, Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::depthFirstSearchSorted(), Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), and Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::vertices.

◆ verticesDominatedBy() [1/2]

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::verticesDominatedBy	(	const Vertex &	v,
		const Vertex &	root,
		const QList< Vertex > &	presortedVertices
	)		const

inline

For a vertex v reachable from a vertex root returns all vertices dominated by v starting from root. The order is the same as in the given, sorted list of all vertices in this graph (or all vertices expected to be returned. The returned list is the intersection of the dominated vertices and presortedVertices, in order of presortedVertices)

remove all vertices from the DFS of v that are not in the dominated tree

References Digikam::Graph< VertexProperties, EdgeProperties >::DominatorTree::enter(), Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), and Digikam::Graph< VertexProperties, EdgeProperties >::DominatorTree::predecessors.

◆ verticesDominatedBy() [2/2]

template<class VertexProperties , class EdgeProperties >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::verticesDominatedBy	(	const Vertex &	v,
		const Vertex &	root,
		ReturnOrder	order = `BreadthFirstOrder`
	)		const

inline

For a vertex v reachable from a vertex root, returns, in depth-first or breadth-first order, all vertices dominated by v starting from root.

References Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::breadthFirstSearch(), Digikam::ChildToParent, Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::depthFirstSearch(), Digikam::Graph< VertexProperties, EdgeProperties >::Vertex::isNull(), and Digikam::Graph< VertexProperties, EdgeProperties >::GraphSearch::vertices.

◆ verticesDominatedByDepthFirstSorted()

template<class VertexProperties , class EdgeProperties >

template<typename LessThan >

QList<Vertex> Digikam::Graph< VertexProperties, EdgeProperties >::verticesDominatedByDepthFirstSorted	(	const Vertex &	v,
		const Vertex &	root,
		LessThan	lessThan
	)		const

inline

For a vertex v reachable from a vertex root all vertices dominated by v starting from root. The returned list is in depth-first order, using root as starting point, and when discovering a vertex, sorting the adjacent vertices with the given lessThan.

Member Data Documentation

◆ direction

template<class VertexProperties , class EdgeProperties >

MeaningOfDirection Digikam::Graph< VertexProperties, EdgeProperties >::direction

protected

Referenced by Digikam::Graph< VertexProperties, EdgeProperties >::copyProperties(), and Digikam::Graph< VertexProperties, EdgeProperties >::operator=().

◆ graph

template<class VertexProperties , class EdgeProperties >

GraphContainer Digikam::Graph< VertexProperties, EdgeProperties >::graph

protected

Referenced by Digikam::Graph< VertexProperties, EdgeProperties >::operator=(), Digikam::Graph< VertexProperties, EdgeProperties >::transitiveClosure(), and Digikam::Graph< VertexProperties, EdgeProperties >::transitiveReduction().

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

core/libs/database/history/itemhistorygraph_boost.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

template<class VertexProperties, class EdgeProperties> class Digikam::Graph< VertexProperties, EdgeProperties >

Member Typedef Documentation

◆ adjacency_iter

◆ adjacency_vertex_range_t

◆ const_edge_property_map_t

◆ const_vertex_index_map_t

◆ const_vertex_property_map_t

◆ degree_t

◆ edge_iter

◆ edge_property_map_t

◆ edge_range_t

◆ edge_t

◆ EdgePair

◆ graph_traits

◆ GraphContainer

◆ in_edge_iter

◆ inv_adjacency_iter

◆ inv_adjacency_vertex_range_t

◆ out_edge_iter

◆ out_edge_range_t

◆ vertex_index_map_t

◆ vertex_iter

◆ vertex_property_map_t

◆ vertex_range_t

◆ vertex_t

◆ VertexIntMap

◆ VertexIntMapAdaptor

◆ VertexPair

◆ VertexVertexMap

◆ VertexVertexMapAdaptor

Member Enumeration Documentation

◆ AdjacencyFlags

◆ GraphCopyFlags

◆ ReturnOrder

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

◆ ~Graph()

Member Function Documentation

◆ addEdge()

◆ addVertex() [1/2]

◆ addVertex() [2/2]

◆ adjacentVertices()

◆ alwaysFalse()

◆ clear()

◆ copyProperties()

◆ edge()

◆ edgeCount()

◆ edgeDifference()

◆ edgePairs()

◆ edges() [1/2]

◆ edges() [2/2]

◆ findVertexByProperties()

◆ findZeroDegree()

◆ findZeroDegreeFrom()

◆ getGraph()

◆ hasEdge()

◆ hasEdges() [1/2]

◆ hasEdges() [2/2]

◆ inDegree()

◆ isConnected()

◆ isEmpty()

◆ isEmptyRange()

◆ isLeaf()

◆ isRoot()

◆ leaves()

◆ leavesFrom()

◆ listPath()

◆ longestPathTouching() [1/2]

◆ longestPathTouching() [2/2]

◆ meaningOfDirection()

◆ mostRemoteNodes()

template<class VertexProperties, class EdgeProperties>
class Digikam::Graph< VertexProperties, EdgeProperties >