<commit_before>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using YAGLi.EdgeComparers;
using YAGLi.Interfaces;

namespace YAGLi
{
    /// <summary>
    /// The class <see cref="UndirectedGraph{TVertex}"/> models graph in which edges have no direction.
    /// The edge (x -- y) is equal to the edge (y -- x).
    /// </summary>
    /// <typeparam name="TVertex">The type of the vertex that the graph store.</typeparam>
    public class UndirectedGraph<TVertex> : IModelAUndirectedGraph<TVertex>
    {
        #region Instance fields
        /// <summary>
        /// Readonly field who store the incident edges of each vertex contained in this instance.
        /// </summary>
        private readonly IReadOnlyDictionary<TVertex, IEnumerable<Edge<TVertex>>> _incidentEdges;

        /// <summary>
        /// Readonly field who store the incident vertices of each vertex contained in this instance.
        /// </summary>
        private readonly IReadOnlyDictionary<Edge<TVertex>, IEnumerable<TVertex>> _incidentVertices;

        /// <summary>
        /// Readonly field who hold the edge comparison logic specific of this instance.
        /// </summary>
        private readonly IEqualityComparer<Edge<TVertex>> _edgesComparer;

        /// <summary>
        /// Readonly field who store the object who hold the comparison logic for the vertices.
        /// </summary>
        private readonly IEqualityComparer<TVertex> _verticesComparer;
        #endregion

        #region Constructors
        public UndirectedGraph(bool allowLoops, bool allowParallelEdges) : this(allowLoops, allowParallelEdges, EqualityComparer<TVertex>.Default) { }

        public UndirectedGraph(bool allowLoops, bool allowParallelEdges, IEqualityComparer<TVertex> verticesComparer) : this(allowLoops, allowParallelEdges, Enumerable.Empty<Edge<TVertex>>(), Enumerable.Empty<TVertex>(), verticesComparer) { }

        public UndirectedGraph(bool allowLoops, bool allowParallelEdges, IEnumerable<Edge<TVertex>> edges, IEnumerable<TVertex> vertices) : this(allowLoops, allowParallelEdges, edges, vertices, EqualityComparer<TVertex>.Default) { }

        public UndirectedGraph(bool allowLoops, bool allowParallelEdges, IEnumerable<Edge<TVertex>> edges, IEnumerable<TVertex> vertices, IEqualityComparer<TVertex> verticesComparer)
        {
            AllowLoops = allowLoops;
            AllowParallelEdges = allowParallelEdges;

            if (AllowParallelEdges)
            {
                _edgesComparer = new IgnoreDirectionAndAllowParallelEdges<TVertex>(verticesComparer);
            }
            else
            {
                _edgesComparer = new IgnoreDirectionAndDisallowParallelEdges<TVertex>(verticesComparer);
            }

            _verticesComparer = verticesComparer;

            var incidentEdges = new Dictionary<TVertex, IList<Edge<TVertex>>>(_verticesComparer);
            var incidentVertices = new Dictionary<Edge<TVertex>, IEnumerable<TVertex>>(_edgesComparer);

            var distinctEdges = AllowParallelEdges ? edges : edges.Distinct(_edgesComparer);

            foreach (var edge in (!AllowLoops ? distinctEdges.Where(edge => !_verticesComparer.Equals(edge.End1, edge.End2)) : distinctEdges))
            {
                var distinctEnds = new TVertex[] { edge.End1, edge.End2 }.Distinct();

                foreach (var end in distinctEnds)
                {
                    if (!incidentEdges.ContainsKey(end))
                    {
                        incidentEdges[end] = new List<Edge<TVertex>>();
                    }

                    incidentEdges[end].Add(edge);
                }

                incidentVertices[edge] = distinctEnds;
            }

            foreach (var vertex in vertices.Where(vertex => !incidentEdges.ContainsKey(vertex)))
            {
                incidentEdges.Add(vertex, new List<Edge<TVertex>>(0));
            }

            _incidentEdges = incidentEdges.ToDictionary(x => x.Key, x => x.Value.AsEnumerable(), _verticesComparer);
            _incidentVertices = incidentVertices.ToDictionary(x => x.Key, x => x.Value.AsEnumerable(), _edgesComparer);
        }
        #endregion

        #region Properties
        public bool AllowLoops { get; }

        public bool AllowParallelEdges { get; }
        #endregion

        #region Methods
        public IEnumerable<Edge<TVertex>> Edges
        {
            get
            {
                return _incidentVertices.Keys;
            }
        }

        public IEnumerable<TVertex> Vertices
        {
            get
            {
                return _incidentEdges.Keys;
            }
        }

        public IEnumerable<Edge<TVertex>> AdjacentEdgesOf(Edge<TVertex> edge)
        {
            if (!ContainsEdge(edge))
            {
                return Enumerable.Empty<Edge<TVertex>>();
            }

            return Edges.Where(x => !_edgesComparer.Equals(edge, x) && Edge<TVertex>.AreAdjacent(x, edge, _verticesComparer));
        }

        public IEnumerable<TVertex> AdjacentVerticesOf(TVertex vertex)
        {
            if (!ContainsVertex(vertex))
            {
                return Enumerable.Empty<TVertex>();
            }

            return _incidentEdges[vertex].SelectMany(edge => new TVertex[] { edge.End1, edge.End2 }).Where(v => !_verticesComparer.Equals(v, vertex));
        }

        public UndirectedGraph<TVertex> AddEdge(Edge<TVertex> edge)
        {
            return AddEdges(Enumerable.Repeat(edge, 1));
        }

        public UndirectedGraph<TVertex> AddEdgeAndVertices(Edge<TVertex> edge)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges.Concat(Enumerable.Repeat(edge, 1)), Vertices, _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddEdges(IEnumerable<Edge<TVertex>> edges)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges.Concat(edges.Where(edge => ContainsVertices(edge.End1, edge.End2))), Vertices, _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddEdges(params Edge<TVertex>[] edges)
        {
            return AddEdges(edges.AsEnumerable());
        }

        public UndirectedGraph<TVertex> AddVertex(TVertex vertex)
        {
            return AddVertices(Enumerable.Repeat(vertex, 1));
        }

        public UndirectedGraph<TVertex> AddEdgesAndVertices(IEnumerable<Edge<TVertex>> edges)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges.Concat(edges), Vertices, _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddEdgesAndVertices(params Edge<TVertex>[] edges)
        {
            return AddEdgesAndVertices(edges.AsEnumerable());
        }

        public UndirectedGraph<TVertex> AddVertices(IEnumerable<TVertex> vertices)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges, Vertices.Concat(vertices), _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddVertices(params TVertex[] vertices)
        {
            return AddVertices(vertices.AsEnumerable());
        }

        public bool AreEdgesAdjacent(Edge<TVertex> edge1, Edge<TVertex> edge2)
        {
            if (!ContainsEdges(edge1, edge2))
            {
                return false;
            }

            return Edge<TVertex>.AreAdjacent(edge1, edge2, _verticesComparer);
        }

        public bool AreVerticesAdjacent(TVertex vertex1, TVertex vertex2)
        {
            var referenceVertex = new Edge<TVertex>(vertex1, vertex2);

            return Edges.Contains(referenceVertex, new IgnoreDirectionAndDisallowParallelEdges<TVertex>(_verticesComparer));
        }

        public bool ContainsEdge(Edge<TVertex> edge)
        {
            return _incidentVertices.ContainsKey(edge);
        }

        public bool ContainsEdges(params Edge<TVertex>[] edges)
        {
            return ContainsEdges(edges.AsEnumerable());
        }

        public bool ContainsEdges(IEnumerable<Edge<TVertex>> edges)
        {
            return edges.All(ContainsEdge);
        }

        public bool ContainsVertex(TVertex vertex)
        {
            return _incidentEdges.ContainsKey(vertex);
        }

        public bool ContainsVertices(params TVertex[] vertices)
        {
            return ContainsVertices(vertices.AsEnumerable());
        }

        public bool ContainsVertices(IEnumerable<TVertex> vertices)
        {
            return vertices.All(ContainsVertex);
        }

        public int DegreeOf(TVertex vertex)
        {
            if (!ContainsVertex(vertex))
            {
                return -1;
            }

            return _incidentEdges[vertex].Sum(edge => _verticesComparer.Equals(edge.End1, edge.End2) ? 2 : 1);
        }

        public bool Equals(IModelAUndirectedGraph<TVertex> other)
        {
            if (ReferenceEquals(other, null))
            {
                return false;
            }

            if (ReferenceEquals(other, this))
            {
                return true;
            }

            if (AllowLoops != other.AllowLoops
                || AllowParallelEdges != other.AllowParallelEdges
                || !Edges.IsEquivalent(other.Edges, new IgnoreDirectionAndDisallowParallelEdges<TVertex>(_verticesComparer))
                || !Vertices.IsEquivalent(other.Vertices, _verticesComparer))
            {
                return false;
            }

            return true;
        }

        public bool Equals(IModelAGraph<TVertex> other)
        {
            return Equals(other as IModelAUndirectedGraph<TVertex>);
        }

        public override bool Equals(object other)
        {
            return Equals(other as IModelAUndirectedGraph<TVertex>);
        }

        public override int GetHashCode()
        {
            var hash = 101;

            hash = hash * 107 + AllowLoops.GetHashCode();
            hash = hash * 107 + AllowParallelEdges.GetHashCode();

            foreach (var edgeHashing in Edges.Select(edge => _edgesComparer.GetHashCode(edge)).OrderBy(x => x))
            {
                hash = hash * 107 + edgeHashing;
            }

            foreach (var vertexHashing in Vertices.Select(vertex => _verticesComparer.GetHashCode(vertex)).OrderBy(x => x))
            {
                hash = hash * 107 + vertexHashing;
            }

            return hash;
        }

        public IEnumerable<Edge<TVertex>> IncidentEdgesOf(TVertex vertex)
        {
            if (!ContainsVertex(vertex))
            {
                return Enumerable.Empty<Edge<TVertex>>();
            }

            return _incidentEdges[vertex];
        }

        public IEnumerable<TVertex> IncidentVerticesOf(Edge<TVertex> edge)
        {<commit_msg>Refactoring<commit_after>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using YAGLi.EdgeComparers;
using YAGLi.Interfaces;

namespace YAGLi
{
    /// <summary>
    /// The class <see cref="UndirectedGraph{TVertex}"/> models graph in which edges have no direction.
    /// The edge (x -- y) is equal to the edge (y -- x).
    /// </summary>
    /// <typeparam name="TVertex">The type of the vertex that the graph store.</typeparam>
    public class UndirectedGraph<TVertex> : IModelAUndirectedGraph<TVertex>
    {
        #region Constants
        private const int UNDIRECTED_GRAPHS_HASH_BASE = 101;
        private const int UNDIRECTED_GRAPHS_HASH_FACTOR = 107;
        #endregion

        #region Instance fields
        /// <summary>
        /// Readonly field who store the incident edges of each vertex contained in this instance.
        /// </summary>
        private readonly IReadOnlyDictionary<TVertex, IEnumerable<Edge<TVertex>>> _incidentEdges;

        /// <summary>
        /// Readonly field who store the incident vertices of each vertex contained in this instance.
        /// </summary>
        private readonly IReadOnlyDictionary<Edge<TVertex>, IEnumerable<TVertex>> _incidentVertices;

        /// <summary>
        /// Readonly field who hold the edge comparison logic specific of this instance.
        /// </summary>
        private readonly IEqualityComparer<Edge<TVertex>> _edgesComparer;

        /// <summary>
        /// Readonly field who store the object who hold the comparison logic for the vertices.
        /// </summary>
        private readonly IEqualityComparer<TVertex> _verticesComparer;
        #endregion

        #region Constructors
        public UndirectedGraph(bool allowLoops, bool allowParallelEdges) : this(allowLoops, allowParallelEdges, EqualityComparer<TVertex>.Default) { }

        public UndirectedGraph(bool allowLoops, bool allowParallelEdges, IEqualityComparer<TVertex> verticesComparer) : this(allowLoops, allowParallelEdges, Enumerable.Empty<Edge<TVertex>>(), Enumerable.Empty<TVertex>(), verticesComparer) { }

        public UndirectedGraph(bool allowLoops, bool allowParallelEdges, IEnumerable<Edge<TVertex>> edges, IEnumerable<TVertex> vertices) : this(allowLoops, allowParallelEdges, edges, vertices, EqualityComparer<TVertex>.Default) { }

        public UndirectedGraph(bool allowLoops, bool allowParallelEdges, IEnumerable<Edge<TVertex>> edges, IEnumerable<TVertex> vertices, IEqualityComparer<TVertex> verticesComparer)
        {
            AllowLoops = allowLoops;
            AllowParallelEdges = allowParallelEdges;

            _edgesComparer = AllowParallelEdges ? new IgnoreDirectionAndAllowParallelEdges<TVertex>(verticesComparer) as IEqualityComparer<Edge<TVertex>> : new IgnoreDirectionAndDisallowParallelEdges<TVertex>(verticesComparer);

            _verticesComparer = verticesComparer;

            var incidentEdges = new Dictionary<TVertex, IList<Edge<TVertex>>>(_verticesComparer);
            var incidentVertices = new Dictionary<Edge<TVertex>, IEnumerable<TVertex>>(_edgesComparer);

            var distinctEdges = AllowParallelEdges ? edges : edges.Distinct(_edgesComparer);

            foreach (var edge in (!AllowLoops ? distinctEdges.Where(edge => !_verticesComparer.Equals(edge.End1, edge.End2)) : distinctEdges))
            {
                var distinctEnds = new TVertex[] { edge.End1, edge.End2 }.Distinct();

                foreach (var end in distinctEnds)
                {
                    if (!incidentEdges.ContainsKey(end))
                    {
                        incidentEdges[end] = new List<Edge<TVertex>>();
                    }

                    incidentEdges[end].Add(edge);
                }

                incidentVertices[edge] = distinctEnds;
            }

            foreach (var vertex in vertices.Where(vertex => !incidentEdges.ContainsKey(vertex)))
            {
                incidentEdges.Add(vertex, new List<Edge<TVertex>>(0));
            }

            _incidentEdges = incidentEdges.ToDictionary(x => x.Key, x => x.Value.AsEnumerable(), _verticesComparer);
            _incidentVertices = incidentVertices.ToDictionary(x => x.Key, x => x.Value.AsEnumerable(), _edgesComparer);
        }
        #endregion

        #region Properties
        public bool AllowLoops { get; }

        public bool AllowParallelEdges { get; }
        #endregion

        #region Methods
        public IEnumerable<Edge<TVertex>> Edges
        {
            get
            {
                return _incidentVertices.Keys;
            }
        }

        public IEnumerable<TVertex> Vertices
        {
            get
            {
                return _incidentEdges.Keys;
            }
        }

        public IEnumerable<Edge<TVertex>> AdjacentEdgesOf(Edge<TVertex> edge)
        {
            if (!ContainsEdge(edge))
            {
                return Enumerable.Empty<Edge<TVertex>>();
            }

            return Edges.Where(x => !_edgesComparer.Equals(edge, x) && Edge<TVertex>.AreAdjacent(x, edge, _verticesComparer));
        }

        public IEnumerable<TVertex> AdjacentVerticesOf(TVertex vertex)
        {
            if (!ContainsVertex(vertex))
            {
                return Enumerable.Empty<TVertex>();
            }

            return _incidentEdges[vertex].SelectMany(edge => new TVertex[] { edge.End1, edge.End2 }).Where(v => !_verticesComparer.Equals(v, vertex));
        }

        public UndirectedGraph<TVertex> AddEdge(Edge<TVertex> edge)
        {
            return AddEdges(Enumerable.Repeat(edge, 1));
        }

        public UndirectedGraph<TVertex> AddEdgeAndVertices(Edge<TVertex> edge)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges.Concat(Enumerable.Repeat(edge, 1)), Vertices, _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddEdges(IEnumerable<Edge<TVertex>> edges)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges.Concat(edges.Where(edge => ContainsVertices(edge.End1, edge.End2))), Vertices, _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddEdges(params Edge<TVertex>[] edges)
        {
            return AddEdges(edges.AsEnumerable());
        }

        public UndirectedGraph<TVertex> AddVertex(TVertex vertex)
        {
            return AddVertices(Enumerable.Repeat(vertex, 1));
        }

        public UndirectedGraph<TVertex> AddEdgesAndVertices(IEnumerable<Edge<TVertex>> edges)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges.Concat(edges), Vertices, _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddEdgesAndVertices(params Edge<TVertex>[] edges)
        {
            return AddEdgesAndVertices(edges.AsEnumerable());
        }

        public UndirectedGraph<TVertex> AddVertices(IEnumerable<TVertex> vertices)
        {
            return new UndirectedGraph<TVertex>(AllowLoops, AllowParallelEdges, Edges, Vertices.Concat(vertices), _verticesComparer);
        }

        public UndirectedGraph<TVertex> AddVertices(params TVertex[] vertices)
        {
            return AddVertices(vertices.AsEnumerable());
        }

        public bool AreEdgesAdjacent(Edge<TVertex> edge1, Edge<TVertex> edge2)
        {
            if (!ContainsEdges(edge1, edge2))
            {
                return false;
            }

            return Edge<TVertex>.AreAdjacent(edge1, edge2, _verticesComparer);
        }

        public bool AreVerticesAdjacent(TVertex vertex1, TVertex vertex2)
        {
            var referenceVertex = new Edge<TVertex>(vertex1, vertex2);

            return Edges.Contains(referenceVertex, new IgnoreDirectionAndDisallowParallelEdges<TVertex>(_verticesComparer));
        }

        public bool ContainsEdge(Edge<TVertex> edge)
        {
            return _incidentVertices.ContainsKey(edge);
        }

        public bool ContainsEdges(params Edge<TVertex>[] edges)
        {
            return ContainsEdges(edges.AsEnumerable());
        }

        public bool ContainsEdges(IEnumerable<Edge<TVertex>> edges)
        {
            return edges.All(ContainsEdge);
        }

        public bool ContainsVertex(TVertex vertex)
        {
            return _incidentEdges.ContainsKey(vertex);
        }

        public bool ContainsVertices(params TVertex[] vertices)
        {
            return ContainsVertices(vertices.AsEnumerable());
        }

        public bool ContainsVertices(IEnumerable<TVertex> vertices)
        {
            return vertices.All(ContainsVertex);
        }

        public int DegreeOf(TVertex vertex)
        {
            if (!ContainsVertex(vertex))
            {
                return -1;
            }

            return _incidentEdges[vertex].Sum(edge => _verticesComparer.Equals(edge.End1, edge.End2) ? 2 : 1);
        }

        public bool Equals(IModelAUndirectedGraph<TVertex> other)
        {
            if (ReferenceEquals(other, null))
            {
                return false;
            }

            if (ReferenceEquals(other, this))
            {
                return true;
            }

            if (AllowLoops != other.AllowLoops
                || AllowParallelEdges != other.AllowParallelEdges
                || !Edges.IsEquivalent(other.Edges, new IgnoreDirectionAndDisallowParallelEdges<TVertex>(_verticesComparer))
                || !Vertices.IsEquivalent(other.Vertices, _verticesComparer))
            {
                return false;
            }

            return true;
        }

        public bool Equals(IModelAGraph<TVertex> other)
        {
            return Equals(other as IModelAUndirectedGraph<TVertex>);
        }

        public override bool Equals(object other)
        {
            return Equals(other as IModelAUndirectedGraph<TVertex>);
        }

        public override int GetHashCode()
        {
            var hash = UNDIRECTED_GRAPHS_HASH_BASE;

            hash = hash * UNDIRECTED_GRAPHS_HASH_FACTOR + AllowLoops.GetHashCode();
            hash = hash * UNDIRECTED_GRAPHS_HASH_FACTOR + AllowParallelEdges.GetHashCode();
            hash = Edges.Select(_edgesComparer.GetHashCode).OrderBy(x => x).Aggregate(hash, (x, y) => x * UNDIRECTED_GRAPHS_HASH_FACTOR + y);
            return Vertices.Select(_verticesComparer.GetHashCode).OrderBy(x => x).Aggregate(hash, (x, y) => x * UNDIRECTED_GRAPHS_HASH_FACTOR + y);
        }

        public IEnumerable<Edge<TVertex>> IncidentEdgesOf(TVertex vertex)
        {
            if (!ContainsVertex(vertex))
            {
                return Enumerable.Empty<Edge<TVertex>>();
            }

            return _incidentEdges[vertex];
        }

        public IEnumerable<TVertex> IncidentVerticesOf(Edge<TVertex> edge)
        {
{'fraction_non_alphanumeric': 0.09352252833317977, 'fraction_numerical': 0.003455265825117479, 'mean_word_length': 2.2529596882961185, 'pattern_counts': {'":': 0, '<': 211, '<?xml version=': 0, '>': 241, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5082055', 'n_tokens_mistral': 6061, 'n_tokens_neox': 5875, 'n_words': 1172}