Graph Programming

จากที่ผ่านๆมาหลายบทความในช่วงนี้ ผู้เขียนได้เขียนแต่เรื่องที่ไม่ยากมากนัก คือไม่ต้องต้องมีการคำนวนซับซ้อนอะไรเท่าไหร่ เช่นการเชื่อมต่อกับฐานข้อมูล การส่งผ่านตัวแปรระหว่าง Class บน .NET อะไรแบบนี้ ซึ่งทำให้เราได้ห่างหายจากการวิเคราะห์โค้ดกันไปบ้างพอสมควร ในบทความนี้ ผู้เขียนจึงคิดขึ้นมาได้อย่างนึงว่า เราควรจะมีอะไรแรงๆมาขั้นบ้าง เพื่อความหลากหลายในบทความของเรา

พูดถึง Graph Programming ต้องย้อนกลับไปตั้งแต่ผู้เขียนยังเรียนอยู่มหาลัยฯ ปี 2 ซึ่งตอนนั้นผู้เขียนได้เรียนวิชา Data Structure and Algorithm ซึ่งในวิชานั้น ก็มีการสอนถึง Data Structure หลายๆตัว เช่น Queue, Stack, Linklistและก็รวมทั้ง Graph นี้ด้วย แต่สิ่งที่ต่างกันคือ ถ้าเป็น Queue, Stack หรือ Linklistอาจารย์เค้าจะเจาะเข้าไปให้เราดูโค้ด เอาไปใช้งาน แต่พอเป็น Graph กลับมีแค่การอธิบายทฤษฎี และการนำเอาไปใช้ ไม่ได้ลงโค้ด ผู้เขียนจึงได้ไปถามอาจารย์ท่านว่า ทำไมถึงไม่มีการสอนเชิงลึกเกี่ยวกับเรื่องนี้ ซึ่งอาจารย์ท่านก็ได้ตอบกลับมาว่า “เพราะแต่ละคน มีพื้นฐานไม่เท่ากันนะสิ ถึงแม้ว่าแต่ละคน จะเรียนมาเหมือนกัน แต่ในเมื่อสุดท้าย แต่ละคนมีพื้นฐานที่ไม่เท่ากันแล้ว จะสอนเรื่องให้ยากเกินไปเลยไม่ได้”
พอได้ยินอย่างนี้ ผู้เขียนก็มานั่งคิด เออ.. จริงวะ แต่ถ้าคนที่อยากเรียนจะทำยังไงละ แล้วพอผู้เขียนเรียนผ่านไปอีกไม่กี่ปี มันก็มีเรื่องเยอะแยะเลย ที่ได้นำ Graph ไปใช้ ฉะนั้น วันนี้ผู้เขียนเลยคิดว่า เราควรที่จะเผยแพร่ความรู้ให้คนอื่นบ้างซักที อย่างน้อย มันก็ต้องมีคนมาอ่านแล้วเข้าใจบ้างละวะ!!!
กราฟ (Graph)  เป็นโครงสร้างของข้อมูลชนิดหนึ่ง ที่ไม่ใช่เชิงเส้น มักนำมาใช้ในการแก้ปัญหาที่ซับซ้อน เช่นการวางข่ายคอมพิวเตอร์ วิเคราะห์เส้นทางที่สั้นที่สุดเป็นต้น ซึ่งกราฟนั้น เราสามารถอธิบายได้ง่ายๆ ว่า มันคือโครงข่ายของแต่ละโนด (Nodes หรือ Vertexes) ซึ่งถูกเชื่อมต่อเข้าด้วยกันด้วยเส้นเชื่อม (Edges) ซึ่งหาก Edges ไม่มีทิศทาง กราฟก็จะเป็นกราฟแบบไม่มีทิศทาง แต่หาก Edges เป็นแบบมีทิศทาง กราฟก็จะเป็นแบบมีทิศทางด้วย(Directed Graph)
ซึ่งแปลว่า หากเราจะสร้างคลาส Graph ขึ้นมานั้น ย่อมแปลว่าเราจะต้องสร้างคลาสองค์ประกอบ ทั้ง 2 อย่างขึ้นมา ซึ่งก็คือ Edge และ Node อย่างแน่นอน Class Diagram ตอนแรก เราจึงให้เป็นแบบนี้ก่อน
 ซึงในกราฟของเรา จำเป็นต้องเก็บ Edges และ Nodes เอาไว้มากๆ ในที่นี้ เราอาจเลือกได้ว่า เราจะเก็บเป็น Dictionary หรือ List ก็ได้ แล้วแต่เราแต่ผู้เขียน จะใช้เป็น List ไปก่อน เพราะเอาไปใช้ง่ายดี
public class Graph
{
    protectedList<Node> _nodes = new List<Node>();
    protectedList<Edge> _edges = new List<Edge>();
    publicGraph()
    {
        //todos
    }
}                           
                               
แต่จากที่เราทราบมาแล้วว่า Graph ของเรามีทั้งแบบ Directed และ Undirected การออบแบบข้างต้น อาจจะยังไม่ดีเท่าใดนัก เราจึงอาจแก้ไขโครงสร้างของ Class ทั้งหมด เป็นไปได้ดังนี้
โดยเราจะค่อยๆพัฒนาไปในแนวทางของ Undirected ก่อน เพื่อความง่ายในการทำงาน ซึ่งส่วนใหญ่ เราจะเขียนองค์ประกอบต่างๆไว้ใน Class หลัก ส่วนการทำงานที่แตกต่างกัน เราค่อยแยกไปเขียนใน Undirected กับ Directed
พอเราสร้างมาถึงขั้นตอนนี้แล้ว สิ่งที่เราจะลืมไม่ได้เลย ก็คือการเทส(เราจะเทสกันบ่อยๆ แต่ไม่ถึงกับทำเป็น TDD (Test-Driven Development))ซึ่งเราจะใช้ตัว Unit Test ที่มีใน Visual Studio นี่แหละ ช่วยเรา
ให้เราไปสร้าง Test Project ขึ้นมาก่อน โดยให้เพิ่ม Project ไว้ที่ Solution เดียวกัน (ต้องเป็น .NET Framework 4.0 ขึ้นไป)
เราก็จะไปโปรเจค หน้าตาเป็นแบบนี้
จากนั้นคลิกขวาที่ Project Graph_Test > Reference เลือก Add Reference เลือกโปรเจค Graph_lib เข้ามา
ให้เราทำการแก้ไขชื่อไฟล์UnitTest1.cs เป็น Graph_Tester.cs แล้วแก้โค้ดเป็นดังข้างล่างนี้
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using Graph_lib;
namespace Graph_Test
{
    [TestClass]
    publicclass Graph_Tester
    {
        [TestMethod]
        public void GraphCanBeDeclaredAsUndirectedGraph()
        {
            Graphg = new UndirectedGraph();
        }
    }
}
หากเราทดสอบรันเทส (Ctrl + R, A)ก็จะพบว่า สิ่งที่เราเทสนั้น ผ่าน แปลว่า เราสามารถทำสิ่งที่เราเทสขึ้นมาได้อย่างถูกต้องนั้นเอง
กลับไปดูที่งานหลักของเรา เราจะเริ่มออกแบบ Graph ของเรากันอีกครั้ง ซึ่งเราจะทำการออกแบบแบบ Buttom Up หรือก็คือการออกแบบจากส่วนย่อยไปก่อน โดยต่อไป เราจะเริ่มต้นกันที่ Node
Node ของเรา ต้องเก็บอะไรได้ข้างละ? ชื่อโนด? อย่างเดียวรึเปล่า? คิดยังไม่ออก ตอนนี้เราก็ให้มีอย่างเดียวไปก่อนละกัน
public class Node
{
    privatestring _name;
   
    publicNode()
    {
        _name = “A”;
    }
}
การทำแบบนี้ เป็นการเก็บข้อมูลที่ใช้ใน Class ไว้ด้านใน (เราจะเรียกว่า field)ซึ่ง field นี้ เราจะไม่ให้มันสามารถมาติดต่อกับโลกภายนอกได้เอง และ Class อื่นๆ ก็จะไม่เห็นด้วย แต่หากเราต้องการนำ field ไปใช้ข้างนอกหละ สิ่งที่เรานิยมทำก็คือ การเพิ่ม Property เข้าไปนั่นเอง หน้าตาก็จะประมาณนี้
using System;
using System.Collections.Generic;
using System.Text;
namespace Graph_lib
{
    publicclass Node
    {
        private string_name;
        public stringName
        {
            get
            {
                return _name;
            }
            set
            {
                _name = value;
            }
        }
        public Node()
        {
            _name = “A”;
        }
    }
}
พอเราต้องการจะเข้าถึง _name เราก็สามารถเรีกใช้ผ่าน Name ได้เลย ซึ่งสามารถเทสได้ดังนี้
        [TestMethod]
        public void NodeCanChangeName()
        {
            Noden1 = new Node();
            Assert.AreEqual(n1.Name, “A”);
            Noden2 = new Node() { Name = “B”};
            Assert.AreEqual(n2.Name, “B”);
        }
และเพื่อให้ง่ายต่อการใช้งาน เราจึงควรเพิ่ม Constructor ที่รับ ชื่อเข้าไปด้วย
ถ้าคิดว่า Node เสร็จแล้ว ต่อไปเราไปทำ Edge กัน
สำหรับ Edge นั้น สิ่งสำคัญที่อยู่ภายในของมัน กลับไม่ใช่ ชื่อ แต่เป็นค่า Cost ที่ใช้สำหรับผ่าน Edge นั้นๆ กับอีกสิ่งที่สำคัญ ก็คือตัวของ Edge จะต้องทราบว่า Node ที่มันเชื่อมต่ออยู่ มีอะไรบ้าง
โค้ดข้างล่างนี้ค่อนข้างเหมือนเดิม ขอให้ไปลองศึกษาเข้าใจเอง และอยากให้ลองสังเกตุด้วยว่า ทำไมบางอย่างถึงเป็น public, protected, หรือ private แตกต่างกันไป
using System;
using System.Collections.Generic;
using System.Text;
namespace Graph_lib
{
    publicabstract class Edge
    {
        private int _cost;
        protected Node[] _nodes = new Node[2];
        public int Cost
        {
            get { return_cost; }
            set{ _cost = value; }
        }
        public Node[] Nodes
        {
            get
            {
                return _nodes;
            }
        }
        public Edge()
        {
           
        }
    }
}
พอถึงตรงนี้ เรายังไม่มีฟังชั่นที่ทำการเชื่อมระหว่าง Node ทั้ง 2 เข้าด้วยกันเลย เราจึงเพิ่มฟังชั่นในการเชื่อมโนดเข้าไป
    publicvoid Connect(Nodenode1, Node node2)
    {
        this._nodes[0] = node1;
        this._nodes[1] = node2;
    }
และทุกๆครั้งที่จะทำการสร้าง Edge เราจะต้องมีการกำหนด Node ที่จะมาเชื่อมเข้าไปตั้งแต่ต้นเสมอ เพื่อไม่ให้ Edge นั้นลอย
public Edge(Node node1, Node node2)
{
    this.Connect(node1, node2);
}
โค้ดของ Edge ตอนนี้เลยเป็นแบบนี้
using System;
using System.Collections.Generic;
using System.Text;
namespace Graph_lib
{
    publicabstract class Edge
    {
        private int _cost;
        protected Node[] _nodes = new Node[2];
        public int Cost
        {
            get { return_cost; }
            set { _cost = value; }
        }
        public Node[] Nodes
        {
            get
            {
                return _nodes;
            }
        }
        public voidConnect(Node node1, Nodenode2)
        {
            this._nodes[0] = node1;
            this._nodes[1] = node2;
        }
        public Edge(Nodenode1, Node node2)
        {
            this.Connect(node1, node2);
        }
    }
}
แต่เนื่องจาก Edge เราเป็น abstract เราจึงต้องจัดการแก้ Constructor ของ Class ลูกให้เรียบร้อย
using System;
using System.Collections.Generic;
using System.Text;
namespace Graph_lib
{
    publicclass UndirectedEdge : Edge
    {
        public UndirectedEdge(Node node1, Nodenode2)
            :base(node1, node2)
        {
        }
    }
}
และเราก็มาเทสกัน
        [TestMethod]
        public void EdgeCanConnectAndGotTrueConnectedNodes()
        {
            Noden1 = new Node() { Name = “A”};
            Noden2 = new Node() { Name = “B”};
            Edgee = new UndirectedEdge(n1, n2);
            Node[] answer = e.Nodes;
            Assert.AreEqual(
                (answer[0] == n1) ||
                (answer[0] == n2)
                , true);
            Assert.AreEqual(
                (answer[1] == n1) ||
                (answer[1] == n2)
                , true);
            Assert.AreNotEqual(answer[0], answer[1]);
        }
นอกจากนี้ ยังมีเรื่องของ Cost ใน Constructor อีก ซึ่งเราสามารถเพิ่ม และ แก้ไข Constructor ได้ดังนี้
        public Edge(Nodenode1, Node node2)
        {
            this.Connect(node1, node2);
            Cost = 0;
        }
        public Edge(Nodenode1, Node node2, int cost)
        {
            this.Connect(node1, node2);
            Cost = cost;
        }
พอเรามองว่า Edge กับ Node ของเราเริ่มใช้ได้ ต่อไป เราก็ต้องไปดูที่ Graph ของเราแล้วละ ว่ายังขาดอะไร
    publicabstract class Graph
    {
        protected List<Node> _nodes = newList<Node>();
        protected List<Edge> _edges = newList<Edge>();
        public Graph()
        {
            //todos
        }
    }
ที่เราเห็นได้ชัดเลย ก็คือตัวของ Graph ของเรา ยังไม่สามารถทำการเพิ่ม Node กับ Edge ลงไปได้ด้วยซ้ำ เราจึงต้องเพิ่งฟังชั่นทั้ง 2
        public void AddNode(string nodeName)
        {
            _nodes.Add(new Node(nodeName));
        }
        public void AddEdge(Node node1, Node node2, int cost)
        {
            _edges.Add(new Edge(node1, node2, cost));
        }
แต่พอเราโค้ดเสร็จ เราจะพบว่าเกิดการ error ขึ้นที่ AddEdge เนื่องจาก Edge นั้นเป็น abstract class เราจึงอาจจะให้ฟังชั่น AddEdge นี้ เป็น abstract function ไปก่อนก็ได้ แล้วค่อยไประบุใน DirectedGraph และ UndirectedGraph
public abstract void AddEdge(Node node1, Node node2, int cost);
UndirectedGraph เราก็ทำเป็นแบบนี้
using System;
using System.Collections.Generic;
using System.Text;
namespace Graph_lib
{
    publicclass UndirectedGraph : Graph
    {
        public UndirectedGraph()
            : base()
        {
           
        }
        public overridevoid AddEdge(Node node1, Nodenode2, int cost)
        {
            base._edges.Add(new UndirectedEdge(node1, node2, cost));
        }
    }
}
แล้วเราก็ไปแก้ใน UndirectedEdge ด้วย
using System;
using System.Collections.Generic;
using System.Text;
namespace Graph_lib
{
    publicclass UndirectedEdge : Edge
    {
        public UndirectedEdge(Node node1, Nodenode2)
            : base(node1, node2)
        {
        }
        public UndirectedEdge(Node node1, Nodenode2, int cost)
            : base(node1, node2, cost)
        {
        }
    }
}
ต่อไป เราก็ลองไปเทส
        [TestMethod]
        public void GraphCanAddNode()
        {
            Graphg = new UndirectedGraph();
            g.AddNode(“A”);
            g.AddNode(“B”);
            Node[] answer = g.Nodes;
            Assert.AreEqual(
                (answer[0].Name == “A”) ||
                (answer[0].Name == “B”)
                , true);
            Assert.AreEqual(
                (answer[1].Name == “A”) ||
                (answer[1].Name == “B”)
                , true);
            Assert.AreNotEqual(answer[0].Name, answer[1].Name);
        }
แต่ Graph ของเรา ยังไม่มี Property Nodes จึงเกิด error ขึ้น ให้เราเพิ่ม Property นี้เข้าไปซะ
public Node[] Nodes { get{ return _nodes.ToArray(); } }
ทดสอบเทส ก็จะพบว่า เทสผ่านนั่นเอง
ต่อไป ให้ลองเพิ่มในส่วนของ
public Edge[] Edges { get{ return _edges.ToArray(); } }
เข้าไปใน Graph ด้วย แล้วลองเขียนเทสเอาเอง สำหรับทดสอบ Graph.AddEdge();
หลังจากที่เขียนเทส ซัก 2 3 เทสล่าสุด เราจะพบปัญหาว่า เวลาเราจะหา Node ใน Graph นั้น เราต้องรู้ว่า Node ไหนอยู่ Index ที่เท่าไหร่ ซึ่งในความเป็นจริง เราไม่สามารถจะรู้ได้ แต่เราจะใช้เป็น ชื่อของ Node แทน เราจึงต้องสร้างฟังชั่นขึ้นมาใหม่ใน Graph เพื่อค้นหา Node ออกมา โดยดึงจากชื่อ
ซึ่งจริงๆแล้ว ใน List นั้น มีฟังชั่นในการหาอยู่แล้ว คือ List.find() ซึ่งเราสามารถนำมาใช้ได้เลย ร่วมกับ Lambda Expression
public Node findNodeByName(string nodeName)
{
    return_nodes.Find(x => x.Name== nodeName);
}
นอกจากนี้ เรายังเพิ่ม Overload ให้กับ Graph.AddNode() เล็กน้อย
    publicvoid AddNode(Node node)
    {
        _nodes.Add(node);
    }
เทสฟังชั่นการค้นหา Node ของเรา
        [TestMethod]
        public void GraphCanFindNodeByName()
        {
            Graphg = new UndirectedGraph();
            Noden = new Node(“ABC”);
            g.AddNode(n);
            Assert.AreEqual(n, g.findNodeByName(“ABC”));
        }
แต่เอาเข้าจริงๆ การทำแบบนี้ ก็มีปัญหาได้เช่นกัน เพราะว่าเราอาจจะใส่ชื่อ Node ลงไปซ้ำๆกัน แล้วผลลัพท์การค้นหาผิดพลาด เช่น
        [TestMethod]
        public void GraphCanFindNodeByNameWithDuplicateName()
        {
            Graphg = new UndirectedGraph();
            Node n1 = new Node(“ABC”);
            Noden2 = new Node(“ABC”);
            g.AddNode(n1);
            g.AddNode(n2);
            Assert.AreEqual(n1, g.findNodeByName(“ABC”));
            Assert.AreEqual(n2, g.findNodeByName(“ABC”));
        }
ซึ่งมันจะไม่ผ่าน
วิธีแก้ ถ้าเราตั้งใจจะให้มันหาชื่อ Node จาก Name จริงๆ เราก็ต้องไม่ให้มันใส่ Node ที่ชื่อซ้ำกันได้ ไม่ก็เปลี่ยนการทำงานเล็กน้อย เป็นให้กำหนด NodeID ไปด้วย แต่อย่างหลังยากกว่าหน่อย เลยขิเกียจทำ สรุป เราแค่ห้ามไม่ให้มันชื่อซ้ำกันก็พอ
สิ่งที่เราต้องทำก็คือ ทุกครั้งที่มีการ AddNode ให้เราทำการเช็คทุกครั้งว่า มี Node ที่มีชื่อเดียวกันหรือยัง ถ้ามี ก็ให้ throw exception ไป
        public void AddNode(Node node)
        {
            if (!_nodes.Exists(x => x.Name == node.Name))
                _nodes.Add(node);
            else
                throw new DuplicateNameException();
        }
ซึ่ง Exception นี้ เราก็ต้องสร้างขึ้นมาเอง
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Graph_lib
{
    publicclass DuplicateNameException : Exception
    {
        public stringMessage = “Duplicate error.”;
    }
}
เปลี่ยนจากเทสเก่า เป็นเทสนี้ ก็จะพบว่า ผ่านไปได้ด้วยดี
        [TestMethod]
        [ExpectedException(typeof(DuplicateNameException))]
        public void GraphThrowDuplicateNameExceptionIfDuplicateNodeName()
        {
            Graphg = new UndirectedGraph();
            Noden1 = new Node(“ABC”);
            Noden2 = new Node(“ABC”);
            g.AddNode(n1);
            g.AddNode(n2);
            Assert.AreEqual(n1, g.findNodeByName(“ABC”));
            Assert.AreEqual(n2, g.findNodeByName(“ABC”));
        }
ทำมาตั้งนาน ย้อนกลับไปดูกัน เราทำอะไรไปบ้าง
ใช่ครับ แค่นี้ แต่สิ่งที่เราทำนั้น มันเป็นการโค้ดแบบแข็งแรงครับ คือในอนาคต ต่อให้เราพัฒนาโค้ดต่อไปเยอะแค่ไหน โค้ดเก่าของเราก็จะสามารถถูกนำมาใช้ใหม่ได้เสมอครับ
สิ่งต่อไปที่เราจะทำคือ การทำ Graph Traversal หรือก็คือการท่องไปใน Graph ซึ่งเราจะใช้วิธีแบบ Breadth First ใครยังไม่รู้จัก ไปทำความเข้าใจได้ที่นี่
ซึ่งหากสรุปง่ายๆ มันก็คือการที่เราเริ่มจาก Node ใดๆ แล้วไปที่ Node รอบๆของ Node นั้น โดยที่เราจะไม่ไปผ่านซ้ำกับ Nodeเดิมที่เคยผ่านมาแล้วนั่นเอง
ตรงนี้ ผู้เขียนอยากให้ผู้อ่านทดลองเขียนฟังชั่นนี้ด้วยตัวเองให้ได้ก่อน อาจจะใช้เวลา หนึ่ง หรือ 2 หรือหลายชั่วโมงก็ว่ากันไป เพราะโค้ดตรงนี้ มันจะยากเกินกว่าที่จะอธิบายด้วยตัวอักษรให้เข้าใจง่ายๆได้
เริ่มจากขั้นแรก ก่อนอื่น การทำ Graph Traversal นั้น เราจะต้องหา Node ข้างเคียงของ Node ใดๆให้ได้ก่อน ซึ่งเรายังไม่มีฟังชั่นนั้น เราจึงต้องสร้างมันขึ้นมา ซึ่ง ณ ตรงนี้ Undirected กับ Directed จะทำงานไม่เหมือนกัน เราจึงต้องแยกกันเขียน (แต่ผู้เขียนจะแสดง Undirected อย่างเดียว)
    publicoverride Node[] AroundNodes(Nodecenter)
    {
        var around = newList<Node>();
        var nearEdge= base._edges.FindAll(x =>
            x.Nodes[0] == center ||
            x.Nodes[1] == center
        );
        foreach (var x in nearEdge)
        {
            around.Add((x.Nodes[0] == center) ? x.Nodes[1] : x.Nodes[0]);
        }
        return around.ToArray();
    }                   
โค้ดข้างบนนี้ เนื่องจากผู้เขียนอยากให้โค้ดมันกระชับมากที่สุดเพราะเรื่องเริ่มมาไกลแล้ว จึงได้ใส่เทคนิคการโค้ดเข้าไปมากมาย อีกทั้งอยากให้ผู้อ่านไปศึกษาต่อยอดเองด้วย เรื่องที่ต้องศึกษาเพิ่ม จะมีเรื่องของ Delegate, Lambda Expansion และเรื่องของOperator ? ด้วย
ต่อไปก็เหมือนเดิม คือเรามาเทสกัน
    [TestMethod]
    publicvoid GraphCanFindAroundNodeCorrectly()
    {
        Graphg = new UndirectedGraph();
        List<Node> ln = new List<Node>();
        ln.AddRange(new Node[] {
            new Node(“A”),
            new Node(“B”),
            new Node(“C”),
            new Node(“D”),
            new Node(“E”)
        });
        foreach (var x in ln)
            g.AddNode(x);
        /*  Graph will be like this
            *  A–B
            *  |  |
            *  |  C–D
            *  | /
            *  E
            */
        g.AddEdge(g.findNodeByName(“A”), g.findNodeByName(“B”), 0);
        g.AddEdge(g.findNodeByName(“C”), g.findNodeByName(“B”), 0);
        g.AddEdge(g.findNodeByName(“C”), g.findNodeByName(“D”), 0);
        g.AddEdge(g.findNodeByName(“C”), g.findNodeByName(“E”), 0);
        g.AddEdge(g.findNodeByName(“A”), g.findNodeByName(“E”), 0);
        Node[] answer = g.AroundNodes(g.findNodeByName(“C”));
        Assert.AreEqual(answer.Count(x => true), 3);
        Assert.AreEqual(answer.Contains<Node>(ln.Find(x => x.Name == “B”)), true);
        Assert.AreEqual(answer.Contains<Node>(ln.Find(x => x.Name == “E”)), true);
        Assert.AreEqual(answer.Contains<Node>(ln.Find(x => x.Name == “D”)), true);
        answer = g.AroundNodes(g.findNodeByName(“E”));
        Assert.AreEqual(answer.Count(x => true), 2);
        Assert.AreEqual(answer.Contains<Node>(ln.Find(x => x.Name == “A”)), true);
        Assert.AreEqual(answer.Contains<Node>(ln.Find(x => x.Name == “C”)), true);
    }
ซึ่งแน่นอน มันก็ผ่าน (ผู้เขียนยังตกใจเลย ทีเดียวผ่านเนี่ย)
ต่อไป เราก็มาทำ Breadth First Traversal กันต่อ ซึ่งก็ได้หน้าตามาแบบนี้ ซึ่งฟังชั่นนี้ เราทำใน Graph ได้เลย ไม่ต้องแยกทำใน Directed หรือ Undirected เพราะผลลัพท์มันต่างกัน ตั้งแต่ตอนที่ทำฟังชั่น AroundNodes แล้ว
        public Node[] BreadthFirst(Node startNode)
        {
            List<Node> passed = newList<Node>();
            List<Node> temp;
            NodethisNode;
            Queue<Node> q = new Queue<Node>();
            q.Enqueue(startNode);
            while(q.Count != 0)
            {
                thisNode = q.Dequeue();
                passed.Add(thisNode);
                temp = new List<Node>();
                temp.AddRange(this.AroundNodes(thisNode));
                temp.RemoveAll(x => passed.Contains(x) || q.Contains(x));
                foreach (var x in temp) q.Enqueue(x);
            }
            return passed.ToArray();
        }
แล้วก็เทสเช่นเคย
    [TestMethod]
    publicvoid GraphCanBreadthFirstTraversal()
    {
        Graphg = new UndirectedGraph();
        List<Node> ln = new List<Node>();
        ln.AddRange(new Node[] {
            new Node(“A”),
            new Node(“B”),
            new Node(“C”),
            new Node(“D”),
            new Node(“E”)
        });
        foreach (var x in ln)
            g.AddNode(x);
        /*  Graph will be like this
            *  A–B
            *  |  |
            *  |  C–D
            *  | /
            *  E
            */
        g.AddEdge(g.findNodeByName(“A”), g.findNodeByName(“B”), 0);
        g.AddEdge(g.findNodeByName(“C”), g.findNodeByName(“B”), 0);
        g.AddEdge(g.findNodeByName(“C”), g.findNodeByName(“D”), 0);
        g.AddEdge(g.findNodeByName(“C”), g.findNodeByName(“E”), 0);
        g.AddEdge(g.findNodeByName(“A”), g.findNodeByName(“E”), 0);
        ln= new List<Node>();
        ln.AddRange(g.BreadthFirst(g.findNodeByName(“A”)));
        string s = “”;
        foreach (var x in ln)
            s += x.Name;
        Assert.AreEqual((s == “ABECD” || s == “AEBCD”),true);
    }
และหากเราต้องการทำฟังชั่นที่เป็น Depth First เราก็แค่เปลี่ยนจาก Queue เป็น Stack เท่านั้นเอง
    publicNode[] DepthFirst(Node startNode)
    {
        List<Node> passed = newList<Node>();
        List<Node> temp;
        NodethisNode;
        Stack<Node> st = new Stack<Node>();
        st.Push(startNode);
        while (st.Count != 0)
        {
            thisNode= st.Pop();
            passed.Add(thisNode);
            temp = new List<Node>();
            temp.AddRange(this.AroundNodes(thisNode));
            temp.RemoveAll(x => passed.Contains(x) || st.Contains(x));
            foreach (var x in temp) st.Push(x);
        }
        return passed.ToArray();
    }
พอมาถึงตรงนี้ ก็คิดว่าคงเพียงพอ และหนักหนาไปกับ Graph กันแล้ว ในครั้งถัดไป เราก็จะนำ Graph เดิมนี้มาใช้อีก แต่เราจะเริ่มนำอัลกอริธึมที่ยากกว่านี้มาใช้กัน ขอบคุณที่อ่านมาถึงตรงนี้ครับ สวัสดีครับ

Leave a Reply

Your email address will not be published. Required fields are marked *