spanning_tree Class Reference

A class that generates a minimum-spanning-tree (MST) graph for a given grid map. More...

#include <spanning_tree.h>

Public Member Functions
void	construct ()
	Generate the MST using Kruskal's algorithm. More...
vector< edge >	get_mst_edges ()
	Get the edges of the MST. More...
geometry_msgs::PoseArray	get_tree ()
	Get the generated MST for visualization. More...
void	initialize_graph (nav_msgs::OccupancyGrid gridmap, bool connect4=true)
	Initialize the internal tree structure from a given grid map. More...
	spanning_tree ()
	Constructor. More...

Private Member Functions
void	add_edge (int from, int to, int cost)
	Add an edge to the tree. More...
bool	different_sets (int a, int b)
	Check whether two vertices are in different sets. More...

Private Attributes
priority_queue< edge, vector< edge >, compare_edge >	edges
	Priority queue of edge objects sorted by cost. More...
nav_msgs::OccupancyGrid	map
	The grid map that needs to be covered by the MST. More...
vector< edge >	mst_edges
	Edges in Minimal-Spanning Tree. More...
vector< unordered_set< int > >	nodes
	The sets of connected vertices. More...

Detailed Description

A class that generates a minimum-spanning-tree (MST) graph for a given grid map.

Definition at line 19 of file spanning_tree.h.

Constructor & Destructor Documentation

spanning_tree()

spanning_tree::spanning_tree

(

)

Constructor.

Definition at line 3 of file spanning_tree.cpp.

Member Function Documentation

add_edge()

void spanning_tree::add_edge ( int  from, int  to, int  cost  )

private

Add an edge to the tree.

Parameters

from	The starting vertex.
to	The ending vertex.
cost	The cost of the edge.

Definition at line 116 of file spanning_tree.cpp.

construct()

void spanning_tree::construct

(

)

Generate the MST using Kruskal's algorithm.

Definition at line 90 of file spanning_tree.cpp.

different_sets()

bool spanning_tree::different_sets ( int  a, int  b  )

private

Check whether two vertices are in different sets.

Parameters

a	The first vertex.
b	The second vertex.

Returns

True if the vertices are in different connected components, i.e., the set for vertex a is different from that for vertex b.

Definition at line 130 of file spanning_tree.cpp.

get_mst_edges()

vector< edge > spanning_tree::get_mst_edges

(

)

Get the edges of the MST.

Returns

A vector with all edges of the MST.

Definition at line 7 of file spanning_tree.cpp.

get_tree()

geometry_msgs::PoseArray spanning_tree::get_tree

(

)

Get the generated MST for visualization.

Returns

An array of poses that represent the vertices of the tree.

Definition at line 12 of file spanning_tree.cpp.

initialize_graph()

void spanning_tree::initialize_graph	(	nav_msgs::OccupancyGrid	gridmap,
		bool	connect4 = true
	)

Initialize the internal tree structure from a given grid map.

Parameters

gridmap	The grid map that needs to be covered by the tree.
connect4	Whether only the von Neumann neighborhood is considered. Default true.

Definition at line 39 of file spanning_tree.cpp.

Member Data Documentation

edges

priority_queue<edge, vector<edge>, compare_edge> spanning_tree::edges

private

Priority queue of edge objects sorted by cost.

Definition at line 76 of file spanning_tree.h.

map

nav_msgs::OccupancyGrid spanning_tree::map

private

The grid map that needs to be covered by the MST.

Definition at line 86 of file spanning_tree.h.

mst_edges

vector<edge> spanning_tree::mst_edges

private

Edges in Minimal-Spanning Tree.

Definition at line 81 of file spanning_tree.h.

nodes

vector<unordered_set<int> > spanning_tree::nodes

private

The sets of connected vertices.

Definition at line 71 of file spanning_tree.h.

---

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

• spanning_tree.h
• spanning_tree.cpp