programer skripsi tesis tugas akhir
-

Contoh Program Source Code   /

Pewarnaan Simpul Graph Metode Greedy

Posted on 07.20
Join with us

Pewarnaan Simpul Graph Metode Greedy

Dalam Teori Graph, masalah pewarnaan graph terdiri dari tiga macam, yaitu pewarnaan simpul, pewarnaan sisi, dan pewarnaan peta. Teknik pewarnaan simpul merupakan salah satu subyek yang menarik dalam bidang graph. Pewarnaan simpul adalah mewarnai semua simpul suatu graph sehingga setiap pasang simpul yang terhubung langsung diberi warna yang berbeda. Sedangkan, jumlah warna minimum yang diperlukan disebut bilangan kromatik Terdapat beberapa algoritma yang digunakan untuk menemukan bilangan kromatik suatu graph. Salah satu algoritma yang dapat digunakan adalah Algoritma Greedy. Aplikasi dari teknik ini telah banyak diterapkan di berbagai bidang. Salah satu permasalahan yang dapat diselesaikan dengan menggunakan pewarnaan simpul graph adalah pengaturan pola lampu lalu lintas di persimpangan jalan.

Pewarnaan Simpul Graph Metode Greedy
Pewarnaan Simpul Graph Metode Greedy

Langkah awal pewarnaan simpul graph dengan Algoritma Greedy yaitu mengurutkan simpul dari derajat tertinggi sampai yang terendah. Simpul dengan derajat tertinggi diwarnai terlebih dahulu, kemudian diperiksa simpul yang tidak terhubung dengan simpul pertama untuk diberi warna yang sama. Jika tidak ada dipilih simpul dengan derajat tertinggi yang belum diwarna untuk diberi warna yang baru, kemudian diperiksa kembali simpul yang tidak terhubung untuk diberi warna yang sama. Langkah tersebut dilanjutkan hingga semua simpul telah diwarnai.

Penerapan algoritma Greedy pada pengaturan pola lampu lalu lintas dimulai dengan merepresentasikan persimpangan jalan ke dalam bentuk graph. Setiap arus kendaraan pada persimpangan jalan direpresentasikan sebagai simpul. Untuk setiap arus kendaraan yang tidak kompatibel maka simpul yang merepresentasikan arus kendaraan tersebut dihubungkan dengan suatu sisi. Dengan bentuk graph tersebut, maka pengaturan pola lampu lalu lintas dapat lebih mudah diselesaikan dengan pewarnaan simpul graph dengan metode Greedy.

Output dari pewarnaan simpul graph adalah banyaknya warna yang digunakan untuk mewarnai simpul graph. Pada pengaturan pola lampu lalu lintas, banyaknya warna yang diperlukan untuk mewarnai simpul graph digunakan untuk menentukan banyakanya fase yang diperlukan dalam satu siklus. Simpul yang tidak terhubung dengan simpul yang lain adalah arus yang kompatibel dengan semua arus sehingga selalu bergerak dalam tiap fase, sedangkan simpul-simpul dengan warna yang sama merupakan alih gerak kendaraan yang dapat bergerak bersama dalam satu fase. Dengan demikian tidak ada alih gerak yang tidak kompatibel yang bergerak pada fase yang sama, sehingga tidak terjadi penumpukan kendaraan di tengah persimpangan.

Selain dengan perhitungan manual, pada penelitian ini dibuat implementasi program dengan software Delphi 7. Dari perhitungan secara manual dan perhitungan dengan program untuk contoh graph dengan 8 simpul diperoleh hasil yang sama. Demikian pula pada penerapan pengaturan pola lampu lalu lintas pada pertigaan dan perempatan diperoleh hasil yang sama.

Contoh Program / Source Code



using System;
using System.Collections.Generic;
//using System.Linq;
//using System.Text;
using System.IO;
using System.Collections;

// Memecahkan masalah max-klik menggunakan algoritma serakah.
// A klik dari grafik adalah bagian dimana setiap simpul terhubung ke semua
// Node lain dalam subset. Masalah max-klik adalah untuk menemukan
// Klik terbesar. Max-klik adalah NP-lengkap.

namespace GreedyMaxClique
{
  class GreedyMaxCliqueProgram
  {
    static Random random = null;

    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin greedy maximum clique demo\n");

        string graphFile = "..\\..\\DimacsGraph.clq"; // small demo file. best (largest) clique siz is 4.
        //string graphFile = "..\\..\\C2000.9.clq"; // large DIMACS benchmark challenge file. best (largest) known clique is 76.
        Console.WriteLine("Loading graph into memory");
        Console.WriteLine("Graph loaded and validated\n");
        MyGraph graph = new MyGraph(graphFile, "DIMACS");

        int maxTime = 20; // use 20 for small demo file; use about 1,000-10,000 for benchmark problem.
        int targetCliqueSize = graph.NumberNodes; // max-clique size for any graph is the size of the graph -- graph is one giant clique.

        List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
        Console.WriteLine("\nMaximum time reached");
        Console.WriteLine("\nSize of best clique found = " + maxClique.Count);

        Console.WriteLine("\nBest clique found:");
        Console.WriteLine(ListAsString(maxClique));

        Console.WriteLine("\nEnd greedy maximum clique demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
        Console.ReadLine();
      }
    } // Main

    static List<int> FindMaxClique(MyGraph graph, int maxTime, int targetCliqueSize)
    {
      
      List<int> clique = new List<int>();
      random = new Random(1);
      int time = 0;
      int timeBestClique = 0;
      int timeRestart = 0;
      int nodeToAdd = -1;
      int nodeToDrop = -1;

      int randomNode = random.Next(0, graph.NumberNodes);
      Console.WriteLine("Adding node " + randomNode);
      clique.Add(randomNode);
      
      List<int> bestClique = new List<int>();
      bestClique.AddRange(clique);
      int bestSize = bestClique.Count;
      timeBestClique = time;

      List<int> possibleAdd = MakePossibleAdd(graph, clique); // nodes which will increase size of clique
      List<int> oneMissing = MakeOneMissing(graph, clique);

      while (time < maxTime && bestSize < targetCliqueSize)
      {
        ++time;

        bool cliqueChanged = false; // to control branching logic in loop
        if (possibleAdd.Count > 0) // 
        {
          nodeToAdd = GetNodeToAdd(graph, possibleAdd); // node from possibleAdd which is most connected to nodes in possibleAdd
          Console.WriteLine("Adding node " + nodeToAdd);
          clique.Add(nodeToAdd);
          clique.Sort();
          cliqueChanged = true;
          if (clique.Count > bestSize)
          {
            bestSize = clique.Count;
            bestClique.Clear();
            bestClique.AddRange(clique);
            timeBestClique = time;
          }
        } // add node

        if (cliqueChanged == false)
        {
          if (clique.Count > 0)
          {
            nodeToDrop = GetNodeToDrop(graph, clique, oneMissing); // find node in clique which generate max increase in possibleAdd set. if more than one, pick one at random
            Console.WriteLine("Dropping node " + nodeToDrop);
            clique.Remove(nodeToDrop);
            clique.Sort();
            cliqueChanged = true;
          }
        } // drop node

        int restart = 2 * bestSize;
        if (time - timeBestClique > restart && time - timeRestart > restart) // restart? if it's been a while since we found a new best clique or did a restart . . .
        {
          Console.WriteLine("\nRestarting\n");
          timeRestart = time;
          int seedNode = random.Next(0, graph.NumberNodes);
          clique.Clear();
          Console.WriteLine("Adding node " + seedNode);
          clique.Add(seedNode);
        } // restart

        possibleAdd = MakePossibleAdd(graph, clique);
        oneMissing = MakeOneMissing(graph, clique);

        //ValidateState(graph, clique, possibleAdd, oneMissing);

      } // main processing loop


      return bestClique;
    } // FindMaxClique


    static List<int> MakePossibleAdd(MyGraph graph, List<int> clique)
    {
      // create list of nodes in graph which are connected to all nodes in clique and therefore will form a larger clique
      // calls helper FormsALargerClique
      List<int> result = new List<int>();

      for (int i = 0; i < graph.NumberNodes; ++i) // each node in graph
      {
        if (FormsALargerClique(graph, clique, i) == true)
          result.Add(i);
      }
      return result; // could be empty List
    } // MakePossibleAdd

    static bool FormsALargerClique(MyGraph graph, List<int> clique, int node)
    {
      // is node connected to all nodes in clique?
      for (int i = 0; i < clique.Count; ++i) // compare node against each member of clique
      {
        //if (clique[i] == node) return false; // node is aleady in clique so node will not form a larger clique
        if (graph.AreAdjacent(clique[i], node) == false) return false; // node is not connected to one of the nodes in the clique
      }
      return true; // passed all checks
    } // FormsALargerClique

    static int GetNodeToAdd(MyGraph graph, List<int> possibleAdd)
    {
      // find node from a List of allowed and posible add which has max degree in posibleAdd
      // there could be more than one, if so, pick one at random
      //if (possibleAdd == null) throw new Exception("List possibleAdd is null in GetNodeToAdd");
      //if (possibleAdd.Count == 0) throw new Exception("List possibleAdd has Count 0 in GetNodeToAdd");

      if (possibleAdd.Count == 1) // there is only 1 node to choose from
        return possibleAdd[0];

      // examine each node in possibleAdd to find the max degree in possibleAdd (because there could be several nodes tied with max degree)
      int maxDegree = 0;
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        int currNode = possibleAdd[i];
        int degreeOfCurrentNode = 0;
        for (int j = 0; j < possibleAdd.Count; ++j) // check each node in possibleAdd
        {
          int otherNode = possibleAdd[j];
          if (graph.AreAdjacent(currNode, otherNode) == true) ++degreeOfCurrentNode;
        }
        if (degreeOfCurrentNode > maxDegree)
          maxDegree = degreeOfCurrentNode;
      }

      // now rescan possibleAdd and grab all nodes which have maxDegree
      List<int> candidates = new List<int>();
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        int currNode = possibleAdd[i];
        int degreeOfCurrentNode = 0;
        for (int j = 0; j < possibleAdd.Count; ++j) // check each node in possibleAdd
        {
          int otherNode = possibleAdd[j];
          if (graph.AreAdjacent(currNode, otherNode) == true) ++degreeOfCurrentNode;
        }
        if (degreeOfCurrentNode == maxDegree)
          candidates.Add(currNode);
      }

      //if (candidates.Count == 0) throw new Exception("candidates List has size 0 just before return in GetNodeToAdd");
      return candidates[random.Next(0, candidates.Count)]; // if candidates has Count 1 we'll get that one node
    } // GetNodeToAdd

    static int GetNodeToDrop(MyGraph graph, List<int> clique, List<int> oneMissing)
    {
(clique.Count == 0) throw new Exception("clique has Count 0 in GetNodeToDrop");

      if (clique.Count == 1)
        return clique[0];

      int maxCount = 0; // see explanation below
      for (int i = 0; i < clique.Count; ++i) // each node in clique nodes List
      {
        int currCliqueNode = clique[i];
        int countNotAdjacent = 0;
        for (int j = 0; j < oneMissing.Count; ++j) // each node in the one missing list
        {
          int currOneMissingNode = oneMissing[j];
          if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false) // we like this
            ++countNotAdjacent;
        }

        if (countNotAdjacent > maxCount)
          maxCount = countNotAdjacent;
      }

      // at this point we know what the max-not-connected count is but there could be several clique nodes which give that size
      List<int> candidates = new List<int>();
      for (int i = 0; i < clique.Count; ++i) // each node in clique
      {
        int currCliqueNode = clique[i];
        int countNotAdjacent = 0;
        for (int j = 0; j < oneMissing.Count; ++j) // each node in the one missing list
        {
          int currOneMissingNode = oneMissing[j];
          if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false)
            ++countNotAdjacent;
        }

        if (countNotAdjacent == maxCount) // cxurrent clique node has max count not connected
          candidates.Add(currCliqueNode);
      }

      //if (candidates.Count == 0) throw new Exception("candidates List has size 0 just before return in GetNodeToDropFromAllowedInClique");
      return candidates[random.Next(0, candidates.Count)]; // must have size of at least 1

    } // GetNodeToDrop



    static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
    {
      // make a list of nodes in graph which are connected to all but one of the nodes in clique
      int count; // number of nodes in clique which are connected to a candidate node. if final count == (clique size - 1) then candidate is a winner
      List<int> result = new List<int>();

      for (int i = 0; i < graph.NumberNodes; ++i) // each node in graph i a candidate
      {
        count = 0;
        if (graph.NumberNeighbors(i) < clique.Count - 1) continue; // node i has too few neighbors to possibly be connected to all but 1 node in clique
        //if (LinearSearch(clique, i) == true) continue; // node i is in clique. clique is not sorted so use LinearSearch -- consider Sort + BinarySearch
        if (clique.BinarySearch(i) >= 0) continue;
        for (int j = 0; j < clique.Count; ++j) // count how many nodes in clique are connected to candidate i
        {
          if (graph.AreAdjacent(i, clique[j]))
            ++count;
        }
        if (count == clique.Count - 1)
          result.Add(i);
      } // each candidate node i
      return result;

    } // MakeOneMissing

    static string ListAsString(List<int> list)
    {
      string s = "";
      for (int i = 0; i < list.Count; ++i)
      {
        if (i % 10 == 0 && i > 0) s += Environment.NewLine;
        s += list[i] + " ";
      }
      
      s += Environment.NewLine;
      return s;
    } // ListAsString

    static void ValidateState(MyGraph graph, List<int> clique, List<int> possibleAdd, List<int> oneMissing)
    {
      // any duplicates in clique?
      for (int i = 0; i < clique.Count - 1; ++i)
      {
        for (int j = i + 1; j < clique.Count; ++j)
        {
          if (clique[i] == clique[j])
            throw new Exception("Dup value in clique");
        }
      }
      // any values in clique in possibleAdd or oneMissing?
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        if (clique.BinarySearch(possibleAdd[i]) >= 0)
          throw new Exception("Possible Add value in clique");
      }
      for (int i = 0; i < oneMissing.Count; ++i)
      {
        if (clique.BinarySearch(oneMissing[i]) >= 0)
          throw new Exception("Salah satu nilai Hilang di klik");
      }
      // Adakah nilai dalam possibleAdd di oneMissing?
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        if (oneMissing.Contains(possibleAdd[i]))
          throw new Exception("Nilai di possibleAdd ditemukan di oneMissing");
      }
      for (int i = 0; i < oneMissing.Count; ++i)
      {
        if (possibleAdd.Contains(oneMissing[i]))
          throw new Exception("Nilai di oneMissing ditemukan di possibleAdd");
      }
    } // ValidateState

  } // class Program

  public class MyGraph
  {
    private BitMatrix data;
    private int numberNodes;
    private int numberEdges;
    private int[] numberNeighbors;

    public MyGraph(string graphFile, string fileFormat)
    {
      if (fileFormat.ToUpper() == "DIMACS")
        LoadDimacsFormatGraph(graphFile);
      else
        throw new Exception("Format " + fileFormat + " not supported");
    }

    private void LoadDimacsFormatGraph(string graphFile)
    {
      FileStream ifs = new FileStream(graphFile, FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      string line = "";
      string[] tokens = null;

      // untuk mendapatkan garis p (ex: "p tepi 9 16")
      line = sr.ReadLine(); // Membaca baris pertama dari file sebagai priming baca
      line = line.Trim();
      while (line != null && line.StartsWith("p") == false)
      {
        line = sr.ReadLine();
        line = line.Trim();
      }

      tokens = line.Split(' ');
      int numNodes = int.Parse(tokens[2]); // jumlah node
      int numEdges = int.Parse(tokens[3]); // jumlah tepi

      sr.Close(); ifs.Close();

      this.data = new BitMatrix(numNodes);

      ifs = new FileStream(graphFile, FileMode.Open); // membuka ulang file
      sr = new StreamReader(ifs);
      while ((line = sr.ReadLine()) != null)
      {
        line = line.Trim();
        if (line.StartsWith("e") == true) // (ex: "e 7 4")
        {
          tokens = line.Split(' ');
          int nodeA = int.Parse(tokens[1]) - 1; // DIMACS adalah berbasis 1. kurangi 1 untuk mengkonversi ke basis 0
          int nodeB = int.Parse(tokens[2]) - 1;
          data.SetValue(nodeA, nodeB, true);
          data.SetValue(nodeB, nodeA, true);
        }
      }
      sr.Close(); ifs.Close();

      this.numberNeighbors = new int[numNodes];
      for (int row = 0; row < numNodes; ++row)
      {
        int count = 0;
        for (int col = 0; col < numNodes; ++col)
        {
          if (data.GetValue(row, col) == true)
            ++count;
        }
        numberNeighbors[row] = count;
      }

      this.numberNodes = numNodes;
      this.numberEdges = numEdges;
      return;
    }

    public int NumberNodes
    {
      get { return this.numberNodes; }
    }

    public int NumberEdges
    {
      get { return this.numberEdges; }
    }

    public int NumberNeighbors(int node)
    {
      return this.numberNeighbors[node];
    }

    public bool AreAdjacent(int nodeA, int nodeB)
    {
      if (this.data.GetValue(nodeA, nodeB) == true)
        return true;
      else
        return false;
    }

    public override string ToString()
    {
      string s = "";
      for (int i = 0; i < this.data.Dim; ++i)
      {
        s += i + ": ";
        for (int j = 0; j < this.data.Dim; ++j)
        {
          if (this.data.GetValue(i, j) == true)
            s += j + " ";
        }
        s += Environment.NewLine;
      }
      return s;
    }

    public static void ValidateGraphFile(string graphFile, string fileFormat)
    {
      if (fileFormat.ToUpper() == "DIMACS")
        ValidateDimacsGraphFile(graphFile);
      else
        throw new Exception("Format " + fileFormat + " not supported");
    }

    public static void ValidateDimacsGraphFile(string graphFile)
    {
      FileStream ifs = new FileStream(graphFile, FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      string line = "";
      string[] tokens = null;

      while ((line = sr.ReadLine()) != null)
      {
        line = line.Trim();
        if (line.StartsWith("c") == false && line.StartsWith("p") == false &&
          line.StartsWith("e") == false)
          throw new Exception("jenis garis tidak diketahui: " + line + " in ValidateDimacsGraphFile");

        try
        {
          if (line.StartsWith("p"))
          {
            tokens = line.Split(' ');
            int numNodes = int.Parse(tokens[2]);
            int numEdges = int.Parse(tokens[3]);
          }
          else if (line.StartsWith("e"))
          {
            tokens = line.Split(' ');
            int nodeA = int.Parse(tokens[1]);
            int nodeB = int.Parse(tokens[2]);
          }
        }
        catch
        {
          throw new Exception("Kesalahan parsing baris = " + line + " in ValidateDimacsGraphFile");
        }
      }

      sr.Close();
      ifs.Close();
      return;
    } // ValidateDimacsGraphFile

    public void ValidateGraph()
    {
      // Jumlah tepi item harus genap
      int numConnections = 0;
      for (int i = 0; i < this.data.Dim; ++i)
      {
        for (int j = 0; j < this.data.Dim; ++j)
        {
          if (this.data.GetValue(i, j) == true)
            ++numConnections;
        }
      }
      if (numConnections % 2 != 0)
        throw new Exception("Total jumlah koneksi dalam grafik adalah " + numConnections + ". Harus lebih");

      // Sepenuhnya simetris
      for (int i = 0; i < this.data.Dim; ++i)
      {
        if (this.data.GetValue(i, i) == true)
          throw new Exception("Node " + i + " is connected to itself");
        for (int j = 0; j < this.data.Dim; ++j)
        {
          if (this.data.GetValue(i, j) != this.data.GetValue(j, i))
            throw new Exception("Graph is not symmetric at " + i + " and " + j);
        }
      }
      return;
    } // ValidateGraph




    private class BitMatrix
    {
      private BitArray[] data;
      public readonly int Dim;

      public BitMatrix(int n)
      {
        this.data = new BitArray[n];
        for (int i = 0; i < data.Length; ++i)
        {
          this.data[i] = new BitArray(n);
        }
        this.Dim = n;
      }
      public bool GetValue(int row, int col)
      {
        return data[row][col];
      }
      public void SetValue(int row, int col, bool value)
      {
        data[row][col] = value;
      }
      public override string ToString()
      {
        string s = "";
        for (int i = 0; i < data.Length; ++i)
        {
          for (int j = 0; j < data[i].Length; ++j)
          {
            if (data[i][j] == true) s += "1 "; else s += "0 ";
          }
          s += Environment.NewLine;
        }
        return s;
      }


    } // class BitMatrix


  } // class MyGraph


} // ns





Pewarnaan Simpul Graph Metode Greedy

Dalam Teori Graph, masalah pewarnaan graph terdiri dari tiga macam, yaitu pewarnaan simpul, pewarnaan sisi, dan pewarnaan peta. Teknik pewarnaan simpul merupakan salah satu subyek yang menarik dalam bidang graph. Pewarnaan simpul adalah mewarnai semua simpul suatu graph sehingga setiap pasang simpul yang terhubung langsung diberi warna yang berbeda. Sedangkan, jumlah warna minimum yang diperlukan disebut bilangan kromatik Terdapat beberapa algoritma yang digunakan untuk menemukan bilangan kromatik suatu graph. Salah satu algoritma yang dapat digunakan adalah Algoritma Greedy. Aplikasi dari teknik ini telah banyak diterapkan di berbagai bidang. Salah satu permasalahan yang dapat diselesaikan dengan menggunakan pewarnaan simpul graph adalah pengaturan pola lampu lalu lintas di persimpangan jalan.

Pewarnaan Simpul Graph Metode Greedy
Pewarnaan Simpul Graph Metode Greedy

Langkah awal pewarnaan simpul graph dengan Algoritma Greedy yaitu mengurutkan simpul dari derajat tertinggi sampai yang terendah. Simpul dengan derajat tertinggi diwarnai terlebih dahulu, kemudian diperiksa simpul yang tidak terhubung dengan simpul pertama untuk diberi warna yang sama. Jika tidak ada dipilih simpul dengan derajat tertinggi yang belum diwarna untuk diberi warna yang baru, kemudian diperiksa kembali simpul yang tidak terhubung untuk diberi warna yang sama. Langkah tersebut dilanjutkan hingga semua simpul telah diwarnai.

Penerapan algoritma Greedy pada pengaturan pola lampu lalu lintas dimulai dengan merepresentasikan persimpangan jalan ke dalam bentuk graph. Setiap arus kendaraan pada persimpangan jalan direpresentasikan sebagai simpul. Untuk setiap arus kendaraan yang tidak kompatibel maka simpul yang merepresentasikan arus kendaraan tersebut dihubungkan dengan suatu sisi. Dengan bentuk graph tersebut, maka pengaturan pola lampu lalu lintas dapat lebih mudah diselesaikan dengan pewarnaan simpul graph dengan metode Greedy.

Output dari pewarnaan simpul graph adalah banyaknya warna yang digunakan untuk mewarnai simpul graph. Pada pengaturan pola lampu lalu lintas, banyaknya warna yang diperlukan untuk mewarnai simpul graph digunakan untuk menentukan banyakanya fase yang diperlukan dalam satu siklus. Simpul yang tidak terhubung dengan simpul yang lain adalah arus yang kompatibel dengan semua arus sehingga selalu bergerak dalam tiap fase, sedangkan simpul-simpul dengan warna yang sama merupakan alih gerak kendaraan yang dapat bergerak bersama dalam satu fase. Dengan demikian tidak ada alih gerak yang tidak kompatibel yang bergerak pada fase yang sama, sehingga tidak terjadi penumpukan kendaraan di tengah persimpangan.

Selain dengan perhitungan manual, pada penelitian ini dibuat implementasi program dengan software Delphi 7. Dari perhitungan secara manual dan perhitungan dengan program untuk contoh graph dengan 8 simpul diperoleh hasil yang sama. Demikian pula pada penerapan pengaturan pola lampu lalu lintas pada pertigaan dan perempatan diperoleh hasil yang sama.

Contoh Program / Source Code



using System;
using System.Collections.Generic;
//using System.Linq;
//using System.Text;
using System.IO;
using System.Collections;

// Memecahkan masalah max-klik menggunakan algoritma serakah.
// A klik dari grafik adalah bagian dimana setiap simpul terhubung ke semua
// Node lain dalam subset. Masalah max-klik adalah untuk menemukan
// Klik terbesar. Max-klik adalah NP-lengkap.

namespace GreedyMaxClique
{
  class GreedyMaxCliqueProgram
  {
    static Random random = null;

    static void Main(string[] args)
    {
      try
      {
        Console.WriteLine("\nBegin greedy maximum clique demo\n");

        string graphFile = "..\\..\\DimacsGraph.clq"; // small demo file. best (largest) clique siz is 4.
        //string graphFile = "..\\..\\C2000.9.clq"; // large DIMACS benchmark challenge file. best (largest) known clique is 76.
        Console.WriteLine("Loading graph into memory");
        Console.WriteLine("Graph loaded and validated\n");
        MyGraph graph = new MyGraph(graphFile, "DIMACS");

        int maxTime = 20; // use 20 for small demo file; use about 1,000-10,000 for benchmark problem.
        int targetCliqueSize = graph.NumberNodes; // max-clique size for any graph is the size of the graph -- graph is one giant clique.

        List<int> maxClique = FindMaxClique(graph, maxTime, targetCliqueSize);
        Console.WriteLine("\nMaximum time reached");
        Console.WriteLine("\nSize of best clique found = " + maxClique.Count);

        Console.WriteLine("\nBest clique found:");
        Console.WriteLine(ListAsString(maxClique));

        Console.WriteLine("\nEnd greedy maximum clique demo\n");
        Console.ReadLine();
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
        Console.ReadLine();
      }
    } // Main

    static List<int> FindMaxClique(MyGraph graph, int maxTime, int targetCliqueSize)
    {
      
      List<int> clique = new List<int>();
      random = new Random(1);
      int time = 0;
      int timeBestClique = 0;
      int timeRestart = 0;
      int nodeToAdd = -1;
      int nodeToDrop = -1;

      int randomNode = random.Next(0, graph.NumberNodes);
      Console.WriteLine("Adding node " + randomNode);
      clique.Add(randomNode);
      
      List<int> bestClique = new List<int>();
      bestClique.AddRange(clique);
      int bestSize = bestClique.Count;
      timeBestClique = time;

      List<int> possibleAdd = MakePossibleAdd(graph, clique); // nodes which will increase size of clique
      List<int> oneMissing = MakeOneMissing(graph, clique);

      while (time < maxTime && bestSize < targetCliqueSize)
      {
        ++time;

        bool cliqueChanged = false; // to control branching logic in loop
        if (possibleAdd.Count > 0) // 
        {
          nodeToAdd = GetNodeToAdd(graph, possibleAdd); // node from possibleAdd which is most connected to nodes in possibleAdd
          Console.WriteLine("Adding node " + nodeToAdd);
          clique.Add(nodeToAdd);
          clique.Sort();
          cliqueChanged = true;
          if (clique.Count > bestSize)
          {
            bestSize = clique.Count;
            bestClique.Clear();
            bestClique.AddRange(clique);
            timeBestClique = time;
          }
        } // add node

        if (cliqueChanged == false)
        {
          if (clique.Count > 0)
          {
            nodeToDrop = GetNodeToDrop(graph, clique, oneMissing); // find node in clique which generate max increase in possibleAdd set. if more than one, pick one at random
            Console.WriteLine("Dropping node " + nodeToDrop);
            clique.Remove(nodeToDrop);
            clique.Sort();
            cliqueChanged = true;
          }
        } // drop node

        int restart = 2 * bestSize;
        if (time - timeBestClique > restart && time - timeRestart > restart) // restart? if it's been a while since we found a new best clique or did a restart . . .
        {
          Console.WriteLine("\nRestarting\n");
          timeRestart = time;
          int seedNode = random.Next(0, graph.NumberNodes);
          clique.Clear();
          Console.WriteLine("Adding node " + seedNode);
          clique.Add(seedNode);
        } // restart

        possibleAdd = MakePossibleAdd(graph, clique);
        oneMissing = MakeOneMissing(graph, clique);

        //ValidateState(graph, clique, possibleAdd, oneMissing);

      } // main processing loop


      return bestClique;
    } // FindMaxClique


    static List<int> MakePossibleAdd(MyGraph graph, List<int> clique)
    {
      // create list of nodes in graph which are connected to all nodes in clique and therefore will form a larger clique
      // calls helper FormsALargerClique
      List<int> result = new List<int>();

      for (int i = 0; i < graph.NumberNodes; ++i) // each node in graph
      {
        if (FormsALargerClique(graph, clique, i) == true)
          result.Add(i);
      }
      return result; // could be empty List
    } // MakePossibleAdd

    static bool FormsALargerClique(MyGraph graph, List<int> clique, int node)
    {
      // is node connected to all nodes in clique?
      for (int i = 0; i < clique.Count; ++i) // compare node against each member of clique
      {
        //if (clique[i] == node) return false; // node is aleady in clique so node will not form a larger clique
        if (graph.AreAdjacent(clique[i], node) == false) return false; // node is not connected to one of the nodes in the clique
      }
      return true; // passed all checks
    } // FormsALargerClique

    static int GetNodeToAdd(MyGraph graph, List<int> possibleAdd)
    {
      // find node from a List of allowed and posible add which has max degree in posibleAdd
      // there could be more than one, if so, pick one at random
      //if (possibleAdd == null) throw new Exception("List possibleAdd is null in GetNodeToAdd");
      //if (possibleAdd.Count == 0) throw new Exception("List possibleAdd has Count 0 in GetNodeToAdd");

      if (possibleAdd.Count == 1) // there is only 1 node to choose from
        return possibleAdd[0];

      // examine each node in possibleAdd to find the max degree in possibleAdd (because there could be several nodes tied with max degree)
      int maxDegree = 0;
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        int currNode = possibleAdd[i];
        int degreeOfCurrentNode = 0;
        for (int j = 0; j < possibleAdd.Count; ++j) // check each node in possibleAdd
        {
          int otherNode = possibleAdd[j];
          if (graph.AreAdjacent(currNode, otherNode) == true) ++degreeOfCurrentNode;
        }
        if (degreeOfCurrentNode > maxDegree)
          maxDegree = degreeOfCurrentNode;
      }

      // now rescan possibleAdd and grab all nodes which have maxDegree
      List<int> candidates = new List<int>();
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        int currNode = possibleAdd[i];
        int degreeOfCurrentNode = 0;
        for (int j = 0; j < possibleAdd.Count; ++j) // check each node in possibleAdd
        {
          int otherNode = possibleAdd[j];
          if (graph.AreAdjacent(currNode, otherNode) == true) ++degreeOfCurrentNode;
        }
        if (degreeOfCurrentNode == maxDegree)
          candidates.Add(currNode);
      }

      //if (candidates.Count == 0) throw new Exception("candidates List has size 0 just before return in GetNodeToAdd");
      return candidates[random.Next(0, candidates.Count)]; // if candidates has Count 1 we'll get that one node
    } // GetNodeToAdd

    static int GetNodeToDrop(MyGraph graph, List<int> clique, List<int> oneMissing)
    {
(clique.Count == 0) throw new Exception("clique has Count 0 in GetNodeToDrop");

      if (clique.Count == 1)
        return clique[0];

      int maxCount = 0; // see explanation below
      for (int i = 0; i < clique.Count; ++i) // each node in clique nodes List
      {
        int currCliqueNode = clique[i];
        int countNotAdjacent = 0;
        for (int j = 0; j < oneMissing.Count; ++j) // each node in the one missing list
        {
          int currOneMissingNode = oneMissing[j];
          if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false) // we like this
            ++countNotAdjacent;
        }

        if (countNotAdjacent > maxCount)
          maxCount = countNotAdjacent;
      }

      // at this point we know what the max-not-connected count is but there could be several clique nodes which give that size
      List<int> candidates = new List<int>();
      for (int i = 0; i < clique.Count; ++i) // each node in clique
      {
        int currCliqueNode = clique[i];
        int countNotAdjacent = 0;
        for (int j = 0; j < oneMissing.Count; ++j) // each node in the one missing list
        {
          int currOneMissingNode = oneMissing[j];
          if (graph.AreAdjacent(currCliqueNode, currOneMissingNode) == false)
            ++countNotAdjacent;
        }

        if (countNotAdjacent == maxCount) // cxurrent clique node has max count not connected
          candidates.Add(currCliqueNode);
      }

      //if (candidates.Count == 0) throw new Exception("candidates List has size 0 just before return in GetNodeToDropFromAllowedInClique");
      return candidates[random.Next(0, candidates.Count)]; // must have size of at least 1

    } // GetNodeToDrop



    static List<int> MakeOneMissing(MyGraph graph, List<int> clique)
    {
      // make a list of nodes in graph which are connected to all but one of the nodes in clique
      int count; // number of nodes in clique which are connected to a candidate node. if final count == (clique size - 1) then candidate is a winner
      List<int> result = new List<int>();

      for (int i = 0; i < graph.NumberNodes; ++i) // each node in graph i a candidate
      {
        count = 0;
        if (graph.NumberNeighbors(i) < clique.Count - 1) continue; // node i has too few neighbors to possibly be connected to all but 1 node in clique
        //if (LinearSearch(clique, i) == true) continue; // node i is in clique. clique is not sorted so use LinearSearch -- consider Sort + BinarySearch
        if (clique.BinarySearch(i) >= 0) continue;
        for (int j = 0; j < clique.Count; ++j) // count how many nodes in clique are connected to candidate i
        {
          if (graph.AreAdjacent(i, clique[j]))
            ++count;
        }
        if (count == clique.Count - 1)
          result.Add(i);
      } // each candidate node i
      return result;

    } // MakeOneMissing

    static string ListAsString(List<int> list)
    {
      string s = "";
      for (int i = 0; i < list.Count; ++i)
      {
        if (i % 10 == 0 && i > 0) s += Environment.NewLine;
        s += list[i] + " ";
      }
      
      s += Environment.NewLine;
      return s;
    } // ListAsString

    static void ValidateState(MyGraph graph, List<int> clique, List<int> possibleAdd, List<int> oneMissing)
    {
      // any duplicates in clique?
      for (int i = 0; i < clique.Count - 1; ++i)
      {
        for (int j = i + 1; j < clique.Count; ++j)
        {
          if (clique[i] == clique[j])
            throw new Exception("Dup value in clique");
        }
      }
      // any values in clique in possibleAdd or oneMissing?
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        if (clique.BinarySearch(possibleAdd[i]) >= 0)
          throw new Exception("Possible Add value in clique");
      }
      for (int i = 0; i < oneMissing.Count; ++i)
      {
        if (clique.BinarySearch(oneMissing[i]) >= 0)
          throw new Exception("Salah satu nilai Hilang di klik");
      }
      // Adakah nilai dalam possibleAdd di oneMissing?
      for (int i = 0; i < possibleAdd.Count; ++i)
      {
        if (oneMissing.Contains(possibleAdd[i]))
          throw new Exception("Nilai di possibleAdd ditemukan di oneMissing");
      }
      for (int i = 0; i < oneMissing.Count; ++i)
      {
        if (possibleAdd.Contains(oneMissing[i]))
          throw new Exception("Nilai di oneMissing ditemukan di possibleAdd");
      }
    } // ValidateState

  } // class Program

  public class MyGraph
  {
    private BitMatrix data;
    private int numberNodes;
    private int numberEdges;
    private int[] numberNeighbors;

    public MyGraph(string graphFile, string fileFormat)
    {
      if (fileFormat.ToUpper() == "DIMACS")
        LoadDimacsFormatGraph(graphFile);
      else
        throw new Exception("Format " + fileFormat + " not supported");
    }

    private void LoadDimacsFormatGraph(string graphFile)
    {
      FileStream ifs = new FileStream(graphFile, FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      string line = "";
      string[] tokens = null;

      // untuk mendapatkan garis p (ex: "p tepi 9 16")
      line = sr.ReadLine(); // Membaca baris pertama dari file sebagai priming baca
      line = line.Trim();
      while (line != null && line.StartsWith("p") == false)
      {
        line = sr.ReadLine();
        line = line.Trim();
      }

      tokens = line.Split(' ');
      int numNodes = int.Parse(tokens[2]); // jumlah node
      int numEdges = int.Parse(tokens[3]); // jumlah tepi

      sr.Close(); ifs.Close();

      this.data = new BitMatrix(numNodes);

      ifs = new FileStream(graphFile, FileMode.Open); // membuka ulang file
      sr = new StreamReader(ifs);
      while ((line = sr.ReadLine()) != null)
      {
        line = line.Trim();
        if (line.StartsWith("e") == true) // (ex: "e 7 4")
        {
          tokens = line.Split(' ');
          int nodeA = int.Parse(tokens[1]) - 1; // DIMACS adalah berbasis 1. kurangi 1 untuk mengkonversi ke basis 0
          int nodeB = int.Parse(tokens[2]) - 1;
          data.SetValue(nodeA, nodeB, true);
          data.SetValue(nodeB, nodeA, true);
        }
      }
      sr.Close(); ifs.Close();

      this.numberNeighbors = new int[numNodes];
      for (int row = 0; row < numNodes; ++row)
      {
        int count = 0;
        for (int col = 0; col < numNodes; ++col)
        {
          if (data.GetValue(row, col) == true)
            ++count;
        }
        numberNeighbors[row] = count;
      }

      this.numberNodes = numNodes;
      this.numberEdges = numEdges;
      return;
    }

    public int NumberNodes
    {
      get { return this.numberNodes; }
    }

    public int NumberEdges
    {
      get { return this.numberEdges; }
    }

    public int NumberNeighbors(int node)
    {
      return this.numberNeighbors[node];
    }

    public bool AreAdjacent(int nodeA, int nodeB)
    {
      if (this.data.GetValue(nodeA, nodeB) == true)
        return true;
      else
        return false;
    }

    public override string ToString()
    {
      string s = "";
      for (int i = 0; i < this.data.Dim; ++i)
      {
        s += i + ": ";
        for (int j = 0; j < this.data.Dim; ++j)
        {
          if (this.data.GetValue(i, j) == true)
            s += j + " ";
        }
        s += Environment.NewLine;
      }
      return s;
    }

    public static void ValidateGraphFile(string graphFile, string fileFormat)
    {
      if (fileFormat.ToUpper() == "DIMACS")
        ValidateDimacsGraphFile(graphFile);
      else
        throw new Exception("Format " + fileFormat + " not supported");
    }

    public static void ValidateDimacsGraphFile(string graphFile)
    {
      FileStream ifs = new FileStream(graphFile, FileMode.Open);
      StreamReader sr = new StreamReader(ifs);
      string line = "";
      string[] tokens = null;

      while ((line = sr.ReadLine()) != null)
      {
        line = line.Trim();
        if (line.StartsWith("c") == false && line.StartsWith("p") == false &&
          line.StartsWith("e") == false)
          throw new Exception("jenis garis tidak diketahui: " + line + " in ValidateDimacsGraphFile");

        try
        {
          if (line.StartsWith("p"))
          {
            tokens = line.Split(' ');
            int numNodes = int.Parse(tokens[2]);
            int numEdges = int.Parse(tokens[3]);
          }
          else if (line.StartsWith("e"))
          {
            tokens = line.Split(' ');
            int nodeA = int.Parse(tokens[1]);
            int nodeB = int.Parse(tokens[2]);
          }
        }
        catch
        {
          throw new Exception("Kesalahan parsing baris = " + line + " in ValidateDimacsGraphFile");
        }
      }

      sr.Close();
      ifs.Close();
      return;
    } // ValidateDimacsGraphFile

    public void ValidateGraph()
    {
      // Jumlah tepi item harus genap
      int numConnections = 0;
      for (int i = 0; i < this.data.Dim; ++i)
      {
        for (int j = 0; j < this.data.Dim; ++j)
        {
          if (this.data.GetValue(i, j) == true)
            ++numConnections;
        }
      }
      if (numConnections % 2 != 0)
        throw new Exception("Total jumlah koneksi dalam grafik adalah " + numConnections + ". Harus lebih");

      // Sepenuhnya simetris
      for (int i = 0; i < this.data.Dim; ++i)
      {
        if (this.data.GetValue(i, i) == true)
          throw new Exception("Node " + i + " is connected to itself");
        for (int j = 0; j < this.data.Dim; ++j)
        {
          if (this.data.GetValue(i, j) != this.data.GetValue(j, i))
            throw new Exception("Graph is not symmetric at " + i + " and " + j);
        }
      }
      return;
    } // ValidateGraph




    private class BitMatrix
    {
      private BitArray[] data;
      public readonly int Dim;

      public BitMatrix(int n)
      {
        this.data = new BitArray[n];
        for (int i = 0; i < data.Length; ++i)
        {
          this.data[i] = new BitArray(n);
        }
        this.Dim = n;
      }
      public bool GetValue(int row, int col)
      {
        return data[row][col];
      }
      public void SetValue(int row, int col, bool value)
      {
        data[row][col] = value;
      }
      public override string ToString()
      {
        string s = "";
        for (int i = 0; i < data.Length; ++i)
        {
          for (int j = 0; j < data[i].Length; ++j)
          {
            if (data[i][j] == true) s += "1 "; else s += "0 ";
          }
          s += Environment.NewLine;
        }
        return s;
      }


    } // class BitMatrix


  } // class MyGraph


} // ns




Contoh Program Pewarnaan Simpul Graph Metode Greedy

Source Code Pewarnaan Simpul Graph Metode Greedy

Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman

Tutorial belajar Pewarnaan Simpul Graph Metode Greedy

VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow Chart PDF ZIP RAR DOC Java C# Visual Basic

Gratis download Pewarnaan Simpul Graph Metode Greedy

Chart PDF ZIP RAR DOC Java C# Visual Basic VB PHP Matlab C++ Penerapan implementasi metode algoritma pemrograman Source Code Tutorial belajar Gratis download Flow

Penerapan implementasi Pewarnaan Simpul Graph Metode Greedy Pewarnaan Simpul Graph Metode Greedy

Posted by: Project-G Contoh Program Pewarnaan Simpul Graph Metode Greedy Updated at : 07.20
Jika Anda perlu source code terkait dengan artikel di atas atau ada yang ingin di tanyakan anda bisa melakukan konsultasi gratis kepada kami, melalui form di bawah. Hasil konsultasi akan di kirimkan ke email Anda. Kami mohon supportnya dengan mengklik beberapa tombol berikut :


Contoh Program Pewarnaan Simpul Graph Metode Greedy

perhatian

Informasi Penting Untuk Mahasiswa !

Kami menawarkan layanan jasa konsultan bimbingan pembuatan program untuk Tesis Skripsi dan Tugas Akhir Informatika, Komputer, Elektro dan Teknik lainnya yang bidang minatnya mengarah ke teknologi informasi. BASED PROJECT :Mobile Development (Java, Adobe, AS3, Android, BB, iOS, WPhone dll), Web & Desktop Development (.Net, C#, MATLAB, PHP, Delphi, Visual Basic dll). BONUS : Di bimbing untuk penguasaan materi dan coding dan revisi.
detail
Label: , , , , ,
Konsultasi gratis