CostGraph Class Reference

Generic adjacency graph class with shortest path method. More...

#include <shortestgraph.h>

Public Member Functions
	CostGraph (int=0)
	Create the graph.
	CostGraph (const Mesh2 &)
	Initialize the cost graph with a mesh structure.
	CostGraph (const Array2 &, int)
	Initialize the cost graph with a mesh structure.
void	Resize (int)
	Resize the number of nodes.
void	SetEdge (int, int, const double &, bool=false)
	Insert a new edge in the graph.
void	SetEdges (int, int, const double &, const double &)
	Insert two edges in the graph.
void	UpdateEdge (int, int, const double &)
	Change the cost of an edge in the graph.
bool	Exist (int, int)
	test if an edge exist.
void	DijkstraComputePaths (int, std::vector< double > &, std::vector< int > &) const
QVector< int >	DijkstraGetShortestPathTo (int, const std::vector< int > &) const
	Compute the shortest path from the initial node to a target node.
void	BreachingComputePaths (int, std::vector< double > &, std::vector< int > &) const
void	AddNodes (int=1)
	Add new nodes in the graph.
int	Nodes () const
	Return the number of nodes.
int	Edges () const
	Compute and return the number of edges.
int	Edges (int) const
	Return the number of edges of a node.
int	Target (int, int) const
	Return the index of the target node of the i-th node and j-th edge.
bool	Load (const QString &)
	Load the cost graph.
bool	Save (const QString &)
	Save the cost Graph.

Protected Attributes
std::vector< std::vector< GraphEdge > >	adj
	Adjacency (oriented) graph.

Detailed Description

Generic adjacency graph class with shortest path method.

This class implements an oriented graph, unoriented graphs simply use twice as many edges, which can be set using SetEdges().

Constructor & Destructor Documentation

CostGraph() [1/3]

CostGraph::CostGraph ( int n = 0 )

explicit

Create the graph.

Parameters

n	Number of nodes.

CostGraph() [2/3]

CostGraph::CostGraph ( const Mesh2 & mesh )

explicit

Initialize the cost graph with a mesh structure.

Cost is initialized to 1.0.

Parameters

mesh

Mesh.

CostGraph() [3/3]

CostGraph::CostGraph ( const Array2 & a, int mask )

explicit

Initialize the cost graph with a mesh structure.

Parameters

a	Array.
mask	Size of the mask in [0,7], 0 for 4-connexity, 1 for 8-connexity.

Member Function Documentation

AddNodes()

void CostGraph::AddNodes

(

int

n = 1

)

Add new nodes in the graph.

Parameters

n	Number of nodes.

BreachingComputePaths()

void CostGraph::BreachingComputePaths	(	int	source,
		std::vector< double > &	distance,
		std::vector< int > &	previous ) const

Parameters

Compute	all the paths from an initial node.
source	Starting node.
distance	Array or minimum distance for a node to its nearest neighbor.
previous	Array of nearest nodes.

DijkstraComputePaths()

void CostGraph::DijkstraComputePaths	(	int	source,
		std::vector< double > &	distance,
		std::vector< int > &	previous ) const

Parameters

Compute	all the paths from an initial node.
source	Starting node.
distance	Array or minimum distance for a node to its nearest neighbor.
previous	Array of nearest nodes.

DijkstraGetShortestPathTo()

QVector< int > CostGraph::DijkstraGetShortestPathTo	(	int	target,
		const std::vector< int > &	previous ) const

Compute the shortest path from the initial node to a target node.

Parameters

target	Target node.
previous	Set of traversed nodes, in reverse order.

Edges() [1/2]

int CostGraph::Edges

(

)

const

Compute and return the number of edges.

This function requires traversing all the nodes of the graph.

See also

Nodes.

Edges() [2/2]

int CostGraph::Edges ( int i ) const

inline

Return the number of edges of a node.

Parameters

i	Node index.

Exist()

bool CostGraph::Exist	(	int	i,
		int	j )

test if an edge exist.

Parameters

i,j	Starting and ending nodes.

Load()

bool CostGraph::Load

(

const QString &

name

)

Load the cost graph.

Parameters

name

Filename.

Nodes()

int CostGraph::Nodes

(

)

const

Return the number of nodes.

See also

Edges

Resize()

void CostGraph::Resize

(

int

n

)

Resize the number of nodes.

Parameters

n	Number of nodes.

Save()

bool CostGraph::Save

(

const QString &

name

)

Save the cost Graph.

Parameters

name

Filename.

SetEdge()

void CostGraph::SetEdge	(	int	i,
		int	j,
		const double &	c,
		bool	u = false )

Insert a new edge in the graph.

Parameters

i,j	Starting and ending nodes.
c	Cost.
u	Insert edges both ways for an undirected graph, costs will be the same.

SetEdges()

void CostGraph::SetEdges	(	int	i,
		int	j,
		const double &	a,
		const double &	b )

Insert two edges in the graph.

Parameters

i,j	Starting and ending nodes.
a,b	Costs.

Target()

int CostGraph::Target ( int i, int j ) const

inline

Return the index of the target node of the i-th node and j-th edge.

Parameters

i	Node index.
j	Edge index.

UpdateEdge()

void CostGraph::UpdateEdge	(	int	i,
		int	j,
		const double &	c )

Change the cost of an edge in the graph.

Parameters

i,j	Starting and ending nodes.
c	New cost of the edge.

---

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

• E:/X/Code/Libs/LibPath/LibPath/Include/shortestgraph.h
• E:/X/Code/Libs/LibPath/LibPath/Source/cost-graph.cpp