Graph< V, E > Class Template Reference

Collaboration diagram for Graph< V, E >:

Public Member Functions
unsigned int	size () const
unsigned int	edges () const
unsigned int	degree (const V &v) const
	The degree of the vertex. More...
V &	insertVertex (std::string key)
	Inserts a Vertex into the Graph. More...
void	removeVertex (const std::string &key)
	Removes a given Vertex. More...
void	removeVertex (const V &v)
	Removes the Vertex which the given key. More...
E &	insertEdge (const std::string key1, const std::string key2)
	Inserts an Edge into the Graph. More...
E &	insertEdge (const V &v1, const V &v2)
	Inserts an Edge into the Graph. More...
void	removeEdge (const std::string key1, const std::string key2)
	Removes an Edge from the Graph. More...
void	removeEdge (const V &v1, const V &v2)
	Removes an Edge from the adjacency list. More...
void	removeEdge (const Edge &e)
	Removes the given Edge from the Graph. More...
void	removeEdge (const edgeListIter &it)
	Removes an Edge from the Graph given by the location of the given iterator into the edge list. More...
const std::list< E_byRef >	incidentEdges (const std::string key) const
const std::list< E_byRef >	incidentEdges (const V &v) const
bool	isAdjacent (const std::string key1, const std::string key2) const
	Return whether the two vertices are adjacent to one another. More...
bool	isAdjacent (const V &v1, const V &v2) const
	Return whether the two vertices are adjacent to one another. More...
std::list< std::string >	shortestPath (const std::string start, const std::string end)
	Returns an std::list of vertex keys that creates any shortest path between start and end. More...

Private Types
typedef std::reference_wrapper< E >	E_byRef
typedef std::reference_wrapper< V >	V_byRef
typedef std::list< E_byRef >::iterator	edgeListIter

Private Attributes
std::list< E_byRef >	edgeList
std::unordered_map< std::string, V & >	vertexMap
std::unordered_map< std::string, std::list< edgeListIter > >	adjList

Friends
std::ostream &	operator<< (std::ostream &out, const Graph< V, E > &g)

Member Function Documentation

degree()

template<class V , class E >

unsigned int Graph< V, E >::degree

(

const V &

v

)

const

The degree of the vertex.

For directed: Sum of in-degree and out-degree

Returns

Returns the degree of a given vertex.

Parameters

v	Given vertex to return degree.

edges()

template<class V , class E >

unsigned int Graph< V, E >::edges

(

)

const

Returns

The edges of the Graph

incidentEdges() [1/2]

template<class V , class E >

const std::list< std::reference_wrapper< E > > Graph< V, E >::incidentEdges

(

const std::string

key

)

const

Parameters

key	The key of an arbitrary Vertex "v"

Returns

The list edges (by reference) that are adjacent to "v"

incidentEdges() [2/2]

template<class V , class E >

const std::list< std::reference_wrapper< E > > Graph< V, E >::incidentEdges

(

const V &

v

)

const

Parameters

v	The Vertex that you would like to find the incident edges for

Returns

The list edges (by reference) that are adjacent to the given v

insertEdge() [1/2]

template<class V , class E >

E & Graph< V, E >::insertEdge	(	const std::string	key1,
		const std::string	key2
	)

Inserts an Edge into the Graph.

Parameters

key1	The key of the source Vertex
key2	The key of the destination Vertex

Returns

The inserted Edge

insertEdge() [2/2]

template<class V , class E >

E & Graph< V, E >::insertEdge	(	const V &	v1,
		const V &	v2
	)

Inserts an Edge into the Graph.

Parameters

v1	The source Vertex
v2	The destination Vertex

Returns

The inserted Edge

insertVertex()

template<class V , class E >

V & Graph< V, E >::insertVertex

(

std::string

key

)

Inserts a Vertex into the Graph.

Parameters

key	The key of the Vertex to insert

Returns

The inserted Vertex

isAdjacent() [1/2]

template<class V , class E >

bool Graph< V, E >::isAdjacent	(	const std::string	key1,
		const std::string	key2
	)		const

Return whether the two vertices are adjacent to one another.

Consider both the undirected and directed cases.

Parameters

key1	The key of the source Vertex
key2	The key of the destination Vertex

Returns

True if v1 is adjacent to v2, False otherwise

isAdjacent() [2/2]

template<class V , class E >

bool Graph< V, E >::isAdjacent	(	const V &	v1,
		const V &	v2
	)		const

Return whether the two vertices are adjacent to one another.

Parameters

v1	The source Vertex
v2	The destination Vertex

Returns

True if v1 is adjacent to v2, False otherwise

removeEdge() [1/4]

template<class V , class E >

void Graph< V, E >::removeEdge	(	const std::string	key1,
		const std::string	key2
	)

Removes an Edge from the Graph.

Consider both the undirected and directed cases.

Parameters

key1	The key of the source Vertex
key2	The key of the destination Vertex

removeEdge() [2/4]

template<class V , class E >

void Graph< V, E >::removeEdge	(	const V &	v1,
		const V &	v2
	)

Removes an Edge from the adjacency list.

Hint: Maybe we can use our iterator removeEdge?

Parameters

v1	The source Vertex
v2	The destination Vertex

removeEdge() [3/4]

template<class V , class E >

void Graph< V, E >::removeEdge

(

const Edge &

e

)

Removes the given Edge from the Graph.

Hint: Use std::find

Parameters

e	The Edge you want to remove

removeEdge() [4/4]

template<class V , class E >

void Graph< V, E >::removeEdge

(

const edgeListIter &

it

)

Removes an Edge from the Graph given by the location of the given iterator into the edge list.

Parameters

it	An iterator at the location of the Edge that you would like to remove

removeVertex() [1/2]

template<class V , class E >

void Graph< V, E >::removeVertex

(

const std::string &

key

)

Removes a given Vertex.

Parameters

v	The Vertex to remove

removeVertex() [2/2]

template<class V , class E >

void Graph< V, E >::removeVertex

(

const V &

v

)

Removes the Vertex which the given key.

Parameters

key	The key of the Vertex to remove

shortestPath()

template<class V , class E >

std::list< std::string > Graph< V, E >::shortestPath	(	const std::string	start,
		const std::string	end
	)

Returns an std::list of vertex keys that creates any shortest path between start and end.

This list MUST include the key of the start vertex as the first vertex in the list, the key of the end vertex as the last element in the list, and an ordered list of all vertices that must be traveled along the shortest path.

For example, the path a -> c -> e returns a list with three elements: "a", "c", "e".

You should use undirected edges. Hint: There are no edge weights in the Graph.

Parameters

start	The key for the starting vertex.
end	The key for the ending vertex.

size()

template<class V , class E >

unsigned int Graph< V, E >::size

(

)

const

Returns

The number of vertices in the Graph

---

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

• Graph.h
• Graph-given.hpp
• Graph.hpp
• Graph2.hpp