GDAL

- Main Page
- Related Pages
- Classes
- Files

- Class List
- Class Hierarchy
- Class Members

Public Member Functions | Protected Member Functions | Protected Attributes | 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 ()

## 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)
virtual LPGNMCONSTVECTOR | GetOutEdges (GNMGFID nFID) const
virtual GNMGFID | GetOppositVertex (GNMGFID nEdgeFID, GNMGFID nVertexFID) const
virtual void | TraceTargets (std::queue< GNMGFID > &vertexQueue, std::set< GNMGFID > &markedVertIds, GNMPATH &connectedIds)

## Protected Attributes
std::map< GNMGFID, GNMStdVertex > | m_mstVertices
std::map< GNMGFID, GNMStdEdge > | m_mstEdges

## 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

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

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

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

  bIsBlock | Block or unblock

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

Change the block state of edge or vertex.

Parameters

  nFID | Identificator
  bIsBlock | Block or unblock

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

Change edge properties.

Parameters

  nConFID | Edge identificator
  dfCost | Cost
  dfInvCost | Inverse cost

bool GNMGraph::CheckVertexBlocked | ( | GNMGFID | nFID | ) | const
| virtual

Check if vertex is blocked.

Parameters

  nFID | Vertex identificator

Returns
  true if blocked, false if not blocked.

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

void GNMGraph::DeleteEdge | ( | GNMGFID | nConFID | ) |
| virtual

Delete edge from graph.

Parameters

  nConFID | Edge identificator

void GNMGraph::DeleteVertex | ( | GNMGFID | nFID | ) |
| virtual

Delete vertex from the graph.

Parameters

  nFID | Vertex identificator

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

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.
  mnPathTree | - means < vertex id, edge id >

Returns
  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.

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 files:

- gnmgraph.h
- gnmgraph.cpp

Generated for GDAL by 1.8.8.