API tools faq
paste
Advertisement
qberik

Untitled

qberik
Nov 27th, 2022
1,223
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 7.83 KB | None | 0 0
raw download clone embed print report
  1.  
  2. class Graph:
  3.     def __init__(self):
  4.         self.gr = []
  5.  
  6.     def from_sm( self, i ):
  7.         self.gr = i
  8.  
  9.     def from_in( self, I ):
  10.  
  11.         n = len( I )
  12.         self.gr = [ [ 0 for _ in range(n) ] for _ in range(n) ]
  13.         for j in range( len(I[0]) ):
  14.             ver = []
  15.             ver_id = []
  16.             for i in range( len(I) ):
  17.                 if( I[i][j] != 0 ):
  18.                     ver.append( I[i][j] )
  19.                     ver_id.append(i)
  20.  
  21.        
  22.  
  23.             if( len(ver) == 1 ):
  24.                 if( ver[0] != 2 ):
  25.                     raise ValueError("wrong edge nums")
  26.                 self.gr[ ver_id[0] ][ ver_id[0] ] = 2
  27.  
  28.             elif( len(ver) == 2 ):
  29.                 if( ver[0] < ver[1] ):
  30.                     ver[0],ver[1] = ver[1],ver[0]
  31.                     ver_id[0],ver_id[1] = ver_id[1],ver_id[0]
  32.  
  33.                 if( ver[0] == 1 and ver[1] == -1 ):
  34.                     #print( ver_id[0], ver_id[1], n )
  35.                     self.gr[ ver_id[0] ][ ver_id[1] ] = 1
  36.                 elif( ver[0] == 1 and ver[1] == 1 ):
  37.                     self.gr[ ver_id[0] ][ ver_id[1] ] = 1
  38.                     self.gr[ ver_id[1] ][ ver_id[0] ] = 1
  39.                 else:
  40.                     raise ValueError("wrong edge nums")
  41.  
  42.             else:
  43.                 raise ValueError("wrong len of ver")
  44.  
  45.  
  46.  
  47.     def to_sm( self ):
  48.         return self.gr        
  49.  
  50.  
  51.     def to_in( self ):
  52.        
  53.         n = len( self.gr )
  54.         inc = []
  55.         for i in range(n):
  56.             for j in range( n-i - 1 ):
  57.                 if( self.gr[i][1+i+j] != 0 or self.gr[1+i+j][i] != 0 ):
  58.                     inc.append([0 for _ in range(n) ])
  59.                     if( self.gr[i][1+i+j] == 0 and self.gr[1+i+j][i] == 1 ):
  60.                         inc[-1][i] = -1
  61.                         inc[-1][1+i+j] = 1
  62.                     elif( self.gr[i][1+i+j] == 1 and self.gr[1+i+j][i] == 0 ):
  63.                         inc[-1][i] = 1
  64.                         inc[-1][1+i+j] = -1
  65.                     elif( self.gr[i][1+i+j] == 1 and self.gr[1+i+j][i] == 1 ):
  66.                         inc[-1][i] = 1
  67.                         inc[-1][1+i+j] = 1
  68.  
  69.         for i in range(n):
  70.             if self.gr[i][i] == 2:
  71.                 inc.append([0 for _ in range(n) ])
  72.                 inc[-1][i] = 2
  73.  
  74.         inc_t = [ [ inc[i][j] for i in range(len(inc)) ] for j in range(len( inc[0])) ]
  75.  
  76.         return inc_t
  77.  
  78.     def ver_count( self ):
  79.         return len( self.gr )
  80.  
  81.     def edg_count( self ):
  82.         return len( self.to_in()[0] )
  83.  
  84.     def sm_list( self ):
  85.         lines = []
  86.         for i in range( len(self.gr) ):
  87.             l = []
  88.             for j in range( len(self.gr[0]) ):
  89.                 if self.gr[i][j] != 0:
  90.                     l.append(j)
  91.             lines.append( l )
  92.         return lines
  93.  
  94.     def sm_list_r( self ):
  95.         lines_in = []
  96.         lines_out = []
  97.         for i in range( len(self.gr) ):
  98.             li = []
  99.             lo = []
  100.             for j in range( len(self.gr[0]) ):
  101.                 if self.gr[i][j] != 0:
  102.                     if i < j:
  103.                         lo.append(j)
  104.                     else:
  105.                         li.append(j)
  106.             lines_in.append( li )
  107.             lines_out.append( lo )
  108.         return lines_in, lines_out
  109.  
  110.     def is_ograph( self ):
  111.         n = len( self.gr )
  112.         for i in range(n):
  113.             for j in range( n-i - 1 ):
  114.                 if( self.gr[i][1+i+j] != 0 and self.gr[1+i+j][i] != 0 ):
  115.                     if( self.gr[i][1+i+j] != self.gr[1+i+j][i] ):
  116.                         return False
  117.         return True
  118.  
  119.     def step_posl( self ):
  120.         if self.is_ograph():
  121.             return self.polu_step_posl()
  122.         l = self.sm_list()
  123.         c = [ len(i) for i in l ]
  124.         return c
  125.  
  126.     def polu_step_posl( self ):
  127.         li, lo = self.sm_list_r()
  128.         c1 = [ len(i) for i in li ]
  129.         c2 = [ len(i) for i in lo ]
  130.         c = [ (c1[i],c2[i]) for i in range( len(c1 ) ) ]
  131.         return c
  132.  
  133.  
  134.     def del_ver( self, i ):
  135.         i -= 1
  136.         for line in self.gr:
  137.             line.pop( i )
  138.         self.gr.pop( i )
  139.  
  140.     def add_ver( self, i ):
  141.         n = len( self.gr )
  142.         i -= 1
  143.         new_l = [ 0 for _ in range( n + 1 ) ]
  144.         for line in self.gr:
  145.             line.insert(i,0)
  146.         self.gr.insert(i,new_l)
  147.  
  148.     def del_edg( self, e ):
  149.         a,b = e
  150.         a -= 1
  151.         b -= 1
  152.         if( self.gr[a][b] == self.gr[b][a] == 1 ):
  153.             self.gr[a][b] = 0
  154.             self.gr[b][a] = 0
  155.         if( self.gr[a][b] == 1 ):
  156.             self.gr[a][b] = 0
  157.  
  158.     def add_edg( self, e, pos = False):
  159.         a,b = e
  160.         a -= 1
  161.         b -= 1
  162.         self.gr[a][b] = 1
  163.         if not pos :
  164.             self.gr[b][a] = 1
  165.  
  166.  
  167.     def dop(self):
  168.         n = len(self.gr)
  169.         g = [ [ 0 for _ in range(n) ] for _ in range(n) ]
  170.  
  171.         for i in range( n ):
  172.             for j in range( n ):
  173.                 if self.gr[i][j] != 0:
  174.                     g[i][j] = 0
  175.                 else:
  176.                     g[i][j] = 1
  177.                     if i == j:
  178.                         g[i][j] = 2
  179.         return g
  180.  
  181.     def out( self ):
  182.         print_matr( self.gr )
  183.  
  184.  
  185. def print_matr( m ):
  186.     for l in m:
  187.         print( l )
  188.  
  189.  
  190.  
  191.  
  192.  
  193. def task_1( G ):
  194.     print( "vertices count" )
  195.     print( G.ver_count() )
  196.     print( "edge count" )
  197.     print( G.edg_count() )
  198.     print( "adjacency lists" )
  199.     print_matr( G.sm_list() )
  200.     print( "power sequences" )
  201.     print_matr( G.step_posl() )
  202.  
  203.  
  204.  
  205.  
  206.  
  207. if __name__ == "__main__":
  208.     G_1=[[0, 1, 1, 0, 0, 0, 0, 0, 0, 1],
  209.     [1, 0, 1, 1, 0, 0, 1, 1, 0, 0],
  210.     [1, 1, 0, 1, 0, 1, 0, 0, 1, 1],
  211.     [0, 1, 1, 0, 0, 1, 1, 1, 0, 0],
  212.     [0, 0, 0, 0, 0, 1, 0, 1, 1, 1],
  213.     [0, 0, 1, 1, 1, 0, 1, 1, 0, 0],
  214.     [0, 1, 0, 1, 0, 1, 0, 1, 1, 0],
  215.     [0, 1, 0, 1, 1, 1, 1, 0, 0, 0],
  216.     [0, 0, 1, 0, 1, 0, 1, 0, 0, 1],
  217.     [1, 0, 1, 0, 1, 0, 0, 0, 1, 0],]
  218.     G_2=[[1, 1, 0, 0, 1, 1, 1],
  219.     [1, 0, 1, 1, 0, 0, 0],
  220.     [0, 1, 0, 1, 0, 0, 0],
  221.     [0, 0, 0, 0, 1, 0, 0],
  222.     [0, 0, 0, 0, 0, 1, 0],
  223.     [0, 0, 1, 0, 0, 0, 1],]
  224.     G_3=[[1, 0, 0, 0, 0, 0],
  225.     [-1, -1, -1, -1, -1, -1],
  226.     [0, 1, 0, 0, 0, 0],
  227.     [0, 0, 1, 0, 0, 0],
  228.     [0, 0, 0, 1, 0, 0],
  229.     [0, 0, 0, 0, 1, 0],
  230.     [0, 0, 0, 0, 0, 1],]
  231.  
  232.     v_i=[11, 12, 7, 8, 9, 8, 3]
  233.     e_i=[(4,11), (9,11), (11,11), (1, 9), (5,11), (3,4), (4,6)]
  234.     f_i=[(1,4), (4,3), (5,7),(7,2)]
  235.  
  236.     G1 = Graph()
  237.     G1.from_sm(G_1)
  238.     G2 = Graph()
  239.     G2.from_in(G_2)
  240.     G3 = Graph()
  241.     G3.from_in(G_3)
  242.  
  243.     #G2.out()
  244.  
  245.     print(  "for G1" )
  246.     task_1( G1 )
  247.    
  248.     print(  "for G2" )
  249.     task_1( G2 )
  250.    
  251.     print(  "for G3" )
  252.     task_1( G3 )
  253.  
  254.     print("incidence matrix for G1")
  255.     print_matr( G1.to_in() )
  256.     print("adjacency matrix for G2")
  257.     print_matr( G2.to_sm() )
  258.     print("adjacency matrix for G3")
  259.     print_matr( G3.to_sm() )
  260.  
  261.  
  262.     print( "task_2" )
  263.  
  264.     print( "new G1" )
  265.     print_matr( G1.to_sm() )
  266.  
  267.     G1.add_ver(v_i[0])
  268.     G1.add_ver(v_i[1])
  269.     G1.del_ver(v_i[2])
  270.  
  271.     print( "new G1" )
  272.     print_matr( G1.to_sm() )
  273.  
  274.     G1.add_edg(e_i[0])
  275.     G1.add_edg(e_i[1])
  276.     G1.add_edg(e_i[2])
  277.     G1.add_edg(e_i[3])
  278.     G1.add_edg(e_i[4])
  279.     G1.del_edg(e_i[5])
  280.     G1.del_edg(e_i[6])
  281.  
  282.     print( "G4" )
  283.     print_matr( G1.to_sm() )
  284.  
  285.  
  286.  
  287.     G3.add_ver(v_i[3])
  288.     G3.add_ver(v_i[4])
  289.     G3.add_ver(v_i[5])
  290.     G3.del_ver(v_i[6])
  291.  
  292.  
  293.     G3.add_edg(f_i[0],True)
  294.     G3.add_edg(f_i[1],True)
  295.     G3.add_edg(f_i[2],True)
  296.     G3.del_edg(f_i[3])
  297.  
  298.     print( "new G3" )
  299.     print_matr( G3.to_in() )
  300.  
  301.     G3.add_edg(f_i[3],True)
  302.     G3.del_edg(f_i[2])
  303.     G3.del_edg(f_i[1])
  304.     G3.del_edg(f_i[0])
  305.  
  306.     G3.add_ver(v_i[6])
  307.     G3.del_ver(v_i[3])
  308.     G3.del_ver(v_i[4])
  309.     G3.del_ver(v_i[5])
  310.  
  311.  
  312.     print( "new G3" )
  313.     print_matr( G3.to_in() )
  314.  
  315.  
  316.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!