Skip to content

Instantly share code, notes, and snippets.

@rioki
Created Jul 1, 2013
Embed
What would you like to do?
#ifndef _GRAPH_H_
#define _GRAPH_H_
#include <stdexcept>
#inlcude <set>
#include <map>
struct nil {};
template <typename VertexData = nil, typename EdgeData = nil>
class Graph
{
public:
class Vertex
{
public:
const std::set<Edge*>& get_edges()
{
return edges;
}
std::set<const Edge*> get_edges() const
{
return std::vector<const Edge*>(edges.begin(), edges.end());
}
void set_data(const VertexData& value)
{
data = value;
}
const VertexData& get_data() const
{
return data;
}
private:
VertexData data;
std::set<Edge*> edges;
Vertex() {}
~Vertex() {}
};
class Edge
{
public:
Vertex* get_first_vertex()
{
return first_vertex;
}
const Vertex* get_first_vertex() const
{
return first_vertex;
}
Vertex* get_second_vertex()
{
return second_vertex;
}
const Vertex* get_second_vertex() const
{
return second_vertex;
}
void set_data(const EdgeData& value)
{
data = value;
}
const EdgeData& get_data() const
{
return data;
}
private:
EdgeData data;
Vertex* first_vertex;
Vertex* second_vertex;
Edge(Vertex* first, Vertex* second)
{
first_vertex = first;
second_vertex = second;
}
~Edge() {}
};
Graph() {}
Graph(const Graph<VertexData, EdgeData>& orig)
{
std::map<Vertex*, Vertex*> vmapping;
for (Vertex* orig_vertex: orig.vertexes)
{
Vertex* new_vertex = add_vertex(orig_vertex->data);
vmapping[orig_vertex] = new_vertex;
}
for (Edge* orig_edge: orig.edges)
{
auto fi = vmapping.find(orig_edge->get_first_vertex());
if (fi == vmapping.end())
{
throw std::logic_error("vertex in edge not on graph");
}
auto si = vmapping.find(orig_edge->get_second_vertex());
if (si == vmapping.end())
{
throw std::logic_error("vertex in edge not on graph");
}
add_edge(*fi, *si);
}
}
~Graph()
{
for (Edge* edge: edges)
{
delete edge;
}
edges.clear();
for (Vertex* vertex: vertexes)
{
delete vertex;
}
vertexes.clear();
}
const Graph<VertexData, EdgeData>& operator = (const Graph<VertexData, EdgeData>& orig)
{
Graph<VertexData, EdgeData> tmp(orig);
tmp.swap(*this);
return *this;
}
Vertex* add_vertex()
{
Vertex* v = new Vertex;
vertexes.insert(v);
return v;
}
Vertex* add_vertex(const VertexData& data)
{
Vertex* v = add_vertex();
v->set_data(data);
return v;
}
void remove_vertex(Vertex* vertex)
{
if (vertex == NULL)
{
throw std::invalid_argument("vertex == NULL");
}
auto vi = vertexes.find(vertex);
if (vi == vertexes.end())
{
throw std::logic_error("vertex not in this graph");
}
for (Edge* edge: (*i)->edges)
{
auto ei = edges.find(edge);
if (ei == edges.end())
{
throw std::logic_error("vertex edge not in edge list");
}
edges.erase(ei);
delete edge;
}
delete vertex;
vertexes.erase(vi);
}
const std::vector<Vertex*>& get_vertexes()
{
return vertexes;
}
std::vector<const Vertex*> get_vertexes() const
{
return vertexes;
}
Edge* add_edge(Vertex* first, Vertex* second)
{
Edge* edge = new Edge(first, second);
first->edges.insert(edge);
second->edges.insert(edge);
edges.insert(edge);
return edge;
}
Edge* add_edge(Vertex* a, Vertex* b, const EdgeData& data)
{
Edge* edge = add_edge(first, second);
edge->set_data(data);
return edge;
}
void remove_edge(Edge* edge)
{
if (edge == NULL)
{
throw std::invalid_argument("edge == NULL");
}
auto ei = edges.find(edge);
if (ei == edges.end())
{
throw std::logic_error("edge not in this graph");
}
auto fi = edge->first_vertex->edges.find(edge);
if (fi == edge->first_vertex->edges.end)
{
throw std::logic_error("edge not in first vertex edge list");
}
edge->first_vertex->edges.erase(fi);
auto si = edge->second_vertex->edges.find(edge);
if (si == edge->second_vertex->edges.end)
{
throw std::logic_error("edge not in second vertex edge list");
}
edge->second_vertex->edges.erase(si);
edges.erase(ei);
delete edge;
}
const std::vector<Edge*>& get_edges()
{
return edges;
}
std::vector<const Edge*> get_edges() const
{
return edges;
}
void swap(Graph<VertexData, EdgeData>& other)
{
vertexes.swap(other->vertexes);
edges.swap(other->edges);
}
private:
std::set<Vertex*> vertexes;
std::set<Edge*> edges;
};
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment