GDAL
Public Member Functions | Protected Member Functions | List of all members
GNMGraph Class Reference

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

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

Add an edge to the graph.

Parameters
nConFIDEdge identificator
nSrcFIDSource vertex identificator
nTgtFIDTarget vertex identificator
bIsBidirIs bidirectional
dfCostCost
dfInvCostInverse cost
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
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
bBlockBlock or unblock
virtual void GNMGraph::ChangeBlockState ( GNMGFID  nFID,
bool  bBlock 
)
virtual

Change the block state of edge or vertex.

Parameters
nFIDIdentificator
bBlockBlock or unblock
virtual void GNMGraph::ChangeEdge ( GNMGFID  nFID,
double  dfCost,
double  dfInvCost 
)
virtual

Change edge properties.

Parameters
nFIDEdge identificator
dfCostCost
dfInvCostInverse cost
virtual bool GNMGraph::CheckVertexBlocked ( GNMGFID  nFID) const
virtual

Check if vertex is blocked.

Parameters
nFIDVertex identificator
Returns
true if blocked, false if not blocked.
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
virtual void GNMGraph::DeleteEdge ( GNMGFID  nConFID)
virtual

Delete edge from graph.

Parameters
nConFIDEdge identificator
virtual void GNMGraph::DeleteVertex ( GNMGFID  nFID)
virtual

Delete vertex from the graph.

Parameters
nFIDVertex identificator
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
nStartFIDStart identificator
nEndFIDEnd identificator
Returns
an array of best path included identificator of vertices and edges
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.
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
nStartFIDVertex identificator from which to start paths calculating.
nEndFIDVertex identificator to which the path will be calculated.
nKHow 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:

Generated for GDAL by doxygen 1.8.8.