mp_stories
Sneaky Stories
Graph< V, E > Class Template Reference
Collaboration diagram for Graph< V, E >:
[legend]

Public Member Functions

unsigned int numVertices () const
 
unsigned int numEdges () const
 
unsigned int degree (const std::string key) const
 The degree of the vertex, given the key. More...
 
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_byRefincidentEdges (const std::string key) const
 Return the list of incident edges from a given vertex. More...
 
const std::list< E_byRefincidentEdges (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::stringshortestPath (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_byRefedgeList
 
std::unordered_map< std::string, V_byRefvertexMap
 
std::unordered_map< std::string, std::list< edgeListIter > > adjList
 

Friends

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

Member Function Documentation

◆ degree() [1/2]

template<class V , class E >
unsigned int Graph< V, E >::degree ( const std::string  key) const

The degree of the vertex, given the key.

Parameters
keyGiven key to the vertex to return degree.

◆ degree() [2/2]

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
vGiven vertex to return degree.

◆ incidentEdges() [1/2]

template<class V , class E >
const std::list< std::reference_wrapper< E > > Graph< V, E >::incidentEdges ( const std::string  key) const

Return the list of incident edges from a given vertex.

For the directed case, consider all edges that has the vertex as either a source or destination.

Parameters
keyThe key of the given vertex
Returns
The list edges (by reference) that are adjacent to the given vertex

◆ incidentEdges() [2/2]

template<class V , class E >
const std::list< std::reference_wrapper< E > > Graph< V, E >::incidentEdges ( const V &  v) const
Parameters
vThe 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
key1The key of the source Vertex
key2The 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
v1The source Vertex
v2The 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
keyThe 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. When the graph is directed, v1 and v2 are only adjacent if there is an edge from v1 to v2.

Parameters
key1The key of the source Vertex
key2The 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
v1The source Vertex
v2The destination Vertex
Returns
True if v1 is adjacent to v2, False otherwise

◆ numEdges()

template<class V , class E >
unsigned int Graph< V, E >::numEdges ( ) const
Returns
The number of edges of the Graph

◆ numVertices()

template<class V , class E >
unsigned int Graph< V, E >::numVertices ( ) const
Returns
The number of vertices in the Graph

◆ 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. min(degree(key1), degree(key2))

Parameters
key1The key of the source Vertex
key2The 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
v1The source Vertex
v2The 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
eThe 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
itAn 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
vThe 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
keyThe 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
startThe key for the starting vertex.
endThe key for the ending vertex.

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