Advertisement
desdemona

przynajmniej wydaje się że zapisywanie w macierzy działa

Oct 27th, 2015
599
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 5.80 KB | None | 0 0
  1. #!/usr/bin/env python3
  2. # -*- coding: utf-8 -*-
  3.  
  4. from ctypes import *
  5.  
  6.  
  7. # Grafy reprezentowane przy pomocy macierzy sąsiedztwa.
  8. class AdjacencyMatrix64bit:
  9.     # Wyjątek pojawiający się przy próbie konwersji z błędnej reprezentacji tekstowej.
  10.     class G6Error(Exception):
  11.         pass
  12.  
  13.     # Wyjątek pojawiający się przy próbie stworzenia grafu bez wierzchołków lub posiadającego > 10 wierzchołków.
  14.     class LimitError(Exception):
  15.         pass
  16.  
  17.     # Tworzy graf o podanej reprezentacji tekstowej (domyślnie: 1-wierzchołkowy graf pusty).
  18.     def __init__(self, text="@"):
  19.         self.__matrix = c_ulonglong(0)
  20.         self.__order = 1
  21.         self.fromString(text)
  22.  
  23.     # Zwraca liczbę wierzchołków grafu.
  24.     def order(self):
  25.         return self.__order
  26.  
  27.     # Dodaje do grafu nowy izolowany wierzchołek.
  28.     def addVertex(self):
  29.         if self.__order == 10:
  30.             raise AdjacencyMatrix64bit.LimitError("Graf nie może mieć więcej niż 10 wierzchołków")
  31.         for v in range(0, self.__order):
  32.             self.__matrix.value &= ~(1 << self.__indexInMatrix__(v, self.__order))
  33.         self.__order += 1
  34.         """
  35.        for v in range(self.__order):
  36.            self.__matrix[v] += [False]
  37.        self.__order += 1
  38.        self.__matrix += [[False] * self.__order]
  39.        """
  40.  
  41.     # Usuwa z grafu wskazany wierzchołek.
  42.     def deleteVertex(self, u):
  43.         if self.__order == 1:
  44.             raise AdjacencyMatrix64bit.LimitError("Graf musi mieć wierzchołki")
  45.         if type(u) != int or u < 0 or u >= self.__order:
  46.             raise ValueError
  47.         #wywala wszelkie krawedzie z tym wierzcholkiem
  48.         for v in range(0, self.__order):
  49.             self.__matrix &= ~(1 << self.__indexInMatrix__(v, u))
  50.  
  51.         temp = self.__matrix.value
  52.         return
  53.  
  54.         del self.__matrix[u]
  55.         for v in range(self.__order - 1):
  56.             del self.__matrix[v][u]
  57.         self.__order -= 1
  58.  
  59.     # Zwraca informację o tym, czy podane wierzchołki sąsiadują z sobą.
  60.     def isEdge(self, u, v):
  61.         return (self.__matrix.value & (1 << self.__indexInMatrix__(u, v))) != 0
  62.  
  63.     # Dodaje podaną krawędź.
  64.     def addEdge(self, u, v):
  65.         if type(u) != int or u < 0 or u >= self.__order:
  66.             raise ValueError
  67.         if type(v) != int or v < 0 or v >= self.__order:
  68.             raise ValueError
  69.         self.__matrix.value &= (1 << self.__indexInMatrix__(u, v))
  70.  
  71.     # Usuwa podaną krawędź.
  72.     def deleteEdge(self, u, v):
  73.         if type(u) != int or u < 0 or u >= self.__order:
  74.             raise ValueError
  75.         if type(u) != int or u < 0 or u >= self.__order:
  76.             raise ValueError
  77.         #self.__matrix[u][v] = self.__matrix[v][u] = False
  78.         self.__matrix.value &= ~(1 << self.__indexInMatrix__(u, v))
  79.  
  80.     # Przekształca reprezentację tekstową grafu w graf.
  81.     def fromString(self, text):
  82.         try:
  83.             t, k = iter(text), 0
  84.             c = ord(next(t)) - 63
  85.             if c < 1 or c > 10:
  86.                 raise AdjacencyMatrix64bit.G6Error("niewłaściwa liczba wierzchołków: {0}".format(c))
  87.             self.__order = c
  88.             self.__matrix = c_ulonglong(0)
  89.             for v in range(1, self.__order):
  90.                 for u in range(v):
  91.                     self.__matrix.value &= ~(1 << self.__indexInMatrix__(v, u))
  92.             for v in range(1, self.__order):
  93.                 for u in range(v):
  94.                     if k == 0:
  95.                         c = ord(next(t)) - 63
  96.                         if c < 0 or c > 63:
  97.                             raise AdjacencyMatrix64bit.G6Error("zakazany znak o kodzie {0}".format(c + 63))
  98.                         k = 6
  99.                     k -= 1
  100.                     if (c & (1 << k)) != 0:
  101.                         self.__matrix.value &= (1 << self.__indexInMatrix__(u, v))
  102.                         #self.__matrix[u][v] = self.__matrix[v][u] = True
  103.         except StopIteration:
  104.             raise AdjacencyMatrix64bit.G6Error("niekompletny napis")
  105.         try:
  106.             c = ord(next(t))
  107.             raise AdjacencyMatrix64bit.G6Error("nadmiarowy znak o kodzie {0}".format(c))
  108.         except StopIteration:
  109.             pass
  110.  
  111.     # Przekształca graf w reprezentację tekstową.
  112.     def __str__(self):
  113.         text, k, c = chr(self.__order + 63), 5, 0
  114.         for v in range(1, self.__order):
  115.             for u in range(v):
  116.                 if (self.__matrix.value & (1 << self.__indexInMatrix__(u, v))) != 0:
  117.                     c |= (1 << k)
  118.                 if k == 0:
  119.                     text += chr(c + 63)
  120.                     k, c = 6, 0
  121.                 k -= 1
  122.         if k != 5:
  123.             text += chr(c + 63)
  124.         return text
  125.  
  126.     # Test równości dwóch reprezentacji grafów.
  127.     def __eq__(self, other):
  128.         if self.__order != other.order():
  129.             return False
  130.         for v in range(1, self.__order):
  131.             for u in range(v):
  132.                 if self.isEdge(u, v) != other.isEdge(u, v):
  133.                     return False
  134.  
  135.         return True
  136.  
  137.     # Test różności dwóch reprezentacji grafów.
  138.     def __ne__(self, other):
  139.         if self.__order != other.order():
  140.             return True
  141.         for v in range(1, self.__order):
  142.             for u in range(v):
  143.                 if self.isEdge(u, v) != other.isEdge(u, v):
  144.                     return True
  145.         return False
  146.  
  147.     def __indexInMatrix__(self, v1, v2):
  148.         if v1 == v2:
  149.             return -1
  150.         v3 = 0
  151.         v4 = 0
  152.         if v2 > v1:
  153.             v3 = v1
  154.             v4 = v2
  155.         else:
  156.             v3 = v2
  157.             v4 = v1
  158.         #v3 to mniejszy, v4 to wiekszy
  159.         index = 0
  160.         step = 8
  161.         for i in range(0, v3):
  162.             index += step
  163.             step -= 1
  164.  
  165.         return index + v4 - 1
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement