mp_stories
Sneaky Stories
|
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_byRef > | incidentEdges (const std::string key) const |
Return the list of incident edges from a given vertex. More... | |
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_byRef > | vertexMap |
std::unordered_map< std::string, std::list< edgeListIter > > | adjList |
Friends | |
std::ostream & | operator<< (std::ostream &out, const Graph< V, E > &g) |
unsigned int Graph< V, E >::degree | ( | const std::string | key | ) | const |
The degree of the vertex, given the key.
key | Given key to the vertex to return degree. |
unsigned int Graph< V, E >::degree | ( | const V & | v | ) | const |
The degree of the vertex.
For directed: Sum of in-degree and out-degree
v | Given vertex to return degree. |
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.
key | The key of the given vertex |
const std::list< std::reference_wrapper< E > > Graph< V, E >::incidentEdges | ( | const V & | v | ) | const |
v | The Vertex that you would like to find the incident edges for |
E & Graph< V, E >::insertEdge | ( | const std::string | key1, |
const std::string | key2 | ||
) |
E & Graph< V, E >::insertEdge | ( | const V & | v1, |
const V & | v2 | ||
) |
V & Graph< V, E >::insertVertex | ( | std::string | key | ) |
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.
bool Graph< V, E >::isAdjacent | ( | const V & | v1, |
const V & | v2 | ||
) | const |
unsigned int Graph< V, E >::numEdges | ( | ) | const |
unsigned int Graph< V, E >::numVertices | ( | ) | const |
void Graph< V, E >::removeEdge | ( | const std::string | key1, |
const std::string | key2 | ||
) |
void Graph< V, E >::removeEdge | ( | const V & | v1, |
const V & | v2 | ||
) |
void Graph< V, E >::removeEdge | ( | const edgeListIter & | it | ) |
void Graph< V, E >::removeVertex | ( | const std::string & | key | ) |
void Graph< V, E >::removeVertex | ( | const V & | v | ) |
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.
start | The key for the starting vertex. |
end | The key for the ending vertex. |