Проверьте, связан ли списоксодержит определенный узел - PullRequest
Новая
       6

Проверьте, связан ли списоксодержит определенный узел

0 голосов
/ 02 декабря 2018

Я реализую График, используя c #, и я хочу проверить, вставил ли я одно и то же ребро дважды, чтобы я мог выбросить исключение при этом.

Мой класс называется Graph

Вот мое объявление _adjacencyList 

 protected virtual Dictionary<T, LinkedList<Node<T>>> _adjacencyList { get; set; }

Вот мой класс узла 

 class Node<T> where T : IComparable<T>
{
    public double speed { get; set; }
    public double time { get; set; }
    public double distance { get; set; }
    public T source { get; set; }
    public T destenation { get; set; }

    public Node() { }
    public Node(T SOURCE, T DESTENATION, double SPEED, double DISTANCE)
    {
        this.source = SOURCE;
        this.destenation = DESTENATION;
        this.speed = SPEED;
        this.distance = DISTANCE;
        this.time = this.distance / this.speed;
    }
}

Вот моя функция addEdge, которая принимает исходную вершину и конечную вершину, а также значения "Weight" из Edge 

public void addEdge(T source, T Destenation, double speed, double Distance)
    {
        if (_adjacencyList.Count <= 0)
        {
            throw new InvalidOperationException("addEdge: There are no Vertices in Graph.\n");
        }
        else
        {
            if (_adjacencyList.ContainsKey(source) && _adjacencyList.ContainsKey(Destenation))
            {
                var sourceEdge = new Node<T>(source, Destenation, speed, Distance);
                var destenationEdge = new Node<T>(Destenation, source, speed, Distance);

                if (_adjacencyList[source].Contains(sourceEdge) || _adjacencyList[Destenation].Contains(destenationEdge))
                {
                    throw new InvalidOperationException("addEdge: Edge already exists in Graph.\n");
                }
                else
                {
                    _adjacencyList[source].AddLast(sourceEdge);
                    _adjacencyList[Destenation].AddLast(destenationEdge);

                    ++_edgeCount;
                }


            }
            else
            {
                throw new NullReferenceException("addEdge : Source or Destenation Vetrtex Don't Exist in Graph.\n");
            }
        }

    }

Когда я пишу этот код в main, он не выдает исключение «Edge уже существует в Graph». 

   Graph<int> g = new Graph<int>();
        g.addVertex(1);
        g.addVertex(2);
        g.addVertex(3);
        g.addVertex(4);
        g.addEdge(1,2,15.0,60.0);//Multiple Edge
        g.addEdge(1, 2, 15.0, 60.0);//Multiple Edge
        g.addEdge(1, 3, 5.0, 40.0);
        g.addEdge(2,3,1.0,10.0);
        g.addEdge(4,1,2.0,8.0);

Что не так с моей реализацией и как ее исправить

Ответы [ 2 ]

0 голосов
/ 02 декабря 2018

Причина действительно в том, что вы не реализовали метод Equals для класса Node, я здесь также, чтобы объяснить, почему.

Чтобы понять, зачем вам нужен метод Equals, вам нужно понять, какКласс LinkedList работает, что довольно просто, вы просто добавляете, а затем удаляете в нем объекты типа Node.Пока все хорошо, но когда вы используете этот объект в этом блоке кода
if (_adjacencyList[source].Contains(sourceEdge) ...) { throw new InvalidOperationException("addEdge: Edge already exists in Graph.\n"); }
, вы вызываете метод Contains.Теперь ваш объект LinkedList должен просмотреть данные, которые он содержит, и попытаться сравнить, если данная запись уже есть в списке, к сожалению, нигде не упоминается, как это сделать, поэтому он не знает, что делать.Хорошо, что люди, которые создали LinkedLists, подумали об этом и сказали: давайте найдем общий способ проверить, равны ли два объекта любого типа данных, и так родился знаменитый метод Equals.
Теперь вы имеете право наскажем, подожди минутку, разве Равные не определены по умолчанию для каждого класса?Ну, вы абсолютно правы, это так, но в некотором смысле неправильная реализация dafault метода Equals для нас бесполезна, поскольку он проверяет ссылки на объекты и сравнивает их.Даже если вы создадите 2 объекта с одинаковыми данными, у них будут разные ссылки, и метод Equals на них не будет работать (очевидно).

При переходе к истории связанного списка, связанный список будет использовать реализацию по умолчаниюметода Equals, который не работает, и поэтому вы пропустите случай с несколькими ребрами.

0 голосов
/ 02 декабря 2018

Это происходит потому, что вы забыли переопределить метод Equals для класса Node.

Вам нужно что-то вроде следующей реализации: 

public class Edge<T> 
{
    public double Speed { get; }
    public double Time { get; }
    public double Distance { get; }
    public T Source { get; }
    public T Destination { get; }

    public Edge(T source, T destination, double speed, double distance)
    {
        if (source == null) throw new ArgumentNullException(nameof(source));
        if (destination == null) throw new ArgumentNullException(nameof(destination));
        if (Math.Abs(speed) < 1E-9) throw new ArgumentException("speed must greater than zero", nameof(speed));
        if (Math.Abs(distance) < 1E-9) throw new ArgumentException("distance must greater than zero", nameof(speed));

        Source = source;
        Destination = destination;
        Speed = speed;
        Distance = distance;
        Time = Distance / Speed;
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Edge<T> objAsEdgeT))
        {
            return false;
        }

        return Math.Abs(Speed - objAsNodeT.Speed) < 1E-9
               && Math.Abs(Time - objAsNodeT.Time) < 1E-9
               && Source.Equals(objAsNodeT.Source)
               && Destination.Equals(objAsNodeT.Destination);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash*7) + Speed.GetHashCode();
            hash = (hash*7) + Time.GetHashCode();
            hash = (hash*7) + Source.GetHashCode();
            hash = (hash*7) + Destination.GetHashCode();
            return hash;
        }
    }
}

Некоторые примечания:

  • Именование имеет первостепенное значение.Класс Node представляет по существу ребро.Так что Edge будет более подходящим именем класса.Подумайте об обратном: насколько трудно будет кому-то прочитать и действительно понять фрагмент кода, связанный с узлами графа, и выбранное нами имя является краем.
  • Попробуйте использовать общие стили кодирования, чтобы ваш код был более читабельным.Например, для свойств мы используем Pascal Case .
  • В этом случае вам не нужны публичные сеттеры.
  • Вам не нужен конструктор по умолчанию.Что бы означало, что кто-то звонит new Edge<int>()?Не говоря уже о том, что вы получите исключение, поскольку все свойства получат соответствующие значения по умолчанию (double -> 0), а разделение Distance / Speed ​​приведет к разделению с нулем ...
  • Внутри конструктора мыдолжны убедиться, что значения, которые мы получаем, имеют смысл.Иначе в лучшем случае у нас будет объект в бессмысленном состоянии.У нас не может быть ребра без узлов!Так что null не является допустимым значением ни для источника, ни для пункта назначения.Кроме того, distance и speed должны быть больше нуля.Даже если бы speed имело какое-то значение, разделение distance и speed было бы бессмысленным, не говоря уже об исключении ...
...