Function addMissingEdges

MergePaths/MergePaths.cpp:631–669

Add missing overlap edges. For each vertex u with at least two * outgoing edges, (u,v1) and (u,v2), add the edge (v1,v2) if v1 < v2, * and add the edge (v2,v1) if v2 < v1. */

 * and add the edge (v2,v1) if v2 < v1.
 */
static void
addMissingEdges(const Lengths& lengths, PathGraph& g, const ContigPathMap& paths)
{
	typedef graph_traits<PathGraph>::adjacency_iterator Vit;
	typedef graph_traits<PathGraph>::vertex_iterator Uit;
	typedef graph_traits<PathGraph>::vertex_descriptor V;

	unsigned numAdded = 0;
	pair<Uit, Uit> urange = vertices(g);
	for (Uit uit = urange.first; uit != urange.second; ++uit) {
		V u = *uit;
		if (out_degree(u, g) < 2)
			continue;
		pair<Vit, Vit> vrange = adjacent_vertices(u, g);
		for (Vit vit1 = vrange.first; vit1 != vrange.second;) {
			V v1 = *vit1;
			++vit1;
			assert(v1 != u);
			ContigPath path1 = getPath(paths, v1);
			if (find(path1.begin(), path1.end(), ContigPath::value_type(u)) == path1.end())
				continue;
			for (Vit vit2 = vit1; vit2 != vrange.second; ++vit2) {
				V v2 = *vit2;
				assert(v2 != u);
				assert(v1 != v2);
				if (edge(v1, v2, g).second || edge(v2, v1, g).second)
					continue;
				ContigPath path2 = getPath(paths, v2);
				if (find(path2.begin(), path2.end(), ContigPath::value_type(u)) == path2.end())
					continue;
				numAdded += addOverlapEdge(lengths, g, u, v1, path1, v2, path2);
			}
		}
	}
	if (opt::verbose > 0)
		cout << "Added " << numAdded << " missing edges.\n";
	if (!opt::db.empty())
		addToDb(db, "addedMissingEdges", numAdded);
}

/** Remove transitive edges. */
static void