SH::ShGraph< G > Class Template Reference

Inheritance diagram for SH::ShGraph< G >:

[legend]List of all members.

typedef VertexPairMap< Edge * >	FirstStepMap
	All-pairs shortest path using Floyd-Warshall (CLRS 25.2) Returns result in dist, first edge in a shortest path in path.
template<typename W>
void	floydWarshall (W &weigher, VertexPairMap< typename W::WeightType > &dist, FirstStepMap *path=0)
Public Types
typedef G::Vertex	Vertex
typedef G::Edge	Edge
typedef std::set< Vertex * >	VertexSet
typedef std::set< Edge * >	EdgeSet
typedef std::list< Vertex * >	VertexList
typedef std::list< Edge * >	EdgeList
typedef std::pair< Vertex *, Vertex * >	VertexPair
typedef VertexPairMap< bool >	TransitiveClosureMap
typedef VertexMap< int >	HeightMap
typedef VertexPairMap< Vertex * >	LCAMap
Public Member Functions
	ShGraph ()
	ShGraph (const ShGraph< G > &other)
	Makes a copy of the graph using operator=.
	~ShGraph ()
	Destroys ShGraph and deletes any added vertices/edges.
void	addVertex (Vertex *v)
	Adds a vertex to the graph.
void	addEdge (Edge *e)
	Adds an edge to the graph.
void	removeVertex (Vertex *v)
	Removes a vertex from the graph and all incident edges.
void	removeEdge (Edge *e)
	Removes an edge from the graph.
void	clear ()
	erases all vertices/edges from the graph and deletes them
void	clearMarked ()
	clears marks on all vertices
ShGraph< G > &	operator= (const ShGraph< G > &other)
	Clones the vertices and edges in this graph.
template<typename F>
void	dfs (Vertex *start, F &functor)
	Performs a DFS of the graph starting from the given vertex, applying the given functor to each node as it is traversed.
void	transitiveClosure (TransitiveClosureMap &tcm)
void	rootSet (VertexSet &roots)
void	vertexHeight (const VertexSet &roots, HeightMap &heights)
void	leastCommonAncestor (LCAMap &ancestor)
template<typename W>
W::WeightType	bellmanFord (Vertex *start, Vertex *end, W &weigher, EdgeList *path=0)
	Single-Source shortest path using Bellman-Ford (CLRS 24.1) TODO - might want this to return all shortest distances/paths (from the given start).
Public Attributes
VertexSet	verts
EdgeSet	edges
Classes
struct	VertexMap
struct	VertexPairMap

---

Detailed Description

template<typename G>
class SH::ShGraph< G >

Definition at line 106 of file ShGraph.hpp.

---

Member Typedef Documentation

template<typename G> typedef VertexPairMap<Edge*> SH::ShGraph< G >::FirstStepMap

All-pairs shortest path using Floyd-Warshall (CLRS 25.2) Returns result in dist, first edge in a shortest path in path. Note, if you use bool for a weighttype, this produces a reasonably efficient transitive closure implementation... Definition at line 213 of file ShGraph.hpp.

---

Member Function Documentation

template<typename G> void SH::ShGraph< G >::addEdge (  Edge *  e  )

Adds an edge to the graph. Appends e to the end of e->start's edge list Definition at line 94 of file ShGraphImpl.hpp. References SH::ShGraph< G >::edges. Referenced by SH::ShGraph< G >::operator=().

---

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

• ShGraph.hpp
• ShGraphImpl.hpp

---