时间戳

首页 > 解决方案 > 如何获取具有已知边的抽象多边形的顶点

c# - 如何获取具有已知边的抽象多边形的顶点

问题描述

这是对现已删除的问题的重述。我认为这是一个有趣的问题。问题的输入是一个二元元组数组，每个元组代表一条连接两个抽象顶点的抽象边。所需的输出是连接顶点的数组。顶点可以是任何类型，不一定是空间中的点，因此是“抽象”名称。预计不会以任何方式对该数组进行排序。实际上，这些类型甚至没有可比性。我们只允许比较它们是否相等。

输入输出示例：

var input = new[] { ('a', 'b'), ('c', 'b'), ('a', 'c') };
var output = new[] { 'a', 'b', 'c' };

var input = new[] { ("a", "b"), ("a", "b") };
var output = new[] { "a", "b" };

var input = new[] { (true, true) };
var output = new[] { true };

var input = new[] { (1, 2), (4, 3), (3, 2), (1, 4) };
var output = new[] { 1, 2, 3, 4 };

var input = new[] { (1, 2), (2, 3), (3, 4) };
var output = new InvalidDataException(
    "Vertices [1, 4] are not connected with exactly 2 other vertices.");

var input = new[] { (1, 2), (2, 1), (3, 4), (4, 3) };
var output = new InvalidDataException(
    "Vertices [3, 4] are not connected with the rest of the graph.");

方法签名：

public static T[] GetVerticesFromEdges<T>((T, T)[] edges,
    IEqualityComparer<T> comparer);

标签： c#.netalgorithmgraph

解决方案

EqualityComparerExtensions将返回一个值的类，该值指示两条边是否是邻居。

static class EqualityComparerExtensions
{
    internal static bool Neighbours<T>(this IEqualityComparer<T> comparer, 
        Tuple<T, T> a, Tuple<T, T> b)
    {
        return comparer.Equals(a.Item1, b.Item1) 
            || comparer.Equals(a.Item1, b.Item2)
            || comparer.Equals(a.Item2, b.Item1) 
            || comparer.Equals(a.Item2, b.Item2);
    }
}

那么算法将是：

public static T[] GetVerticesFromEdges<T>(Tuple<T, T>[] edges, 
    IEqualityComparer<T> comparer)
{
    var array = edges.Clone() as Tuple<T, T>[];
    var last = array.Length - 1;
    for (int i = 0; i < last; i++)
    {
        var c = 0;
        for (int j = i + 1; j < array.Length; j++)
        {
            if (comparer.Neighbours(array[i], array[j]))
            {
                var t = array[i + 1];
                array[i + 1] = array[j];
                array[j] = t;
                c++;
            }
        }
        if (c > 2 || c == 0)
        {
            throw new ArgumentException($"{nameof(edges)} is not a Polygon!");
        }
    }
    if (!comparer.Neighbours(array[last], array[0]))
    {
        throw new ArgumentException($"{nameof(edges)} is not a Polygon!");
    }
    for (int i = 0, j = 1; j < array.Length; i++, j++)
    {
        if (!comparer.Equals(array[i].Item2, array[j].Item1))
        {
            if (comparer.Equals(array[i].Item2, array[j].Item2))
            {
                array[j] = Tuple.Create(array[j].Item2, array[j].Item1);
            }
            else
            {
                array[i] = Tuple.Create(array[i].Item2, array[i].Item1);
            }
        }
    }
    if (!comparer.Equals(array[last].Item2, array[0].Item1))
    {
        throw new ArgumentException($"{nameof(edges)} is not a Polygon!");
    }
    return array.Select(a => a.Item1).ToArray();
}

推荐阅读