グラフ構造を制御するクラス [詳解]

#include <FK/Graph.h>

FK::fk_Graph の継承関係図

FK::fk_Graph 連携図

公開メンバ関数
	fk_Graph (unsigned int num)
	コンストラクタ

	~fk_Graph ()
	デストラクタ

情報参照関数
unsigned int	getNodeSize (void)
	ノード数取得関数

unsigned int	getMaxEdgeID (void)
	辺ID最大値取得関数

fk_GraphNode *	getNode (unsigned int ID)
	ノード取得関数

std::list< fk_GraphNode * > *	getAllNode (void)
	全ノード取得関数

fk_GraphEdge *	getEdge (unsigned int ID)
	辺情報取得関数

std::list< fk_GraphEdge * > *	getAllEdge (void)
	全辺取得関数

bool	isConnect (fk_GraphNode v1, fk_GraphNode v2)
	辺存在確認関数

接続変更関数
fk_GraphEdge *	makeEdge (bool mode, fk_GraphNode v1, fk_GraphNode v2)
	辺生成関数

bool	deleteEdge (fk_GraphEdge *e)
	辺削除関数

経路コスト制御関数
bool	makeCostTable (unsigned int tableID, fk_CostType type)
	コストテーブル生成関数

bool	setCostDirection (unsigned int tableID, fk_CostDirection direction)
	コスト算出方向指定関数

bool	setEdgeCostID (unsigned int tableID, unsigned int edgeCostID)
	辺コストID対応指定関数

unsigned int	getNodeCostID (unsigned int tableID)
	ノード内コストID参照関数

void	setStart (unsigned int tableID, fk_GraphNode *node)
	出発ノード設定関数

void	addGoal (unsigned int tableID, fk_GraphNode *node)
	目標ノード追加関数

void	removeGoal (unsigned int tableID, fk_GraphNode *node)
	目標ノード除外関数

void	clearGoal (unsigned int tableID)
	目標ノード初期化関数

bool	initCostTable (unsigned int tableID)
	コストテーブル初期化関数

fk_CostStatus	updateCostTable (unsigned int tableID)
	コストテーブル更新関数

fk_CostStatus	getCostStatus (unsigned int tableID)
	コストテーブル状態取得関数

std::list< fk_GraphNode * >	getOnePath (unsigned int tableID)
	最短経路取得関数1

void	getOnePath (unsigned int tableID, std::list< fk_GraphNode * > *nodeList)
	最短経路取得関数2

基底クラス FK::fk_Shape に属する継承公開メンバ関数
	fk_Shape (fk_Type=fk_Type::SHAPE)
	コンストラクタ

virtual	~fk_Shape ()
	デストラクタ

fk_RealShapeType	getRealShapeType (void)
	形状データ構造取得関数

void	setShaderAttribute (std::string name, int dim, std::vector< int > *array, bool self=false)
	シェーダー内 attribute 変数設定関数1

void	setShaderAttribute (std::string name, int dim, std::vector< float > *array, bool self=false)
	シェーダー内 attribute 変数設定関数2

void	setShaderAttribute (std::string name, int dim, std::vector< fk_Vector > *array)
	シェーダー内 attribute 変数設定関数3

void	setShaderAttribute (std::string name, int dim, std::vector< fk_TexCoord > *array)
	シェーダー内 attribute 変数設定関数4

void	setShaderAttribute (std::string name, int dim, std::vector< fk_HVector > *array)
	シェーダー内 attribute 変数設定関数5

void	modifyAttribute (std::string name)
	attribute 変数更新関数

基底クラス FK::fk_Attribute に属する継承公開メンバ関数
	fk_Attribute (void)
	コンストラクタ

virtual	~fk_Attribute ()
	デストラクタ

bool	setAttrII (const int key, const int value)
	キーが int 型、値が int 型である属性設定関数

bool	setAttrID (const int key, const double value)
	キーが int 型、値が double 型である属性設定関数

bool	setAttrIS (const int key, const std::string value)
	キーが int 型、値が std::string 型である属性設定関数

bool	setAttrSI (const std::string key, const int value)
	キーが std::string 型、値が int 型である属性設定関数

bool	setAttrSD (const std::string key, const double value)
	キーが std::string 型、値が double 型である属性設定関数

bool	setAttrSS (const std::string key, const std::string value)
	キーが std::string 型、値が std::string 型である属性設定関数

int	getAttrII (const int key) const
	キーが int 型、値が int 型である属性参照関数

double	getAttrID (const int key) const
	キーが int 型、値が double 型である属性参照関数

std::string	getAttrIS (const int key) const
	キーが int 型、値が std::string 型である属性参照関数

int	getAttrSI (const std::string key) const
	キーが std::string 型、値が int 型である属性参照関数

double	getAttrSD (const std::string key) const
	キーが std::string 型、値が double 型である属性参照関数

std::string	getAttrSS (const std::string key) const
	キーが std::string 型、値が std::string 型である属性参照関数

bool	existAttrII (const int key) const
	キーが int 型、値が int 型である属性存在参照関数

bool	existAttrID (const int key) const
	キーが int 型、値が double 型である属性存在参照関数

bool	existAttrIS (const int key) const
	キーが int 型、値が std::string 型である属性存在参照関数

bool	existAttrSI (const std::string key) const
	キーが std::string 型、値が int 型である属性存在参照関数

bool	existAttrSD (const std::string key) const
	キーが std::string 型、値が double 型である属性存在参照関数

bool	existAttrSS (const std::string key) const
	キーが std::string 型、値が std::string 型である属性存在参照関数

bool	deleteAttrII (const int key)
	キーが int 型、値が int 型である属性消去関数

bool	deleteAttrID (const int key)
	キーが int 型、値が double 型である属性消去関数

bool	deleteAttrIS (const int key)
	キーが int 型、値が std::string 型である属性消去関数

bool	deleteAttrSI (const std::string key)
	キーが std::string 型、値が int 型である属性消去関数

bool	deleteAttrSD (const std::string key)
	キーが std::string 型、値が double 型である属性消去関数

bool	deleteAttrSS (const std::string key)
	キーが std::string 型、値が std::string 型である属性消去関数

基底クラス FK::fk_BaseObject に属する継承公開メンバ関数
	fk_BaseObject (fk_Type type=fk_Type::BASEOBJECT)
	コンストラクタ

fk_Type	getObjectType (void) const
	タイプ取得関数

詳解

グラフ構造を制御するクラス

このクラスは、グラフ構造を制御する機能を提供します。グラフ構造には多くの応用用途がありますが、本クラスではその中でも経路探索を念頭に置いた機能を多く提供しています。

グラフ構造は、「ノード」と「辺」の2種類の要素によって構成されます。ノードは任意の位置を持つ頂点集合であり、辺は任意の2点を接続する線分です。辺は無向線分としても有向線分としても考えることができ、経路としてとらえると無向線分は両通行経路、有向線分は一方通行経路となります。

ノードを表すクラスは fk_GraphNode, 辺を表すクラスは fk_GraphEdge であり、これらのクラスの機能も合わせて利用します。

fk_Graph のノードと辺は、「コスト」を格納することができます。グラフ内の全要素のコストをまとめて「コストテーブル」と呼びます。コストテーブルは、経路探索アルゴリズムで重要なデータであり、 fk_Graph はコストを扱うために有用な機能を多く提供しています。

コストテーブルは、int 型と double 型のいずれかを選択でき、かつ両方の型それぞれで複数のコストテーブルを格納することができます。各コストテーブルは ID により管理します。

参照: fk_GraphNode, fk_GraphEdge

構築子と解体子

◆ fk_Graph()

FK::fk_Graph::fk_Graph ( unsigned int num )

コンストラクタ

初期値として、ノード数を設定します。 fk_Graph ではノード数は固定であるため、利用する際に十分な数のノードを確保しておく必要があります。

引数

[in] num ノード数

◆ ~fk_Graph()

FK::fk_Graph::~fk_Graph ( )

デストラクタ

関数詳解

◆ getNodeSize()

unsigned int FK::fk_Graph::getNodeSize ( void )

ノード数取得関数

グラフ内に存在するノード数を取得します。

戻り値: ノード数

◆ getMaxEdgeID()

unsigned int FK::fk_Graph::getMaxEdgeID ( void )

辺ID最大値取得関数

現在存在する辺の ID の最大値を取得します。

戻り値: 最大ID

◆ getNode()

fk_GraphNode * FK::fk_Graph::getNode ( unsigned int ID )

ノード取得関数

ノードを表すインスタンスを ID より取得します。

引数

[in] ID ノード ID

戻り値: ノード

◆ getAllNode()

std::list< fk_GraphNode * > * FK::fk_Graph::getAllNode ( void )

全ノード取得関数

すべてのノードを std::list 形式で取得します。

戻り値: 全ノード情報

参照: getNode(), getAllEdge()

◆ getEdge()

fk_GraphEdge * FK::fk_Graph::getEdge ( unsigned int ID )

辺情報取得関数

辺を表すインスタンスを ID より取得します。

引数

[in] ID 辺 ID

戻り値: 辺情報

◆ getAllEdge()

std::list< fk_GraphEdge * > * FK::fk_Graph::getAllEdge ( void )

全辺取得関数

すべての辺を std::list 形式で取得します。

戻り値: 全辺情報

参照: getEdge(), getAllNode()

◆ isConnect()

bool FK::fk_Graph::isConnect	(	fk_GraphNode *	v1,
		fk_GraphNode *	v2
	)

辺存在確認関数

2つのノードの間に辺が存在するかどうかを判定します。なお、ノード間の辺は複数存在する場合もあり、2本以上存在する場合も true を返します。

引数

[in]	v1	辺の端点となるノード。
[in]	v2	辺の端点となるノード。

戻り値: 辺が存在する場合 true を、存在しない場合 false を返します。

◆ makeEdge()

fk_GraphEdge * FK::fk_Graph::makeEdge	(	bool	mode,
		fk_GraphNode *	v1,
		fk_GraphNode *	v2
	)

辺生成関数

2点のノード間に辺を作成します。なお、既に2点間に辺が存在する場合でも、エラーとならずに新たに辺を追加生成します。

引数

[in]	mode	true の場合無向、false の場合有向となります。辺が経路を表す場合は、有向辺は一方通行を表します。
[in]	v1	辺の始点となるノード。
[in]	v2	辺の終点となるノード。

戻り値: 接続した辺のインスタンスを返します。作成に失敗した場合は nullptr を返します。

◆ deleteEdge()

bool FK::fk_Graph::deleteEdge ( fk_GraphEdge * e )

辺削除関数

辺を削除します。

引数

[in] e 削除する辺のインスタンス

戻り値: 削除に成功した場合 true を、失敗した場合 false を返します。

◆ makeCostTable()

bool FK::fk_Graph::makeCostTable	(	unsigned int	tableID,
		fk_CostType	type
	)

コストテーブル生成関数

コストテーブルを作成します。作成の際には ID を指定します。指定した ID で既に作成済であった場合は false を返し、初期化は行いません。

引数

[in]	tableID	コストテーブル ID
[in]	type	コスト値のタイプを設定します。 fk_CostType::INT コストが int 型となります。 fk_CostType::DOUBLE コストが double 型となります。 fk_CostType::LENGTH コストは辺の長さとなり、内部では double 型として扱われます。

戻り値: 作成に成功すれば true を、失敗すれば false を返します。

◆ setCostDirection()

bool FK::fk_Graph::setCostDirection	(	unsigned int	tableID,
		fk_CostDirection	direction
	)

コスト算出方向指定関数

コストの算出方向を指定します。

引数

[in]	tableID	コストテーブルID
[in]	direction	コストを出発ノード側から算出する場合は fk_CostDirection::FORWARD を指定します。コストを目標ノード側から算出する場合は fk_CostDirection::BACK を指定します。

戻り値: 設定に成功すれば true を、失敗すれば false を返します。

◆ setEdgeCostID()

bool FK::fk_Graph::setEdgeCostID	(	unsigned int	tableID,
		unsigned int	edgeCostID
	)

辺コストID対応指定関数

コストテーブルに対し、コスト値算出に利用する辺のコストIDを指定します。

引数

[in]	tableID	コストテーブルID
[in]	edgeCostID	利用する辺のコスト値 ID を指定します。 makeCostTable() の第2引数に fk_CostType::LENGTH を指定していた場合、この値は無視されます。

◆ getNodeCostID()

unsigned int FK::fk_Graph::getNodeCostID ( unsigned int tableID )

ノード内コストID参照関数

コストテーブルに対応するノード内コストIDを参照します。

引数

[in] tableID コストテーブルID

戻り値: ノード内コストID

◆ setStart()

void FK::fk_Graph::setStart	(	unsigned int	tableID,
		fk_GraphNode *	node
	)

出発ノード設定関数

経路探索における出発ノードを指定します。既に別の出発ノードが設定されていた場合は、新たに設定したノードに更新されます。

引数

[in]	tableID	コストテーブルID
[in]	node	ノードインスタンス

◆ addGoal()

void FK::fk_Graph::addGoal	(	unsigned int	tableID,
		fk_GraphNode *	node
	)

目標ノード追加関数

経路探索における目標ノードを追加します。目標ノードは一つのコストテーブルに対し複数設定することができます。

引数

[in]	tableID	コストテーブルID
[in]	node	目標ノードインスタンス

◆ removeGoal()

void FK::fk_Graph::removeGoal	(	unsigned int	tableID,
		fk_GraphNode *	node
	)

目標ノード除外関数

対象ノードを、目標ノードから除外します。

引数

[in]	tableID	コストテーブルID
[in]	node	目標ノードインスタンス

◆ clearGoal()

void FK::fk_Graph::clearGoal ( unsigned int tableID )

目標ノード初期化関数

現時点で登録されている目標ノードを全て除外します。

引数

[in] tableID コストテーブルID

◆ initCostTable()

bool FK::fk_Graph::initCostTable ( unsigned int tableID )

コストテーブル初期化関数

コストテーブルを初期化します。

引数

[in] tableID コストテーブルID

戻り値: 初期化に成功したら true を、失敗したら false を返します。 setCostMode() による設定が行われていないコストテーブルだった場合は false を返します。

◆ updateCostTable()

fk_CostStatus FK::fk_Graph::updateCostTable ( unsigned int tableID )

コストテーブル更新関数

各ノードに対し、コスト算出を一段階進めます。全てのノードのコスト値を完全にするには、 fk_CostStatus::FINISH が返されるまで繰り返し本関数を呼び出す必要があります。

引数

[in] tableID コストテーブルID

戻り値

現在のコスト算出状況を返します。

fk_CostStatus::CONTINUE
コスト算出がまだ途中段階であることを意味します。
fk_CostStatus::FINISH
コスト算出が完了したことを意味します。
fk_CostStatus::ERROR
グラフ内のコスト算出に関する情報が不完全であることを意味します。

◆ getCostStatus()

fk_CostStatus FK::fk_Graph::getCostStatus ( unsigned int tableID )

コストテーブル状態取得関数

現在のコストテーブルにおける更新情報を取得します。 updateCostTable() では実際にコストテーブルの更新処理を行いますが、本関数は更新処理は行わず状態のみを取得します。

引数

[in] tableID コストテーブルID

戻り値

現在のコスト算出状況を返します。

fk_CostStatus::CONTINUE
コスト算出がまだ途中段階であることを意味します。
fk_CostStatus::FINISH
コスト算出が完了したことを意味します。
fk_CostStatus::ERROR
グラフ内のコスト算出に関する情報が不完全であることを意味します。

◆ getOnePath() [1/2]

std::list< fk_GraphNode * > FK::fk_Graph::getOnePath ( unsigned int tableID )

最短経路取得関数1

コストテーブルに基づいた、出発ノードから目標ノードまでの最短経路を取得します。本関数を用いる際には、事前にコストテーブルの更新が完了し、 getCostStatus() による結果が fk_CostStatus::FINISH となる状況でなければなりません。

最短経路が複数存在するような場合、任意の1種類のみを取得します。現状では全ての最短経路を取得する機能は提供していません。

目標ノードが複数ある場合、そのうち出発ノードからもっとも経路が短いものが抽出されます。

本関数は STL コンテナを直接返すため、経路情報が大きい場合はコピーの演算コストが増大します。速度を重視する場合は getOnePath(unsigned int, std::list<fk_GraphNode *> *) の利用を推奨します。

引数

[in] tableID 経路探索に用いるコストテーブルの ID

戻り値: 最短経路の経由地となるノードを経路順に格納したリストを返します。

◆ getOnePath() [2/2]

void FK::fk_Graph::getOnePath	(	unsigned int	tableID,
		std::list< fk_GraphNode * > *	nodeList
	)

最短経路取得関数2

コストテーブルに基づいた、出発ノードから目標ノードまでの最短経路を取得します。本関数を用いる際には、事前にコストテーブルの更新が完了し、 getCostStatus() による結果が fk_CostStatus::FINISH となる状況でなければなりません。

最短経路が複数存在するような場合、任意の1種類のみを取得します。現状では全ての最短経路を取得する機能は提供していません。

目標ノードが複数ある場合、そのうち出発ノードからもっとも経路が短いものが抽出されます。

引数

[in]	tableID	経路探索に用いるコストテーブルの ID
[out]	nodeList	最短経路の経由地となるノードを、経路順に格納します。

公開メンバ関数

詳解

構築子と解体子

◆ fk_Graph()

◆ ~fk_Graph()

関数詳解

◆ getNodeSize()

◆ getMaxEdgeID()

◆ getNode()

◆ getAllNode()

◆ getEdge()

◆ getAllEdge()

◆ isConnect()

◆ makeEdge()

◆ deleteEdge()

◆ makeCostTable()

◆ setCostDirection()

◆ setEdgeCostID()

◆ getNodeCostID()

◆ setStart()

◆ addGoal()

◆ removeGoal()

◆ clearGoal()

◆ initCostTable()

◆ updateCostTable()

◆ getCostStatus()

◆ getOnePath() [1/2]

◆ getOnePath() [2/2]