Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
courses:be5b33alg:summer_course [2018/06/16 14:25]
berezovs
courses:be5b33alg:summer_course [2018/08/27 07:49] (current)
berezovs [6. Monday 27.8.: Individual graph problems]
Line 30: Line 30:
  
 [[https://​cw.fel.cvut.cz/​old/​courses/​be5b33prg/​tutorials/​start| Tutorials of the  be5b33prg course]] [[https://​cw.fel.cvut.cz/​old/​courses/​be5b33prg/​tutorials/​start| Tutorials of the  be5b33prg course]]
 +
 +**Programming problems**\\
 +
 +**1.1.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=xtestovaci|Introductory Example problem]]\\
 +**1.2.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=xfence|2nd Introductory Example problem]]\\
  
  
Line 38: Line 43:
 Tree representation in computer memory and in text files, queue, tree traversal, recursive tree traversal. Tree representation in computer memory and in text files, queue, tree traversal, recursive tree traversal.
  
 +**Programming problems**\\
 +
 +**2.1.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=sumleaves_py|Sum of Keys in the Leaves]]\\
 +**2.2.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=stars_py|Regular Stars]]\\
 +**2.3.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=pary_py|Neighbour pairs]]\\
 +**2.4.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=danglingpaths_py|Dangling Paths in a Binary Tree]]\\
 ---- ----
  
Line 43: Line 54:
  
 Graph representation in computer memory and in text files, adjacency matrix, linked list representation,​ node degrees, exploring immediate nodes neighbourhood. Graph representation in computer memory and in text files, adjacency matrix, linked list representation,​ node degrees, exploring immediate nodes neighbourhood.
 +
 +**Programming problems**\\
 +
 +**3.1.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=championship_py|Chess Championship Sites]]\\
 +**3.2.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=irreduciblepaths_py|Short Irreducible paths]]\\
 +**3.3.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=lakeswaterfalls_py|Lakes and Waterfalls]]\\
 +**3.4.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=colorgraph7|Color Graph VII]]\\
  
 ---- ----
Line 49: Line 67:
  
 Queue and breadth-first search, stack and depth-first search, graph connectivity. Queue and breadth-first search, stack and depth-first search, graph connectivity.
 +
 +**Programming problems**\\
 +
 +**4.1.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=criticalnetworks_py|Critical Networks]]\\
 +**4.2.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=fixednodes_py|Fixed Nodes]]\\
 +**4.3.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=championship_dist_py|Chess Championship Distant Sites]]\\
 +**4.4.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=colorgraphII|Colorgraph II]]\\
  
 ---- ----
Line 55: Line 80:
  
 Exploring connected components, computing distances between nodes, reconstructing shortest paths. Exploring connected components, computing distances between nodes, reconstructing shortest paths.
 +
 +**Programming problems**\\
 +
 +**5.1.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=colorgraph4|Colorgraph IV]]\\
 +**5.2.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=networkcycle_py|Network Cycle]]\\
 +**5.3.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=colorgraph6| Colorgraph VI]]\\
 +**5.4.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=cavetrips_py|Cave Trips]]\\
 +
  
 ---- ----
Line 61: Line 94:
  
 Graphs with simple additional node/edge properties, node/​edge ​ weights or colors, searching for sets of edges/nodes with specific properties. Graphs with simple additional node/edge properties, node/​edge ​ weights or colors, searching for sets of edges/nodes with specific properties.
 +
 +**Programming problems**\\
 +
 +**6.1.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=giraffes_py|Safe Giraffes Transport]]\\
 +**6.2.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=colortokens_py|Color Tokens]]\\
 +**6.3.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=separatingedges_py|Simply Separating Edges]]\\
 +**6.4.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=longestpath|Longest Path in a Network]]\\
 +**6.5.** [[https://​cw.felk.cvut.cz/​brute/​data/​ae/​release/​2018l_be5b33alg/​alg_ae/​evaluation/​input.php?​task=fullpaths|Full Paths in Binary Tree]]\\
 +**6.6.** [[https://​cw.felk.cvut.cz/​courses/​a4b33alg/​task.php?​task=moleculecomplexes|Molecule Complexes on Semipermeable Membranes]]\\
  
 ---- ----
Line 70: Line 112:
 ---- ----
  
 +**Irreducible paths example code**
 +
 +----
 +<​code>​
 +import time
 +import math
 +
 +class Graph:
 +
 +    def __init__(self,​ n):  # create a graph with no edges
 +        self.size = n
 +        self.edges = [[] for i in range(n)]
 +        self.paths = 0
 +
 +    def addedge(self,​ inode1, inode2):
 +        self.edges[inode1].append(inode2)
 +        self.edges[inode2].append(inode1)
 +
 +    def isedge( self, a, b ):
 +        if( len(self.edges[a]) > len(self.edges[b]) ):
 +            x = a; a = b; b = x;
 +        # binary search
 +        i1 = 0; i3 = len(self.edges[a])-1
 +        while i1 < i3:
 +            i2 = (i1 + i3)//​2 ​              # in Python no risk of overflow
 +            if self.edges[a][i2] < b: i1 = i2+1
 +            else:                     i3 = i2
 +        if self.edges[a][i1] == b: return True
 +        return False          # else not found
 +
 +    def print(self):​
 +        for n, neighs in enumerate(self.edges):​
 +            print(str(n) + "​__",​ neighs)
 +        print("​------------------------------------------------"​)
 +
 +    def countpaths(self):​
 +        for b in range(0, len(self.edges)):​
 +            for c in self.edges[b]:​
 +                if c > b:
 +                    for a in self.edges[b]:​
 +                        if a == c: continue
 +                        for d in self.edges[c]:​
 +                            if d == a or d == b: continue
 +                            if not self.isedge(a,​c) and not self.isedge(a,​d) and not self.isedge(b,​d):​
 +                                self.paths += 1
 +                                print( a, "​-",​ b, "​-",​ c, "​-",​ d )
 +                                # print( a, "&​ndash;",​ b, "&​ndash;",​ c, "&​ndash;",​ d )
 +
 +    def loadFromInput(self):​
 +        self.size, E = map(int, input().split())
 +        self.edges = [[] for i in range(self.size)]
 +        for i in range(E):
 +            n1, n2 = map(int, input().split())
 +            self.addedge(n1,​ n2)
 +        for i in range(self.size):​
 +            self.edges[i].sort()
 +
 +# ............................................................................
 +#                              M A I N
 +# ............................................................................
 +
 +time1 = time.time()
 +
 +g = Graph(0)
 +g.loadFromInput()
 +time2 = time.time()
 +g.print()
 +#​g.countpaths()
 +time3 = time.time()
 +
 +# print(g.paths)
 +</​code>​
 +----
 +
 +
 +**Fixed Nodes example solution**
 +
 +<​code>​
 +
 +from queue import *
 +
 +class Graph:
 +
 +    def __init__(self): ​ # just empty graph
 +        pass
 +
 +    def addedge(self,​ inode1, inode2):
 +        self.edges[inode1].append(inode2)
 +        self.edges[inode2].append(inode1)
 +
 +    def BFSdistancesFromUpToD(self,​ n):
 +        for i in range( self.size ):
 +            self.dist[i] = 1000000
 +
 +        self.dist[n] = 0
 +        q = Queue()
 +        q.put(n)
 +        while not q.empty():
 +            n = q.get()
 +            for neigh in self.edges[n]:​
 +                if self.dist[neigh] == 1000000:
 +                    self.dist[neigh] = self.dist[n] + 1
 +                    if self.dist[neigh] == self.D:
 +                        self.inDistD[neigh] += 1
 +                    else:
 +                        q.put(neigh)
 +
 +
 +    def solve(self):​
 +        for i in range( self.size ):
 +            if self.isBlue[i]:​
 +                self.BFSdistancesFromUpToD( i )
 +                #print( "dists from blue ", i )
 +                #print( self.dist )
 +        counter = 0
 +        for i in range( self.size ):
 +            if self.inDistD[i] == self.K:
 +                counter += 1
 +                #print( 'found node ' ,  i )
 +        print( counter )
 +        #print( self.inDistD )
 +
 +
 +    def loadFromInput(self):​
 +        self.size, E, self.K, self.D = map(int, input().split())
 +        self.edges = [[] for i in range(self.size)]
 +        self.inDistD = [0] * self.size ​ # infinity distance
 +        self.dist = [0] * self.size ​ # infinity distance
 +
 +        self.isBlue = [False] * self.size
 +        vv = input().split()
 +        uu = []
 +        for i in range(1, len(vv) ):
 +            self.isBlue[ int( vv[i]) ] = True
 +
 +        for i in range(E):
 +            n1, n2 = map(int, input().split())
 +            self.addedge(n1,​ n2)
 +        for i in range(self.size):​
 +            self.edges[i].sort()
 +
 +
 +    def print(self):​
 +        for node in range(self.size):​
 +            print( node, end = " ")
 +            print( self.edges[node] )
 +
 +
 +# ............................................................................
 +#                              M A I N
 +# ............................................................................
 +
 +g = Graph()
 +g.loadFromInput()
 +g.solve()
 +
 +
 +'''​
 +9 12 2 1
 +4 2 3 4 5
 +0 1
 +1 2
 +3 4
 +4 5
 +6 7
 +7 8
 +0 3
 +3 6
 +1 4
 +4 7
 +2 5
 +5 8
 +
 +10 18 1 3
 +3 0 6 8
 +1 2
 +3 4
 +4 5
 +6 7
 +7 8
 +8 9
 +0 1
 +1 3
 +3 6
 +2 4
 +4 7
 +5 8
 +0 2
 +2 5
 +5 9
 +1 4
 +4 8
 +3 7
 +
 +10 18 2 2
 +3 0 6 8
 +1 2
 +3 4
 +4 5
 +6 7
 +7 8
 +8 9
 +0 1
 +1 3
 +3 6
 +2 4
 +4 7
 +5 8
 +0 2
 +2 5
 +5 9
 +1 4
 +4 8
 +3 7
 +
 +
 +'''​
 +
 +</​code>​
 +----
 +**Chess Championship Sites**
 +
 +<​code>​
 +import time
 +import math
 +import sys
 +
 +class Graph:
 +
 +    def __init__(self,​ n):  # discrete graph with no edges
 +        self.size = n
 +        self.edges = [[] for i in range(n)]
 +        self.triangles = 0
 +        self.neighchecks = 0
 +
 +    def addedge(self,​ inode1, inode2):
 +        self.edges[inode1].append(inode2)
 +        self.edges[inode2].append(inode1)
 +
 +    def isedge(self,​ n1, n2):
 +        self.neighchecks += 1
 +        return n2 in self.edges[n1]
 +
 +    def print(self):​
 +        for n, neighs in enumerate(self.edges):​
 +            print(str(n) + "​__",​ neighs)
 +        print("​------------------------------------------------"​)
 +
 +    def countTrianglesAtNode(self,​ x):
 +        #​print("​searching from node", x)
 +        for n1 in self.edges[x]:​
 +            for n2 in self.edges[x]:​
 +                if  n1 < n2 and self.isedge(n1,​ n2):
 +                    #print(x, "​-",​ n1, "​-",​ n2)
 +                    self.triangles += 1
 +
 +    def countTriangles(self):​
 +        for n in range(self.size):​
 +            self.countTrianglesAtNode(n)
 +        print( "tri count: ", self.triangles // 3 )
 +        print( "neigh checks:",​ self.neighchecks)
 +
 +    def loadFromInput(self):​
 +        self.size, E = map(int, input().split())
 +        self.edges = [[] for i in range(self.size)]
 +        self.triangles = 0
 +        for i in range(E):
 +            n1, n2 = map(int, input().split())
 +            self.addedge(n1,​ n2)
 +        for i in range(self.size):​
 +            self.edges[i].sort()
 +
 +
 +# ............................................................................
 +#                              M A I N
 +# ............................................................................
 +
 +time1 = time.time()
 +g = Graph(0)
 +
 +g.loadFromInput()
 +time2 = time.time()
 +#g.print()
 +
 +g.countTriangles()
 +time3 = time.time()
 +
 +# print(g.triangles)
 +print("​time read       %6d ms" % int(math.floor((time2 - time1) * 1000)) )
 +print("​time count      %6d ms" % int(math.floor((time3 - time2) * 1000)) )
 +print("​time total      %6d ms" % int(math.floor((time3 - time1) * 1000)) )
 +sys.stderr.write( 'time: ' + str(int(math.floor((time3 - time1) * 1000))) )
  
 +'''​
 +small example
 +5 6
 +0 1
 +1 2
 +1 3
 +1 4
 +2 4
 +3 4
 +'''​
 +</​code>​
  
courses/be5b33alg/summer_course.1529151917.txt.gz ยท Last modified: 2018/06/16 14:25 by berezovs