첨부 실행 코드는 나눔고딕코딩 폰트를 사용합니다.
유용한 소스 코드가 있으면 icodebroker@naver.com으로 보내주시면 감사합니다.
블로그 자료는 자유롭게 사용하세요.

728x90
반응형

■ 네트워크 최단거리 경로 찾기

------------------------------------------------------------------------------------------------------------------------


TestProject.zip


NodeStatus.cs

 

 

namespace TestProject

{

    /// <summary>

    /// 노드 상태

    /// </summary>

    public enum NodeStatus

    {

        /// <summary>

        /// 리스트에 없음

        /// </summary>

        NotInList,

 

        /// <summary>

        /// 리스트에 있었음

        /// </summary>

        WasInList,

 

        /// <summary>

        /// 리스트에 있음

        /// </summary>

        NowInList

    }

}

 

 

Node.cs

 

 

using System.Collections.Generic;

using System.Drawing;

 

namespace TestProject

{

    /// <summary>

    /// 노드

    /// </summary>

    public class Node

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region Field

 

        /// <summary>

        /// 노드 ID

        /// </summary>

        public int ID;

 

        /// <summary>

        /// 노드 위치

        /// </summary>

        public Point Location;

 

        /// <summary>

        /// 링크 딕셔너리

        /// </summary>

        public Dictionary<int, Link> LinkDictionary = new Dictionary<int, Link>();

 

        /// <summary>

        /// 거리

        /// </summary>

        /// <remarks>경로 트리에서 루트로부터 거리</remarks>

        public int Distance;

 

        /// <summary>

        /// 상태

        /// </summary>

        /// <remarks>경로 트리 상태</remarks>

        public NodeStatus Status;

 

        /// <summary>

        /// IN 링크

        /// </summary>

        public Link InLink;

 

        #endregion

    }

}

 

 

LinkStatus.cs

 

 

namespace TestProject

{

    /// <summary>

    /// 링크 상태

    /// </summary>

    public enum LinkStatus

    {

        /// <summary>

        /// 해당무

        /// </summary>

        None,

 

        /// <summary>

        /// 경로 트리

        /// </summary>

        PathTree,

 

        /// <summary>

        /// 최단거리 경로

        /// </summary>

        ShortestPath

    }

}

 

 

Link.cs

 

 

namespace TestProject

{

    /// <summary>

    /// 링크

    /// </summary>

    public class Link

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region Field

 

        /// <summary>

        /// 노드 1

        /// </summary>

        public Node Node1;

        

        /// <summary>

        /// 노드 2

        /// </summary>

        public Node Node2;

 

        /// <summary>

        /// 비용

        /// </summary>

        public int Cost;

 

        /// <summary>

        /// 상태

        /// </summary>

        public LinkStatus Status = LinkStatus.None;

 

        #endregion

    }

}

 

 

MainForm.cs

 

 

using System;

using System.Collections.Generic;

using System.Drawing;

using System.Drawing.Drawing2D;

using System.IO;

using System.Windows.Forms;

 

namespace TestProject

{

    /// <summary>

    /// 메인 폼

    /// </summary>

    public partial class MainForm : Form

    {

        //////////////////////////////////////////////////////////////////////////////////////////////////// Field

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region Field

 

        /// <summary>

        /// 반경

        /// </summary>

        private const float RADIUS = 15;

 

        /// <summary>

        /// 제곱 반경

        /// </summary>

        private const float RADIUS_SQUARED = RADIUS * RADIUS;

 

        /// <summary>

        /// 노드 딕셔너리

        /// </summary>

        private Dictionary<int, Node> nodeDictionray = null;

 

        /// <summary>

        /// 링크 딕셔너리

        /// </summary>

        private Dictionary<string, Link> linkDictionary = null;

 

        /// <summary>

        /// 루트 노드

        /// </summary>

        private Node rootNode = null;

 

        /// <summary>

        /// 경로 트리 확보 여부

        /// </summary>

        private bool gotPathTree = false;

 

        /// <summary>

        /// 타겟 노드

        /// </summary>

        private Node targetNode = null;

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Constructor

        ////////////////////////////////////////////////////////////////////////////////////////// Public

 

        #region 생성자 - MainForm()

 

        /// <summary>

        /// 생성자

        /// </summary>

        public MainForm()

        {

            InitializeComponent();

 

            #region 이벤트를 설정한다.

 

            MouseClick              += Form_MouseClick;

            Paint                   += Form_Paint;

            this.openMenuItem.Click += openMenuItem_Click;

            this.exitMenuItem.Click += exitMenuItem_Click;

 

            #endregion

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////////////////////////// Method

        ////////////////////////////////////////////////////////////////////////////////////////// Private

        //////////////////////////////////////////////////////////////////////////////// Event

 

        #region 폼 마우스 클릭시 처리하기 - Form_MouseClick(sender, e)

 

        /// <summary>

        /// 폼 마우스 클릭시 처리하기

        /// </summary>

        /// <param name="sender">이벤트 발생자</param>

        /// <param name="e">이벤트 인자</param>

        private void Form_MouseClick(object sender, MouseEventArgs e)

        {

            if(this.nodeDictionray == null)

            {

                return;

            }

 

            Node node = GetNode(e.X, e.Y);

 

            if(node == null)

            {

                return;

            }

 

            if(e.Button == MouseButtons.Left)

            {

                FindPathTree(node);

            }

            else

            {

                this.targetNode = node;

 

                FindShortestPath();

            }

        }

 

        #endregion

        #region 폼 페인트시 처리하기 - Form_Paint(sender, e)

 

        /// <summary>

        /// 폼 페인트시 처리하기

        /// </summary>

        /// <param name="sender">이벤트 발생자</param>

        /// <param name="e">이벤트 인자</param>

        private void Form_Paint(object sender, PaintEventArgs e)

        {

            DrawNetwork(e.Graphics);

        }

 

        #endregion

        #region 파일 열기 메뉴 항목 클릭시 처리하기 - openMenuItem_Click(sender, e)

 

        /// <summary>

        /// 파일 열기 메뉴 항목 클릭시 처리하기

        /// </summary>

        /// <param name="sender">이벤트 발생자</param>

        /// <param name="e">이벤트 인자</param>

        private void openMenuItem_Click(object sender, EventArgs e)

        {

            if(this.openFileDialog.ShowDialog() == DialogResult.OK)

            {

                LoadNetwork(this.openFileDialog.FileName);

 

                Refresh();

            }

        }

 

        #endregion

        #region 종료 메뉴 항목 클릭시 처리하기 - exitMenuItem_Click(sender, e)

 

        /// <summary>

        /// 종료 메뉴 항목 클릭시 처리하기

        /// </summary>

        /// <param name="sender">이벤트 발생자</param>

        /// <param name="e">이벤트 인자</param>

        private void exitMenuItem_Click(object sender, EventArgs e)

        {

            Close();

        }

 

        #endregion

 

        //////////////////////////////////////////////////////////////////////////////// Function

 

        #region 네트워크 로드하기 - LoadNetwork(filePath)

 

        /// <summary>

        /// 네트워크 로드하기

        /// </summary>

        /// <param name="filePath">파일 경로</param>

        private void LoadNetwork(string filePath)

        {

            Text = "네트워크 최단거리 경로 찾기 : ";

 

            try

            {

                float maximumX = 0;

                float maximumY = 0;

 

                using(TextReader reader = new StreamReader(filePath))

                {

                    int nodeCount = int.Parse(reader.ReadLine());

                    int linkCount = int.Parse(reader.ReadLine());

 

                    this.nodeDictionray = new Dictionary<int, Node>();

 

                    for(int i = 0; i < nodeCount; i++)

                    {

                        Node node = new Node();

 

                        node.ID         = int.Parse(reader.ReadLine());

                        node.Location.X = int.Parse(reader.ReadLine()) * 2;

                        node.Location.Y = int.Parse(reader.ReadLine()) * 2;

 

                        if(maximumX < node.Location.X)

                        {

                            maximumX = node.Location.X;

                        }

 

                        if(maximumY < node.Location.Y)

                        {

                            maximumY = node.Location.Y;

                        }

 

                        this.nodeDictionray.Add(node.ID, node);

                    }

 

                    this.linkDictionary = new Dictionary<string,Link>();

 

                    for(int i = 0; i < linkCount; i++)

                    {

                        Link link = new Link();

 

                        int node1ID = int.Parse(reader.ReadLine());

                        int node2ID = int.Parse(reader.ReadLine());

 

                        link.Node1 = this.nodeDictionray[node1ID];

                        link.Node2 = this.nodeDictionray[node2ID];

 

                        this.linkDictionary.Add(node1ID.ToString() + "-" + node2ID.ToString(), link);

 

                        link.Cost = int.Parse(reader.ReadLine());

 

                        link.Node1.LinkDictionary.Add(node2ID, link);

                        link.Node2.LinkDictionary.Add(node1ID, link);

                    }

                }

 

                Rectangle rectangle = Rectangle.Union

                (

                    ClientRectangle,

                    new Rectangle

                    (

                        0,

                        0,

                        (int)(maximumX + RADIUS + 10),

                        (int)(maximumY + RADIUS + 10)

                    )

                );

 

                ClientSize = new Size(rectangle.Width, rectangle.Height);

 

                FileInfo fileInfo = new FileInfo(filePath);

 

                Text = "네트워크 최단거리 경로 찾기 : " + fileInfo.Name;

            }

            catch(Exception exception)

            {

                MessageBox.Show(exception.Message, "에러", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);

            }

        }

 

        #endregion

        #region 노드 구하기 - GetNode(x, y)

 

        /// <summary>

        /// 노드 구하기

        /// </summary>

        /// <param name="x">X 좌표</param>

        /// <param name="y">Y 좌표</param>

        /// <returns>노드</returns>

        private Node GetNode(int x, int y)

        {

            foreach(Node node in this.nodeDictionray.Values)

            {

                float deltaX = node.Location.X - x;

                float deltaY = node.Location.Y - y;

 

                if(deltaX * deltaX + deltaY * deltaY <= RADIUS_SQUARED)

                {

                    return node;

                }

            }

 

            return null;

        }

 

        #endregion

        #region 경로 트리 리셋하기 - ResetPathTree()

 

        /// <summary>

        /// 경로 트리 리셋하기

        /// </summary>

        private void ResetPathTree()

        {

            if(!this.gotPathTree)

            {

                return;

            }

 

            foreach(Node node in this.nodeDictionray.Values)

            {

                node.Status = NodeStatus.NotInList;

            }

 

            foreach(Link link in this.linkDictionary.Values)

            {

                link.Status = LinkStatus.None;

            }

 

            this.gotPathTree = false;

        }

 

        #endregion

        #region 경로 트리 찾기 - FindPathTree(rootNode)

 

        /// <summary>

        /// 경로 트리 찾기

        /// </summary>

        /// <param name="rootNode">루트 노드</param>

        private void FindPathTree(Node rootNode)

        {

            if(rootNode == null)

            {

                return;

            }

 

            this.rootNode = rootNode;

 

            List<Node> candidateNodeList = new List<Node>();

 

            ResetPathTree();

 

            rootNode.Distance = 0;

            rootNode.InLink   = null;

            rootNode.Status   = NodeStatus.NowInList;

 

            candidateNodeList.Add(rootNode);

 

            while(candidateNodeList.Count > 0)

            {

                int bestDistance = int.MaxValue;

                int bestIndex    = -1;

 

                for(int i = 0; i < candidateNodeList.Count; i++)

                {

                    Node candidateNode = candidateNodeList[i];

 

                    int newDistance = candidateNode.Distance;

 

                    if(newDistance < bestDistance)

                    {

                        bestIndex    = i;

                        bestDistance = newDistance;

                    }

                }

 

                Node node = candidateNodeList[bestIndex];

 

                candidateNodeList.RemoveAt(bestIndex);

 

                node.Status = NodeStatus.WasInList;

 

                foreach(Link link in node.LinkDictionary.Values)

                {

                    Node toNode;

 

                    if(node == link.Node1)

                    {

                        toNode = link.Node2;

                    }

                    else

                    {

                        toNode = link.Node1;

                    }

 

                    if(toNode.Status == NodeStatus.NotInList)

                    {

                        candidateNodeList.Add(toNode);

 

                        toNode.Status   = NodeStatus.NowInList;

                        toNode.Distance = bestDistance + link.Cost;

                        toNode.InLink   = link;

                    }

                    else if(toNode.Status == NodeStatus.NowInList)

                    {

                        int newDistance = bestDistance + link.Cost;

 

                        if(newDistance < toNode.Distance)

                        {

                            toNode.Distance = newDistance;

                            toNode.InLink   = link;

                        }

                    }

                }

            }

 

            this.gotPathTree = true;

 

            foreach(Node node in this.nodeDictionray.Values)

            {

                if(node.InLink != null)

                {

                    node.InLink.Status = LinkStatus.PathTree;

                }

            }

 

            this.targetNode = null;

 

            Refresh();

        }

 

        #endregion

        #region 최단거리 경로 찾기 - FindShortestPath()

 

        /// <summary>

        /// 최단거리 경로 찾기

        /// </summary>

        private void FindShortestPath()

        {

            foreach(Link link in this.linkDictionary.Values)

            {

                if(link.Status == LinkStatus.ShortestPath)

                {

                    link.Status = LinkStatus.PathTree;

                }

            }

 

            Node node = this.targetNode;

 

            while(node != this.rootNode)

            {

                node.InLink.Status = LinkStatus.ShortestPath;

 

                if(node.InLink.Node1 == node)

                {

                    node = node.InLink.Node2;

                }

                else

                {

                    node = node.InLink.Node1;

                }

            }

 

            Refresh();

        }

 

        #endregion

        #region 네트워크 그리기 - DrawNetwork(graphics)

 

        /// <summary>

        /// 네트워크 그리기

        /// </summary>

        /// <param name="graphics">이벤트 발생자</param>

        private void DrawNetwork(Graphics graphics)

        {

            graphics.SmoothingMode = SmoothingMode.AntiAlias;

 

            graphics.Clear(this.BackColor);

 

            if(this.nodeDictionray == null)

            {

                return;

            }

 

            using(Pen treePen = new Pen(Color.Blue, 3))

            {

                using(Pen pathPen = new Pen(Color.Red, 3))

                {

                    Pen linkPen;

 

                    using(Brush backgroundBrush = new SolidBrush(this.BackColor))

                    {

                        foreach(Link link in this.linkDictionary.Values)

                        {

                            if(link.Status == LinkStatus.PathTree)

                            {

                                linkPen = treePen;

                            }

                            else if(link.Status == LinkStatus.ShortestPath)

                            {

                                linkPen = pathPen;

                            }

                            else

                            {

                                linkPen = Pens.Black;

                            }

 

                            float x1 = link.Node1.Location.X;

                            float y1 = link.Node1.Location.Y;

 

                            float x2 = link.Node2.Location.X;

                            float y2 = link.Node2.Location.Y;

 

                            float dx = x2 - x1;

                            float dy = y2 - y1;

 

                            float distance = (float)(Math.Sqrt(dx * dx + dy * dy));

 

                            if(distance > 0)

                            {

                                dx = dx * RADIUS / distance;

                                dy = dy * RADIUS / distance;

 

                                x1 = x1 + dx;

                                y1 = y1 + dy;

                                x2 = x2 - dx;

                                y2 = y2 - dy;

 

                                graphics.DrawLine(linkPen, x1, y1, x2, y2);

 

                                x1 = (x1 + x2) / 2;

                                y1 = (y1 + y2) / 2;

 

                                graphics.FillEllipse(backgroundBrush, x1 - RADIUS, y1 - RADIUS, 2 * RADIUS, 2 * RADIUS);

 

                                string costString = link.Cost.ToString();

 

                                SizeF costStringSize = graphics.MeasureString(costString, Font);

 

                                graphics.DrawString

                                (

                                    costString,

                                    Font,

                                    Brushes.Black,

                                    x1 - costStringSize.Width  / 2,

                                    y1 - costStringSize.Height / 2

                                );

                            }

                        }

                    }

                }

            }

 

            Brush textBrush;

            Brush nodeBrush;

            Pen   nodePen;

 

            foreach(Node node in this.nodeDictionray.Values)

            {

                if((node == this.rootNode) || (node == this.targetNode))

                {

                    textBrush = Brushes.White;

                    nodeBrush = Brushes.Black;

 

                    nodePen = Pens.White;

                }

                else

                {

                    textBrush = Brushes.Black;

                    nodeBrush = Brushes.White;

 

                    nodePen = Pens.Black;

                }

 

                graphics.FillEllipse

                (

                    nodeBrush,

                    node.Location.X - RADIUS,

                    node.Location.Y - RADIUS,

                    2 * RADIUS,

                    2 * RADIUS

                );

 

                graphics.DrawEllipse

                (

                    nodePen,

                    node.Location.X - RADIUS,

                    node.Location.Y - RADIUS,

                    2 * RADIUS,

                    2 * RADIUS

                );

 

                string idString = node.ID.ToString();

 

                SizeF idStringSize = graphics.MeasureString(idString, Font);

 

                graphics.DrawString

                (

                    idString,

                    Font,

                    textBrush,

                    node.Location.X - idStringSize.Width  / 2,

                    node.Location.Y - idStringSize.Height / 2

                );

            }

        }

 

        #endregion

    }

}

 

------------------------------------------------------------------------------------------------------------------------

728x90
반응형
Posted by 사용자 icodebroker

댓글을 달아 주세요