قطعه برنامه بررسی مشبکه بودن گراف بهمراه سورس

در قطعه برنامه تهیه شده، مشخصات گراف را در قالب یک ماتریس به برنامه داده و برنامه اعلام می‌کند که این گراف مشبکه هست یا خیر.




تعریف مشبکه در ریاضیات گسسته

مجموعه‌ای با ترتیب جزئی (A, R) را یک مشبکه گویند هرگاه هر زیر مجموعه دو عضوی از این مجموعه دارای LUB یا Least Upper Bound و GLB یا Greatest Lower Bound باشد.


کد برنامه

کد اصلی برنامه کلاس Graph می‌باشد که به صورت زیر پیاده سازی شده است:


فایل Graph.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace LatticeGraph
{
    public class Graph
    {
        private readonly int[,] _matrix;
        private List<List<int>> _lowerPaths;
        private List<List<int>> _upperPaths;
        private List<int> _currentPath;
        private Dictionary<int, int> _nodesLevel;
        private readonly int _nodeCount;

        public Graph(int[,] matrix)
        {
            _matrix = matrix;
            _nodeCount = (int)Math.Sqrt(_matrix.Length);
        }

        public Dictionary<int, int> NodesLevel
        {
            get { return _nodesLevel; }
        }

        public bool IsLattice()
        {
            CalculateNodeLevels();

            for (var i = 0; i < _nodeCount; i++)
            {
                for (var j = 0; j < _nodeCount; j++)
                {
                    if (i == j) continue;
                    var lub = GetLub(i, j);
                    if (!checkLub(lub)) return false;
                    var glb = GetGlb(i, j);
                    if (!checkGlb(glb)) return false;
                }
            }
            return true;
        }

        private bool checkGlb(List<Junction> glb)
        {
            if (glb == null) return false;
            if (glb.Count == 1) return true;

            var glbNodes = glb.Select(x => x.Node).ToList();
            var levels = _nodesLevel.Where(x => glbNodes.Contains(x.Key)).ToList();
            var maxValue = levels.Max(x => x.Value);
            return levels.Count(x => x.Value == maxValue) == 1;
        }

        private bool checkLub(List<Junction> lub)
        {
            if (lub == null) return false;
            if (lub.Count == 1) return true;

            var glbNodes = lub.Select(x => x.Node).ToList();
            var levels = _nodesLevel.Where(x => glbNodes.Contains(x.Key)).ToList();
            var minValue = levels.Min(x => x.Value);
            return levels.Count(x => x.Value == minValue) == 1;
        }

        public void CalculateNodeLevels()
        {
            _nodesLevel = new Dictionary<int, int>();
            for (int i = 0; i < _nodeCount; i++)
            {
                var lowerPaths = LowerPaths(i);
                var maxPath = lowerPaths.Max(x => x.Count);
                _nodesLevel.Add(i, maxPath);
            }
        }

        public List<Junction> GetGlb(int i, int j)
        {
            var iLowerPaths = LowerPaths(i);
            var jLowerPaths = LowerPaths(j);

            var pathJunctions = new List<Junction>();

            foreach (var iPath in iLowerPaths)
            {
                foreach (var jPath in jLowerPaths)
                {
                    for (var x = 0; x < iPath.Count; x++)
                    {
                        var junctionFounded = false;
                        for (var y = 0; y < jPath.Count; y++)
                        {
                            if (iPath[x] != jPath[y]) continue;
                            pathJunctions.Add(new Junction(iPath[x], x));
                            junctionFounded = true;
                            break;
                        }
                        if (junctionFounded)
                        {
                            break;
                        }
                    }
                }
            }

            if (pathJunctions.Count <= 0) return null;
            var minPath = pathJunctions.Min(x => x.PathPartCount);
            return pathJunctions.Where(x => x.PathPartCount == minPath)
                .DistinctBy(d => new { d.Node, d.PathPartCount })
                .ToList();
        }

        public List<List<int>> LowerPaths(int node)
        {
            _lowerPaths = new List<List<int>>();
            _currentPath = new List<int>();
            GetLowerPaths(node);
            return _lowerPaths;
        }

        public void GetLowerPaths(int node)
        {
            if (_currentPath.Count > _nodeCount)
            {
                throw new Exception("به نظر میرسد گراف هاس نمی‌باشد");
            }
            _currentPath.Add(node);

            var childNodes = getChildNodes(node);
            if (childNodes.Count == 0)
            {
                var path = new List<int>(_currentPath);
                _lowerPaths.Add(path);
            }
            else
            {
                foreach (var childNode in childNodes)
                {
                    GetLowerPaths(childNode);
                }
            }
            _currentPath.RemoveAt(_currentPath.Count - 1);
        }

        public List<List<int>> UpperPaths(int node)
        {
            _upperPaths = new List<List<int>>();
            _currentPath = new List<int>();
            GetUpperPaths(node);
            return _upperPaths;
        }

        public void GetUpperPaths(int node)
        {
            if (_currentPath.Count > _nodeCount)
            {
                throw new Exception("به نظر میرسد گراف هاس نمی‌باشد");
            }
            _currentPath.Add(node);

            var parentNodes = getParentNodes(node);
            if (parentNodes.Count == 0)
            {
                var path = new List<int>(_currentPath);
                _upperPaths.Add(path);
            }
            else
            {
                foreach (var parentNode in parentNodes)
                {
                    GetUpperPaths(parentNode);
                }
            }
            _currentPath.RemoveAt(_currentPath.Count - 1);
        }

        private List<int> getChildNodes(int node)
        {
            var result = new List<int>();
            for (var i = node; i < _nodeCount; i++)
            {
                if (i != node && _matrix[i, node] == 1)
                {
                    result.Add(i);
                }
            }
            return result;
        }

        private List<int> getParentNodes(int node)
        {
            var result = new List<int>();
            for (var i = 0; i < _nodeCount; i++)
            {
                if (i != node && _matrix[node, i] == 1)
                {
                    result.Add(i);
                }
            }
            return result;
        }

        public List<Junction> GetLub(int i, int j)
        {
            var iUpperPaths = UpperPaths(i);
            var jUpperPaths = UpperPaths(j);

            var pathJunctions = new List<Junction>();

            foreach (var iPath in iUpperPaths)
            {
                foreach (var jPath in jUpperPaths)
                {
                    for (var x = 0; x < iPath.Count; x++)
                    {
                        var junctionFounded = false;
                        for (var y = 0; y < jPath.Count; y++)
                        {
                            if (iPath[x] != jPath[y]) continue;
                            pathJunctions.Add(new Junction(iPath[x], x));
                            junctionFounded = true;
                            break;
                        }
                        if (junctionFounded)
                        {
                            break;
                        }
                    }
                }
            }

            if (pathJunctions.Count <= 0) return null;
            var minPath = pathJunctions.Min(x => x.PathPartCount);
            return pathJunctions.Where(x => x.PathPartCount == minPath)
                .DistinctBy(d => new { d.Node, d.PathPartCount })
                .ToList();
        }
    }
}


فایل Junction.cs

namespace LatticeGraph
{
    public class Junction
    {
        public Junction(int node, int pathPartCount)
        {
            Node = node;
            PathPartCount = pathPartCount;
        }

        public Junction()
        {
        }

        public int Node { get; set; }
        public int PathPartCount { get; set; }
    }
}


کد آزمون واحد برنامه

using System;
using System.Collections.Generic;
using LatticeGraph;
using NUnit.Framework;

namespace TestProject
{
    [TestFixture]
    public class TestLatticeGraph
    {
        private int[,] _matrix;
        private int[,] _matrix_2;

        [SetUp]
        public void Setup()
        {
            _matrix = new[,]
            {
                {0, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 0, 0},
                {0, 1, 1, 0, 0, 0},
                {0, 0, 0, 1, 1, 0}
            };

            _matrix_2 = new[,]
            {
                {0, 0, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0, 0},
                {1, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 1, 0, 0, 0},
                {0, 0, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 1, 1, 0}
            };
        }

        [Test]
        public void Test_Is_Moshabbakeh()
        {
            var graph = new Graph(_matrix);
            Assert.True(graph.IsLattice());

            _matrix[3, 2] = 1; // Make graph non lattice

            graph = new Graph(_matrix);
            Assert.False(graph.IsLattice());
        }

        [Test]
        public void Test_Get_Lower_Paths()
        {
            var graph = new Graph(_matrix);
            var lowerPaths = graph.LowerPaths(1);
            Assert.AreEqual(2, lowerPaths.Count);
            Assert.AreEqual(3, lowerPaths[0].Count);
            Assert.AreEqual(3, lowerPaths[1].Count);

            Assert.AreEqual(new List<int>() { 1, 3, 5 }, lowerPaths[0]);
            Assert.AreEqual(new List<int>() { 1, 4, 5 }, lowerPaths[1]);

            graph = new Graph(_matrix);
            lowerPaths = graph.LowerPaths(0);
            Assert.AreEqual(3, lowerPaths.Count);

            Assert.AreEqual(new List<int>() { 0, 1, 3, 5 }, lowerPaths[0]);
            Assert.AreEqual(new List<int>() { 0, 1, 4, 5 }, lowerPaths[1]);
            Assert.AreEqual(new List<int>() { 0, 2, 4, 5 }, lowerPaths[2]);
        }

        [Test]
        public void Test_Get_GLB_On_Lattice_Graph()
        {
            var graph = new Graph(_matrix);
            var glb = graph.GetGlb(1, 2);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(4, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);

            glb = graph.GetGlb(2, 1);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(4, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);

            glb = graph.GetGlb(2, 3);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(5, glb[0].Node);
            Assert.AreEqual(2, glb[0].PathPartCount);

            glb = graph.GetGlb(3, 2);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(5, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);

            glb = graph.GetGlb(0, 5);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(5, glb[0].Node);
            Assert.AreEqual(3, glb[0].PathPartCount);
        }

        [Test]
        public void Test_Get_GLB_On_None_Lattice_Graph()
        {
            _matrix[3, 2] = 1; //Make matrix non lattice

            var graph = new Graph(_matrix);
            var glb = graph.GetGlb(1, 2);
            Assert.AreEqual(2, glb.Count);
            Assert.AreEqual(3, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);

            Assert.AreEqual(4, glb[1].Node);
            Assert.AreEqual(1, glb[1].PathPartCount);
        }

        [Test]
        public void Test_Get_Upper_Paths()
        {
            var graph = new Graph(_matrix);
            var upperPaths = graph.UpperPaths(4);
            Assert.AreEqual(2, upperPaths.Count);
            Assert.AreEqual(3, upperPaths[0].Count);
            Assert.AreEqual(3, upperPaths[1].Count);

            Assert.AreEqual(new List<int>() { 4, 1, 0 }, upperPaths[0]);
            Assert.AreEqual(new List<int>() { 4, 2, 0 }, upperPaths[1]);

            graph = new Graph(_matrix);
            upperPaths = graph.UpperPaths(5);
            Assert.AreEqual(3, upperPaths.Count);

            Assert.AreEqual(new List<int>() { 5, 3, 1, 0 }, upperPaths[0]);
            Assert.AreEqual(new List<int>() { 5, 4, 1, 0 }, upperPaths[1]);
            Assert.AreEqual(new List<int>() { 5, 4, 2, 0 }, upperPaths[2]);
        }

        [Test]
        public void Test_Get_LUB_On_Lattice_Graph()
        {
            var graph = new Graph(_matrix);
            var lub = graph.GetLub(3, 4);
            Assert.AreEqual(1, lub.Count);
            Assert.AreEqual(1, lub[0].Node);
            Assert.AreEqual(1, lub[0].PathPartCount);

            lub = graph.GetLub(4, 3);
            Assert.AreEqual(1, lub.Count);
            Assert.AreEqual(1, lub[0].Node);
            Assert.AreEqual(1, lub[0].PathPartCount);

            lub = graph.GetLub(2, 3);
            Assert.AreEqual(1, lub.Count);
            Assert.AreEqual(0, lub[0].Node);
            Assert.AreEqual(1, lub[0].PathPartCount);

            lub = graph.GetLub(0, 5);
            Assert.AreEqual(1, lub.Count);
            Assert.AreEqual(0, lub[0].Node);
            Assert.AreEqual(0, lub[0].PathPartCount);
        }

        [Test]
        public void Test_Get_LUB_On_None_Lattice_Graph()
        {
            _matrix[3, 2] = 1; //Make matrix non lattice

            var graph = new Graph(_matrix);
            var glb = graph.GetLub(3, 4);
            Assert.AreEqual(2, glb.Count);
            Assert.AreEqual(1, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);

            Assert.AreEqual(2, glb[1].Node);
            Assert.AreEqual(1, glb[1].PathPartCount);
        }

        [Test]
        public void Test_Is_Moshabbakeh_2()
        {
            var graph = new Graph(_matrix_2);
            Assert.True(graph.IsLattice());
        }

        [Test]
        public void Test_Get_GLB_On_Lattice_Graph_2()
        {

            var graph = new Graph(_matrix_2);
            var glb = graph.GetGlb(0, 5);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(5, glb[0].Node);
            Assert.AreEqual(2, glb[0].PathPartCount);

            glb = graph.GetGlb(4, 2);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(6, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);

            glb = graph.GetGlb(3, 2);
            Assert.AreEqual(1, glb.Count);
            Assert.AreEqual(5, glb[0].Node);
            Assert.AreEqual(1, glb[0].PathPartCount);
        }

        [Test]
        public void Test_Calculate_Node_level()
        {
            var graph = new Graph(_matrix);
            graph.CalculateNodeLevels();
            Assert.AreEqual(6, graph.NodesLevel.Count);
            int i;
            
            graph.NodesLevel.TryGetValue(5, out i);
            Assert.AreEqual(1, i);

            graph.NodesLevel.TryGetValue(4, out i);
            Assert.AreEqual(2, i);

            graph.NodesLevel.TryGetValue(3, out i);
            Assert.AreEqual(2, i);

            graph.NodesLevel.TryGetValue(2, out i);
            Assert.AreEqual(3, i);

            graph.NodesLevel.TryGetValue(1, out i);
            Assert.AreEqual(3, i);

            graph.NodesLevel.TryGetValue(0, out i);
            Assert.AreEqual(4, i);
        }
    }
}


دریافت فایل

فایل اجرایی برنامه بهمراه نمونه گراف مشبکه


سورس کامل برنامه + آزمون واحد

ارسال نظر

Loading