#ifndef UNDIRECTEDGRAPH_H
#define UNDIRECTEDGRAPH_H 1

#include "Common/ContigNode.h"
#include "Common/Hash.h"
#include "Graph/Properties.h"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
#include <iostream>

/**
 * An edge for an undirected graph, having the key property that
 * (u, v) == (v, u). The unsigned values here are the vertex_descriptor's.
 */
class UndirectedEdge : public std::pair<unsigned, unsigned>
{

public:

	UndirectedEdge() : std::pair<unsigned, unsigned>() {}

	UndirectedEdge(unsigned u, unsigned v)
		: std::pair<unsigned, unsigned>(u, v) {}

	bool operator ==(const UndirectedEdge& e) const
	{
		return (first == e.first && second == e.second) ||
			(first == e.second && second == e.first);
	}

	bool operator !=(const UndirectedEdge& e) const
	{
		return !(*this == e);
	}

	size_t hashCode() const
	{
		return first ^ second;
	}
};

/**
 * The hash function for an undirected edge, having the key property that
 * hash(u, v) == hash(v, u).
 */
NAMESPACE_STD_HASH_BEGIN
template <> struct hash<UndirectedEdge> {
	/**
	 * Hash function for graph vertex type (vertex_descriptor)
	 */
	size_t operator()(const UndirectedEdge& e) const
	{
		return e.hashCode();
	}
};
NAMESPACE_STD_HASH_END

/** A undirected graph. */
template <typename VertexProp = no_property,
		 typename EdgeProp = no_property>
class UndirectedGraph
{
	class Vertex;
	typedef typename std::vector<Vertex> Vertices;
	class Edge;
	typedef typename std::vector<Edge> Edges;

  public:
	// Graph
	/* typedef ContigNode vertex_descriptor; */
	typedef unsigned vertex_descriptor;

	// IncidenceGraph
	typedef UndirectedEdge edge_descriptor;

	typedef unsigned degree_size_type;

	// BidirectionalGraph
	typedef void in_edge_iterator;

	// VertexListGraph
	typedef unsigned vertices_size_type;

	// EdgeListGraph
	typedef unsigned edges_size_type;

	// PropertyGraph
	typedef VertexProp vertex_bundled;
	typedef VertexProp vertex_property_type;
	typedef EdgeProp edge_bundled;
	typedef EdgeProp edge_property_type;

	typedef boost::undirected_tag directed_category;
	typedef boost::allow_parallel_edge_tag edge_parallel_category;
	struct traversal_category
		: boost::incidence_graph_tag,
		boost::adjacency_graph_tag,
		boost::vertex_list_graph_tag,
		boost::edge_list_graph_tag { };

/** Iterate through the vertices of this graph. */
class vertex_iterator
	: public std::iterator<std::input_iterator_tag,
		const vertex_descriptor>
{
  public:
	vertex_iterator() { }
	explicit vertex_iterator(vertices_size_type v) : m_v(v) { }
	const vertex_descriptor& operator *() const { return m_v; }

	bool operator ==(const vertex_iterator& it) const
	{
		return m_v == it.m_v;
	}

	bool operator !=(const vertex_iterator& it) const
	{
		return m_v != it.m_v;
	}

	vertex_iterator& operator ++() { ++m_v; return *this; }
	vertex_iterator operator ++(int)
	{
		vertex_iterator it = *this;
		++*this;
		return it;
	}

  private:
	vertex_descriptor m_v;
};

/** Iterate through the out-edges. */
class out_edge_iterator
	: public std::iterator<std::input_iterator_tag, edge_descriptor>
{
	typedef typename Edges::const_iterator const_iterator;

  public:
	out_edge_iterator() { }
	out_edge_iterator(const const_iterator& it,
			vertex_descriptor src) : m_it(it), m_src(src) { }

	edge_descriptor operator *() const
	{
		return edge_descriptor(m_src, m_it->target());
	}

	bool operator ==(const out_edge_iterator& it) const
	{
		return m_it == it.m_it;
	}

	bool operator !=(const out_edge_iterator& it) const
	{
		return m_it != it.m_it;
	}

	out_edge_iterator& operator ++() { ++m_it; return *this; }
	out_edge_iterator operator ++(int)
	{
		out_edge_iterator it = *this;
		++*this;
		return it;
	}

	const edge_property_type& get_property() const
	{
		return m_it->get_property();
	}

  private:
	const_iterator m_it;
	vertex_descriptor m_src;
};

/** Iterate through adjacent vertices. */
class adjacency_iterator : public Edges::const_iterator
{
	typedef typename Edges::const_iterator It;
  public:
	adjacency_iterator() { }
	adjacency_iterator(const It& it) : It(it) { }
	vertex_descriptor operator*() const
	{
		return It::operator*().target();
	}
};

/** Iterate through edges. */
class edge_iterator
	: public std::iterator<std::input_iterator_tag, edge_descriptor>
{
	void nextVertex()
	{
		vertex_iterator vlast = m_g->vertices().second;
		for (; m_vit != vlast; ++m_vit) {
			std::pair<adjacency_iterator, adjacency_iterator>
				adj = m_g->adjacent_vertices(*m_vit);
			/*
			 * Since each edge exists as both (u, v) and
			 * (v, u), require `adj.first >= *m_vit` to visit only
			 * one of the two possible forms.
			 */
			if (adj.first != adj.second && *adj.first >= *m_vit) {
				m_eit = adj.first;
				return;
			}
		}
		// Set m_eit to a known value.
		static const adjacency_iterator s_eitNULL;
		m_eit = s_eitNULL;
	}

  public:
	edge_iterator() { }
	edge_iterator(const UndirectedGraph* g, const vertex_iterator& vit)
		: m_g(g), m_vit(vit)
	{
		nextVertex();
	}

	edge_descriptor operator*() const
	{
		return edge_descriptor(*m_vit, *m_eit);
	}

	bool operator==(const edge_iterator& it) const
	{
		return m_vit == it.m_vit && m_eit == it.m_eit;
	}

	bool operator!=(const edge_iterator& it) const
	{
		return !(*this == it);
	}

	edge_iterator& operator++()
	{
		if (++m_eit == m_g->adjacent_vertices(*m_vit).second) {
			++m_vit;
			nextVertex();
		}
		return *this;
	}

	edge_iterator operator++(int)
	{
		edge_iterator it = *this;
		++*this;
		return it;
	}

  private:
	const UndirectedGraph* m_g;
	vertex_iterator m_vit;
	adjacency_iterator m_eit;
};

  private:
/** A vertex and its properties. */
class Vertex
{
  public:
	Vertex() { }
	Vertex(const vertex_property_type& p) : m_prop(p) { }

	/** Return the properties of this vertex. */
	const vertex_property_type& get_property() const
	{
		return m_prop;
	}

	/** Returns an iterator-range to the out edges of vertex u. */
	std::pair<out_edge_iterator, out_edge_iterator>
	out_edges(vertex_descriptor u) const
	{
		return make_pair(out_edge_iterator(m_edges.begin(), u),
				out_edge_iterator(m_edges.end(), u));
	}

	/** Returns an iterator-range to the adjacent vertices. */
	std::pair<adjacency_iterator, adjacency_iterator>
	adjacent_vertices() const
	{
		return make_pair(m_edges.begin(), m_edges.end());
	}

	/** Return the number of outgoing edges. */
	degree_size_type out_degree() const
	{
		return m_edges.size();
	}

	/** Add an edge to this vertex. */
	bool add_edge(vertex_descriptor v, const edge_property_type& ep)
	{
		m_edges.push_back(Edge(v, ep));
		return true;
	}

	/** Remove the edge to v from this vertex. */
	void remove_edge(vertex_descriptor v)
	{
		m_edges.erase(remove(m_edges.begin(), m_edges.end(), v),
				m_edges.end());
	}

	/** Remove all out edges from this vertex. */
	void clear_out_edges()
	{
		m_edges.clear();
	}

	/** Return the properties of the edge with target v. */
	edge_property_type& operator[](vertex_descriptor v)
	{
		typename Edges::iterator it
			= find(m_edges.begin(), m_edges.end(), v);
		assert(it != m_edges.end());
		return it->get_property();
	}

	/** Return the properties of the edge with target v. */
	const edge_property_type& operator[](vertex_descriptor v) const
	{
		typename Edges::const_iterator it
			= find(m_edges.begin(), m_edges.end(), v);
		assert(it != m_edges.end());
		return it->get_property();
	}

	/** Return true if edge (u,v) exists. */
	bool edge(vertex_descriptor v) const
	{
		return count(m_edges.begin(), m_edges.end(), v) > 0;
	}

	/** Remove edges that satisfy the predicate. */
	template <typename Predicate>
	void remove_edge_if(vertex_descriptor u, Predicate predicate)
	{
		typename Edges::iterator out = m_edges.begin();
		for (typename Edges::iterator it = m_edges.begin();
				it != m_edges.end(); ++it) {
			if (!predicate(edge_descriptor(u, it->target()))) {
				if (out != it)
					*out = *it;
				++out;
			}
		}
		m_edges.erase(out, m_edges.end());
	}

  private:
	Edges m_edges;
	vertex_property_type m_prop;
};

/** A directed edge. */
class Edge
{
  public:
	explicit Edge(vertex_descriptor v, const edge_property_type& ep)
		: m_target(v), m_ep(ep) { }

	/** Returns the target vertex of this edge. */
	vertex_descriptor target() const { return m_target; }

	/** Return true if the target of this edge is v. */
	bool operator ==(const vertex_descriptor& v) const
	{
		return m_target == v;
	}

	edge_property_type& get_property() { return m_ep; }
	const edge_property_type& get_property() const { return m_ep; }

  private:
	/** The target vertex of this edge. */
	vertex_descriptor m_target;
	edge_property_type m_ep;
};

  public:
	/** Create an empty graph. */
	UndirectedGraph() { }

	/** Create a graph with n vertices and zero edges. */
	UndirectedGraph(vertices_size_type n) : m_vertices(n) { }

	/** Swap this graph with graph x. */
	void swap(UndirectedGraph& x)
	{
		m_vertices.swap(x.m_vertices);
		m_removed.swap(x.m_removed);
	}

	/** Return properties of vertex u. */
	const vertex_property_type& operator[](vertex_descriptor u) const
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		return m_vertices[ui].get_property();
	}

	/** Returns an iterator-range to the vertices. */
	std::pair<vertex_iterator, vertex_iterator> vertices() const
	{
		return make_pair(vertex_iterator(0),
			vertex_iterator(num_vertices()));
	}

	/** Remove all the edges and vertices from this graph. */
	void clear() { m_vertices.clear(); m_removed.clear(); }

	/** Add a vertex to this graph. */
	vertex_descriptor add_vertex(
			const vertex_property_type& vp = vertex_property_type())
	{
		m_vertices.push_back(Vertex(vp));
		return vertex_descriptor(num_vertices() - 1);
	}

	/** Returns an iterator-range to the out edges of vertex u. */
	std::pair<out_edge_iterator, out_edge_iterator>
	out_edges(vertex_descriptor u) const
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		return m_vertices[ui].out_edges(u);
	}

	/** Returns an iterator-range to the adjacent vertices of
	 * vertex u. */
	std::pair<adjacency_iterator, adjacency_iterator>
	adjacent_vertices(vertex_descriptor u) const
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		return m_vertices[ui].adjacent_vertices();
	}

	/** Adds edge (u,v) to this graph. */
	std::pair<edge_descriptor, bool>
	add_edge(vertex_descriptor u, vertex_descriptor v,
			const edge_property_type& ep = edge_property_type())
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		vertices_size_type vi = get(vertex_index, *this, v);
		assert(vi < num_vertices());
		m_vertices[vi].add_edge(u, ep);
		return make_pair(edge_descriptor(u, v),
				m_vertices[ui].add_edge(v, ep));
	}

	/** Remove the edge (u,v) from this graph. */
	void remove_edge(vertex_descriptor u, vertex_descriptor v)
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		vertices_size_type vi = get(vertex_index, *this, v);
		assert(vi < num_vertices());
		m_vertices[ui].remove_edge(v);
		m_vertices[ui].remove_edge(u);
	}

	/** Remove the edge e from this graph. */
	void remove_edge(edge_descriptor e)
	{
		remove_edge(e.first, e.second);
	}

#if 0
	/** Remove all out edges from vertex u. */
	void clear_out_edges(vertex_descriptor u)
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		m_vertices[ui].clear_out_edges();
	}
#endif

	/** Remove all edges to and from vertex u from this graph.
	 * O(V+E) */
	void clear_vertex(vertex_descriptor u)
	{
		std::pair<adjacency_iterator, adjacency_iterator>
			adj = adjacent_vertices(u);
		for (adjacency_iterator v = adj.first; v != adj.second; ++v)
			remove_edge(*v, u);
	}

	/** Set the vertex_removed property. */
	void put(vertex_removed_t, vertex_descriptor u, bool flag)
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		if (ui >= m_removed.size())
			m_removed.resize(ui + 1);
		m_removed[ui] = flag;
	}

	/** Remove vertex u from this graph. It is assumed that there
	 * are no edges to or from vertex u. It is best to call
	 * clear_vertex before remove_vertex.
	 */
	void remove_vertex(vertex_descriptor u)
	{
		put(vertex_removed, u, true);
	}

	/** Return the number of vertices. */
	vertices_size_type num_vertices() const
	{
		return m_vertices.size();
	}

	/** Return the number of edges. */
	edges_size_type num_edges() const
	{
		edges_size_type n = 0;
		std::pair<vertex_iterator, vertex_iterator> vit = vertices();
		for (vertex_iterator v = vit.first; v != vit.second; ++v)
			n += out_degree(*v);
		/* should have (u, v) and (v, u) versions for each edge */
		assert(n % 2 == 0);
		return n / 2;
	}

	/** Return the out degree of vertex u. */
	degree_size_type out_degree(vertex_descriptor u) const
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		return m_vertices[ui].out_degree();
	}

	/** Return the nth vertex. */
	static vertex_descriptor vertex(vertices_size_type n)
	{
		return vertex_descriptor(n);
	}

	/** Iterate through the edges of this graph. */
	std::pair<edge_iterator, edge_iterator> edges() const
	{
		std::pair<vertex_iterator, vertex_iterator> vit = vertices();
		return make_pair(edge_iterator(this, vit.first),
				edge_iterator(this, vit.second));
	}

	/** Return the edge (u,v) if it exists and a flag indicating
	 * whether the edge exists.
	 */
	std::pair<edge_descriptor, bool> edge(
			vertex_descriptor u, vertex_descriptor v) const
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		assert(ui < num_vertices());
		return make_pair(edge_descriptor(u, v),
				m_vertices[ui].edge(v));
	}

	/** Return properties of edge e. */
	edge_property_type& operator[](edge_descriptor e)
	{
		vertices_size_type ui = get(vertex_index, *this, e.first);
		assert(ui < num_vertices());
		return m_vertices[ui][e.second];
	}

	/** Return properties of edge e. */
	const edge_property_type& operator[](edge_descriptor e) const
	{
		vertices_size_type ui = get(vertex_index, *this, e.first);
		assert(ui < num_vertices());
		return m_vertices[ui][e.second];
	}

	/** Remove edges that satisfy the predicate. */
	template <typename Predicate>
	void remove_edge_if(Predicate predicate)
	{
		unsigned i = 0;
		for (typename Vertices::iterator it = m_vertices.begin();
				it != m_vertices.end(); ++it)
			it->remove_edge_if(vertex(i++), predicate);
	}

	/** Return true if this vertex has been removed. */
	bool is_removed(vertex_descriptor u) const
	{
		vertices_size_type ui = get(vertex_index, *this, u);
		return ui < m_removed.size() ? m_removed[ui] : false;
	}

	/** Set the name (usually contig ID) for a given vertex_descriptor */
	void put(vertex_name_t, vertex_descriptor u, const Dictionary::name_type& name)
	{
		m_vertexNames.put(u, name);
	}

	/** Find a vertex_descriptor by name (usually contig ID) */
	vertex_descriptor find_vertex(const Dictionary::name_type& name) const
	{
		return m_vertexNames.getIndex(name);
	}

  private:
	UndirectedGraph& operator =(const UndirectedGraph& x);

	/** The set of vertices. */
	Vertices m_vertices;

	/** Bidirectional map of names to vertex_descriptors */
	Dictionary m_vertexNames;

	/** Flags indicating vertices that have been removed. */
	std::vector<bool> m_removed;
};

namespace std {
	template <typename VertexProp, typename EdgeProp>
	inline void swap(UndirectedGraph<VertexProp, EdgeProp>& a,
			UndirectedGraph<VertexProp, EdgeProp>& b) { a.swap(b); }
}

// IncidenceGraph

template <typename VP, typename EP>
std::pair<
	typename UndirectedGraph<VP, EP>::out_edge_iterator,
	typename UndirectedGraph<VP, EP>::out_edge_iterator>
out_edges(
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		const UndirectedGraph<VP, EP>& g)
{
	return g.out_edges(u);
}

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::degree_size_type
out_degree(
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		const UndirectedGraph<VP, EP>& g)
{
	return g.out_degree(u);
}

// AdjacencyGraph

template <typename VP, typename EP>
std::pair<
	typename UndirectedGraph<VP, EP>::adjacency_iterator,
	typename UndirectedGraph<VP, EP>::adjacency_iterator>
adjacent_vertices(
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		const UndirectedGraph<VP, EP>& g)
{
	return g.adjacent_vertices(u);
}

// VertexListGraph

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertices_size_type
num_vertices(const UndirectedGraph<VP, EP>& g)
{
	return g.num_vertices();
}

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertex_descriptor
vertex(typename UndirectedGraph<VP, EP>::vertices_size_type ui, const UndirectedGraph<VP, EP>& g)
{
	return g.vertex(ui);
}

template <typename VP, typename EP>
std::pair<typename UndirectedGraph<VP, EP>::vertex_iterator,
	typename UndirectedGraph<VP, EP>::vertex_iterator>
vertices(const UndirectedGraph<VP, EP>& g)
{
	return g.vertices();
}

// EdgeListGraph

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::edges_size_type
num_edges(const UndirectedGraph<VP, EP>& g)
{
	return g.num_edges();
}

template <typename VP, typename EP>
std::pair<typename UndirectedGraph<VP, EP>::edge_iterator,
	typename UndirectedGraph<VP, EP>::edge_iterator>
edges(const UndirectedGraph<VP, EP>& g)
{
	return g.edges();
}

// AdjacencyMatrix

template <typename VP, typename EP>
std::pair<typename UndirectedGraph<VP, EP>::edge_descriptor, bool>
edge(
	typename UndirectedGraph<VP, EP>::vertex_descriptor u,
	typename UndirectedGraph<VP, EP>::vertex_descriptor v,
	const UndirectedGraph<VP, EP>& g)
{
	return g.edge(u, v);
}

// VertexMutableGraph

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertex_descriptor
add_vertex(UndirectedGraph<VP, EP>& g)
{
	return g.add_vertex();
}

template <typename VP, typename EP>
void
remove_vertex(
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		UndirectedGraph<VP, EP>& g)
{
	g.remove_vertex(u);
}

// EdgeMutableGraph

template <typename VP, typename EP>
void
clear_vertex(
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		UndirectedGraph<VP, EP>& g)
{
	g.clear_vertex(u);
}

template <typename VP, typename EP>
std::pair<typename UndirectedGraph<VP, EP>::edge_descriptor, bool>
add_edge(
	typename UndirectedGraph<VP, EP>::vertex_descriptor u,
	typename UndirectedGraph<VP, EP>::vertex_descriptor v,
	UndirectedGraph<VP, EP>& g)
{
	return g.add_edge(u, v);
}

template <typename VP, typename EP>
void
remove_edge(
	typename UndirectedGraph<VP, EP>::vertex_descriptor u,
	typename UndirectedGraph<VP, EP>::vertex_descriptor v,
	UndirectedGraph<VP, EP>& g)
{
	g.remove_edge(u, v);
}

template <typename VP, typename EP>
void
remove_edge(
		typename UndirectedGraph<VP, EP>::edge_descriptor e,
		UndirectedGraph<VP, EP>& g)
{
	g.remove_edge(e);
}

// MutableIncidenceGraph

template <typename VP, typename EP>
void
clear_out_edges(
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		UndirectedGraph<VP, EP>& g)
{
	g.clear_out_edges(u);
}

// MutableEdgeListGraph

template <typename VP, typename EP, class Predicate>
void
remove_edge_if(Predicate predicate, UndirectedGraph<VP, EP>& g)
{
	g.remove_edge_if(predicate);
}

// PropertyGraph

/** Return true if this vertex has been removed. */
template <typename VP, typename EP>
bool get(vertex_removed_t, const UndirectedGraph<VP, EP>& g,
		typename UndirectedGraph<VP, EP>::vertex_descriptor u)
{
	return g.is_removed(u);
}

template <typename VP, typename EP>
void put(vertex_removed_t tag, UndirectedGraph<VP, EP>& g,
		typename UndirectedGraph<VP, EP>::vertex_descriptor u,
		bool flag)
{
	g.put(tag, u, flag);
}

/** Return the properties of the edge of iterator eit. */
template <typename VP, typename EP>
const typename UndirectedGraph<VP, EP>::edge_property_type&
get(edge_bundle_t, const UndirectedGraph<VP, EP>&,
		typename UndirectedGraph<VP, EP>::out_edge_iterator eit)
{
	return eit.get_property();
}

// PropertyGraph

template <typename VP, typename EP>
const VP&
get(vertex_bundle_t, const UndirectedGraph<VP, EP>& g,
		typename UndirectedGraph<VP, EP>::vertex_descriptor u)
{
	return g[u];
}

template <typename VP, typename EP>
const EP&
get(edge_bundle_t, const UndirectedGraph<VP, EP>& g,
		typename UndirectedGraph<VP, EP>::edge_descriptor e)
{
	return g[e];
}

// PropertyGraph vertex_index

#if 0
namespace boost {
template <typename VP, typename EP>
struct property_map<UndirectedGraph<VP, EP>, vertex_index_t>
{
	typedef ContigNodeIndexMap type;
	typedef type const_type;
};
}

template <typename VP, typename EP>
ContigNodeIndexMap
get(vertex_index_t, const UndirectedGraph<VP, EP>&)
{
	return ContigNodeIndexMap();
}

template <typename VP, typename EP>
ContigNodeIndexMap::reference
get(vertex_index_t tag, const UndirectedGraph<VP, EP>& g,
		typename UndirectedGraph<VP, EP>::vertex_descriptor u)
{
	return get(get(tag, g), u);
}
#endif

// VertexMutablePropertyGraph

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertex_descriptor
add_vertex(const VP& vp, UndirectedGraph<VP, EP>& g)
{
	return g.add_vertex(vp);
}

// EdgeMutablePropertyGraph

template <typename VP, typename EP>
std::pair<typename UndirectedGraph<VP, EP>::edge_descriptor, bool>
add_edge(
	typename UndirectedGraph<VP, EP>::vertex_descriptor u,
	typename UndirectedGraph<VP, EP>::vertex_descriptor v,
	const typename UndirectedGraph<VP, EP>::edge_property_type& ep,
	UndirectedGraph<VP, EP>& g)
{
	return g.add_edge(u, v, ep);
}

// NamedGraph

template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertex_descriptor
find_vertex(const std::string& name, const UndirectedGraph<VP, EP>& g)
{
	/* return find_vertex(name, g_contigNames); */
	return g.find_vertex(name);
}

#if 0
template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertex_descriptor
find_vertex(const std::string& name, bool sense,
		const UndirectedGraph<VP, EP>&)
{
	return find_vertex(name, sense, g_contigNames);
}
#endif

/**
 * Get the index of a vertex in UndirectedGraph's
 * internal data structures (vertex list and
 * vertex_descriptor => vertex_name map).
 */
template <typename VP, typename EP>
typename UndirectedGraph<VP, EP>::vertices_size_type
get(vertex_index_t, const UndirectedGraph<VP, EP>&,
	typename UndirectedGraph<VP, EP>::vertex_descriptor u)
{
	/*
	 * For UndirectedGraph, vertex_index and vertex_descriptor
	 * are always the same, where `vertex_index` indicates the position of
	 * the vertex in UndirectedGraph's vertex list (`m_vertices` above)
	 * and also the position of the vertex in the
	 * vertex_name <=> vertex_descriptor map (`m_vertexNames` above).
	 *
	 * For DirectedGraph, vertex_index and vertex_descriptor are
	 * different types (unsigned and ContigNode, respectively), because
	 * vertex names end with "+" or "-".
	 */
	return u;
}

/**
 * Set the name for a vertex.  This is a std::string and usually
 * stores the contig ID.
 */
template <typename VP, typename EP>
void put(vertex_name_t tag, UndirectedGraph<VP, EP>& g,
	typename UndirectedGraph<VP, EP>::vertex_descriptor& u,
	const Dictionary::name_type& name)
{
	g.put(tag, u, name);
}

#endif