最長パス

最長のパスを求める方法は、 IPに定式化する方法が一般的なようだ。実用的にはその方がいいだろうが、作るのはちょっと面倒だ。以下に全探索する方法を紹介する。計算量は指数オーダなので、複雑なものはできない。

/// <summary>
/// グラフ上の最長路のホップ数を返す
/// (有向アークが含まれていてはいけない)
/// </summary>
public static int GetLongestPath<TN, TA>(Graph<TN, TA> grp)
{
	foreach (ArcTag<TN, TA> at in grp.ArcTags)
		if (at.IsEnable && at.IsDirected) throw new ApplicationException("Exist directed arc");
	bool[] unchk = new bool[grp.ArcsCount]; // 未チェックのアークか
	int[] degree = new int[grp.NodesCount]; // ノードの次数
	foreach (ArcTag<TN, TA> at in grp.ArcTags)
	{
		if (unchk[at.Index] = (at.IsEnable && at.LeftTag.IsEnable && at.RightTag.IsEnable))
		{
			++degree[at.LeftID];
			++degree[at.RightID];
		}
	}
	List<GLPData> dt = new List<GLPData>(); // 次数が2のノードを縮約した後のリンクの集合
	GLPData gd = new GLPData();
	Dictionary<int, int> dic = new Dictionary<int, int>(); // ノードIndex→縮約後のノードIndex
	// 縮約する
	while (true)
	{
		ArcTag<TN, TA> fnd = null, fst = null;
		for (int i = 0; i < grp.ArcsCount; ++i)
		{
			if (!unchk[i]) continue;
			ArcTag<TN, TA> at = grp.ArcTag(i);
			if (fst == null) fst = at;
			if (degree[at.LeftID] == 2 && degree[at.RightID] == 2) continue;
			fnd = at;
			break;
		}
		if (fnd == null && (fnd = fst) == null) break;
		// 縮約後のノード数が31以上なら求められない
		if (dt.Count >= 31) throw new ApplicationException("Too complex");
		NodeTag<TN, TA> nt = degree[fnd.RightID] != 2 ? fnd.RightTag : fnd.LeftTag;
		gd.len = 0;
		gd.node1 = GetIndex(dic, nt.Index);
		while (true)
		{
			unchk[fnd.Index] = false;
			++gd.len;
			nt = grp.NodeTag(fnd.AnotherID(nt.Index));
			if (degree[nt.Index] != 2) break;
			foreach (ArcTag<TN, TA> act in nt.InArcTags)
			{
				if (act.IsEnable && act != fnd)
				{
					fnd = act;
					break;
				}
			}
			if (!unchk[fnd.Index]) break;
		}
		gd.node2 = GetIndex(dic, nt.Index);
		dt.Add(gd);
	}
	if (dt.Count == 0) return 0;
	int[] con = new int[dic.Count]; // 縮約後のノードの次数
	int[] src = new int[dic.Count]; // 0:非対象、1:未チェック、2:チェック済み
	bool[] bUse = new bool[dt.Count]; // 縮約後のリンクのON/OFF
	int max = 0, cur = 0, odd = 0;
	uint n = 1U << dt.Count;
	// リンクのON/OFFの全組合せをチェック
	for (uint i = 0; i < n - 1; ++i)
	{
		int k = (int)Math.Log((i | ~(~i - 1)) - i, 2);
		gd = dt[k];
		int sgn = (bUse[k] = !bUse[k]) ? 1 : -1;
		cur += sgn * gd.len;
		odd += (con[gd.node1] += sgn) % 2 == 0 ? -1 : 1;
		odd += (con[gd.node2] += sgn) % 2 == 0 ? -1 : 1;
		// 次数が奇数の数が3以上なら一筆書きでない
		if (odd > 2 || cur <= max) continue;
		// 連結性のチェック
		bool bFound = false;
		for (int h = 0; h < src.Length; ++h)
		{
			src[h] = con[h] == 0 ? 0 : (bFound ? 1 : 2);
			if (src[h] > 0) bFound = true;
		}
		while (bFound)
		{
			bFound = false;
			foreach (GLPData gld in dt)
			{
				if (src[gld.node1] + src[gld.node2] == 3)
				{
					bFound = true;
					src[gld.node1] = src[gld.node2] = 2;
				}
			}
		}
		for (int h = 0; h < src.Length; ++h)
			if (bFound = src[h] == 1) break;
		if (!bFound) max = cur;
	}
	return max;
}
private struct GLPData
{
	public int len;
	public int node1;
	public int node2;
}
private static int GetIndex(Dictionary<int, int> dic, int i)
{
	int k;
	if (!dic.TryGetValue(i, out k))
		dic.Add(i, k = dic.Count);
	return k;
}