The simple graph class, which holds the appropriate for calculations graph in memory (based on STL containers) and provides several basic algorithms of this graph's analysis. More...

#include <gnmgraph.h>

Public Member Functions
virtual void	AddVertex (GNMGFID nFID)
	Add a vertex to the graph. More...

virtual void	DeleteVertex (GNMGFID nFID)
	Delete vertex from the graph. More...

virtual void	AddEdge (GNMGFID nConFID, GNMGFID nSrcFID, GNMGFID nTgtFID, bool bIsBidir, double dfCost, double dfInvCost)
	Add an edge to the graph. More...

virtual void	DeleteEdge (GNMGFID nConFID)
	Delete edge from graph. More...

virtual void	ChangeEdge (GNMGFID nFID, double dfCost, double dfInvCost)
	Change edge properties. More...

virtual void	ChangeBlockState (GNMGFID nFID, bool bBlock)
	Change the block state of edge or vertex. More...

virtual bool	CheckVertexBlocked (GNMGFID nFID) const
	Check if vertex is blocked. More...

virtual void	ChangeAllBlockState (bool bBlock=false)
	Change all vertices and edges block state. More...

virtual GNMPATH	DijkstraShortestPath (GNMGFID nStartFID, GNMGFID nEndFID)
	An implementation of Dijkstra shortest path algorithm. More...

virtual std::vector< GNMPATH >	KShortestPaths (GNMGFID nStartFID, GNMGFID nEndFID, size_t nK)
	An implementation of KShortest paths algorithm. More...

virtual GNMPATH	ConnectedComponents (const GNMVECTOR &anEmittersIDs)
	Search connected components of the network. More...

virtual void	Clear ()
	Clear.

Protected Member Functions
virtual void	DijkstraShortestPathTree (GNMGFID nFID, const std::map< GNMGFID, GNMStdEdge > &mstEdges, std::map< GNMGFID, GNMGFID > &mnPathTree)
	Method to create best path tree. More...

virtual GNMPATH	DijkstraShortestPath (GNMGFID nStartFID, GNMGFID nEndFID, const std::map< GNMGFID, GNMStdEdge > &mstEdges)
	DijkstraShortestPath.

Detailed Description

The simple graph class, which holds the appropriate for calculations graph in memory (based on STL containers) and provides several basic algorithms of this graph's analysis.

See the methods of this class for details. The common thing for all analysis methods is that all of them return the results in the array of GFIDs form. Use the GNMGraph class to receive the results in OGRLayer form. NOTE: GNMGraph holds the whole graph in memory, so it can consume a lot of memory if operating huge networks.

Since: GDAL 2.1

Member Function Documentation

◆ AddEdge()

virtual void GNMGraph::AddEdge	(	GNMGFID	nConFID,
		GNMGFID	nSrcFID,
		GNMGFID	nTgtFID,
		bool	bIsBidir,
		double	dfCost,
		double	dfInvCost
	)

virtual

Add an edge to the graph.

Parameters

nConFID	Edge identificator
nSrcFID	Source vertex identificator
nTgtFID	Target vertex identificator
bIsBidir	Is bidirectional
dfCost	Cost
dfInvCost	Inverse cost

◆ AddVertex()

virtual void GNMGraph::AddVertex ( GNMGFID nFID )

virtual

Add a vertex to the graph.

NOTE: if there are vertices with these ID's already - nothing will be added.

Parameters

nFID	- vertex identificator

◆ ChangeAllBlockState()

virtual void GNMGraph::ChangeAllBlockState ( bool bBlock = false )

virtual

Change all vertices and edges block state.

This is mainly use for unblock all vertices and edges.

Parameters

bBlock Block or unblock

◆ ChangeBlockState()

virtual void GNMGraph::ChangeBlockState	(	GNMGFID	nFID,
		bool	bBlock
	)

virtual

Change the block state of edge or vertex.

Parameters

nFID	Identificator
bBlock	Block or unblock

◆ ChangeEdge()

virtual void GNMGraph::ChangeEdge	(	GNMGFID	nFID,
		double	dfCost,
		double	dfInvCost
	)

virtual

Change edge properties.

Parameters

nFID	Edge identificator
dfCost	Cost
dfInvCost	Inverse cost

◆ CheckVertexBlocked()

virtual bool GNMGraph::CheckVertexBlocked ( GNMGFID nFID ) const

virtual

Check if vertex is blocked.

Parameters

nFID	Vertex identificator

Returns: true if blocked, false if not blocked.

◆ ConnectedComponents()

virtual GNMPATH GNMGraph::ConnectedComponents ( const GNMVECTOR & anEmittersIDs )

virtual

Search connected components of the network.

Returns the resource distribution in the network. Method search starting from the features identificators from input array. Uses the recursive Breadth-first search algorithm to find the connected to the given vector of GFIDs components. Method takes in account the blocking state of features, i.e. the blocked features are the barriers during the routing process.

Parameters

anEmittersIDs - array of emitters identificators

Returns: an array of connected identificators

◆ DeleteEdge()

virtual void GNMGraph::DeleteEdge ( GNMGFID nConFID )

virtual

Delete edge from graph.

Parameters

nConFID Edge identificator

◆ DeleteVertex()

virtual void GNMGraph::DeleteVertex ( GNMGFID nFID )

virtual

Delete vertex from the graph.

Parameters

nFID	Vertex identificator

◆ DijkstraShortestPath()

virtual GNMPATH GNMGraph::DijkstraShortestPath	(	GNMGFID	nStartFID,
		GNMGFID	nEndFID
	)

virtual

An implementation of Dijkstra shortest path algorithm.

Returns the best path between nStartFID and nEndFID features. Method uses

See also: DijkstraShortestPathTree and after that searches in the resulting tree the path from end to start point.

Parameters

nStartFID	Start identificator
nEndFID	End identificator

Returns: an array of best path included identificator of vertices and edges

◆ DijkstraShortestPathTree()

virtual void GNMGraph::DijkstraShortestPathTree	(	GNMGFID	nFID,
		const std::map< GNMGFID, GNMStdEdge > &	mstEdges,
		std::map< GNMGFID, GNMGFID > &	mnPathTree
	)

protectedvirtual

Method to create best path tree.

Calculates and builds the best path tree with the Dijkstra algorithm starting from the nFID. Method takes in account the blocking state of features, i.e. the blocked features are the barriers during the routing process.

Parameters

nFID	- Vertex identificator from which to start tree building
mstEdges	- TODO
mnPathTree	- means < vertex id, edge id >. std::map where the first is vertex identificator and the second is the edge identificator, which is the best way to the current vertex. The identificator to the start vertex is -1. If the vertex is isolated the returned map will be empty.

◆ KShortestPaths()

virtual std::vector<GNMPATH> GNMGraph::KShortestPaths	(	GNMGFID	nStartFID,
		GNMGFID	nEndFID,
		size_t	nK
	)

virtual

An implementation of KShortest paths algorithm.

Calculates several best paths between two points. Method takes in account the blocking state of features, i.e. the blocked features are the barriers during the routing process.

Parameters

nStartFID	Vertex identificator from which to start paths calculating.
nEndFID	Vertex identificator to which the path will be calculated.
nK	How much best paths try to find between start and end points.

Returns: an array of best paths. Each path is an array of pairs, where the first in a pair is a vertex identificator and the second is an edge identificator leading to this vertex. The elements in a path array are sorted by the path segments order, i.e. the first is the pair (nStartFID, -1) and the last is (nEndFID, <some edge>). If there is no any path between start and end vertex the returned array of paths will be empty. Also the actual amount of paths in the returned array can be less or equal than the nK parameter.

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

gnmgraph.h

Public Member Functions

Protected Member Functions

Detailed Description

Member Function Documentation

◆ AddEdge()

◆ AddVertex()

◆ ChangeAllBlockState()

◆ ChangeBlockState()

◆ ChangeEdge()

◆ CheckVertexBlocked()

◆ ConnectedComponents()

◆ DeleteEdge()

◆ DeleteVertex()

◆ DijkstraShortestPath()

◆ DijkstraShortestPathTree()

◆ KShortestPaths()