In [1]:

    

import numpy as np
import pandas as pd


    

In [3]:

    

# from operator import itemgetter, attrgetter
def BFS(graph, start):
    queue = list()
    most = dict()
    visited = set()
    queue.append(start)
    while queue:
        node = queue.pop(0)
        visited.add(node)
        if node in most:
            most[node][0] = len(graph[node])
        else:
            most[node] = [len(graph[node]), 0];
        for adjacent in graph[node]:
            #LOGICA DO QUE A GENTE QUER
            if adjacent in most:
                    most[adjacent][1] += 1;
            else:
                most[adjacent] = [0, 1];
            if adjacent not in visited:
                visited.add(adjacent)
                if adjacent in graph:
                    queue.append(adjacent)
                
    # print(most)
    #SORT MOST EM [0] e depois em [1]
    
    def s(t):
        v = t[1]
        return -v[0], -v[1]

    # sorted(d.items(), key=lambda (y,x): (-x[0], -x[1]))
    return sorted(most.items(), key=s)


    

In [8]:

    

file_name = 'real1'
mt = np.genfromtxt('networks/' + file_name + '.csv',delimiter=',').astype(np.int32)


    

In [9]:

    

network = {}
for row in mt:
    source = row[0]
    target = row[1]
    if source not in network:
        network[source] = set()
    network[source].add(target)
        
# print(graph)


    

In [10]:

    

print(len(network))


    

    




965796

In [21]:

    

from pprint import pprint
pprint(list(network.keys())[-10:])


    

    




[1694602,
 1694604,
 1694605,
 1694606,
 1694607,
 1694608,
 1694610,
 1694612,
 1694613,
 1694614]

In [11]:

    

result = BFS(network, 0)
# print(len(result))
# print(result[:30])


    

In [22]:

    

print(len(result))
print(result[-30:])


    

    




1694616
[(1694543, [0, 1]), (1694545, [0, 1]), (1694551, [0, 1]), (1694552, [0, 1]), (1694555, [0, 1]), (1694557, [0, 1]), (1694558, [0, 1]), (1694560, [0, 1]), (1694562, [0, 1]), (1694565, [0, 1]), (1694566, [0, 1]), (1694567, [0, 1]), (1694568, [0, 1]), (1694569, [0, 1]), (1694571, [0, 1]), (1694573, [0, 1]), (1694574, [0, 1]), (1694575, [0, 1]), (1694576, [0, 1]), (1694577, [0, 1]), (1694579, [0, 1]), (1694581, [0, 1]), (1694586, [0, 1]), (1694589, [0, 1]), (1694591, [0, 1]), (1694593, [0, 1]), (1694594, [0, 1]), (1694603, [0, 1]), (1694609, [0, 1]), (1694611, [0, 1])]

In [87]:

    

graph = { 'A': ['B', 'C'],
          'B': ['A', 'C'],
          'C': ['B', 'D', 'E' ,'F'],
          'D': ['E'],
          'E': ['C'],
          'F': ['B', 'D'],
          'G': ['H'],
          'H': ['G']}


    

In [16]:

    

def BFS(graph, start):
    queue = []
    visited = set()
    queue.append(start)
    while queue:
        node = queue.pop(0)
        visited.add(node)
        for adjacent in graph[node]:
            if adjacent not in visited:
                queue.append(adjacent)
                visited.add(adjacent)
                
    print(visited)


    

In [102]:

    

def s(t):
    v = t[1]
    return -v[0], -v[1]

# sorted(d.items(), key=lambda (y,x): (-x[0], -x[1]))
sorted(d.items(), key=s)


    

    
Out[102]:





[('b', [4, 5]), ('a', [3, 2])]

In [ ]:

    

graph = { 'A': ['B', 'C'],
          'B': ['A', 'C'],
          'C': ['B', 'D', 'E' ,'F'],
          'D': ['E'],
          'E': ['C'],
          'F': ['B', 'D'] }

def BFS(graph, start, end):
    parent = {}
    queue = []
    queue.append(start)
    while queue:
        node = queue.pop(0)
        if node == end:
            return backtrace(parent, start, end)
        for adjacent in graph.get(node, []):
            parent[adjacent] = node 
            queue.append(adjacent)

def backtrace(parent, start, end):
    path = [end]
    while path[-1] != start:
        path.append(parent[path[-1]])
    path.reverse()
    return path

print (BFS(graph, 'A', 'E'))


    

In [ ]:

    

BFS(G,s)
1.  for each vertex u ∈ G.V - {s}
2.     u.color == WHITE
3.     u.d = INF
4.     u.pi = NIL
5.  s.color = GRAY
6.  s.d = 0
7.  s.pi = NIL
8.  Q = ∅
9.  ENQUEUE(Q,s)
10. while Q ≠ ∅
11.    u = DEQUEUE(Q)
12.    for each v ∈ G.Adj[u]
13.       if v.color == WHITE
14.          v.color = GRAY
15.          v.d = u.d + 1
16.          v.pi = u
17.          ENQUEUE(Q,v)
18.    u.color = BLACK


    

In [ ]:

    

# G que tem a propriedade V, vértices
def BFS(G, s):
    for each vertex in G[V] - [s]:


    

In [ ]:

    

def bfs(graph, root):
    S = set()
    Q = list()
    
    S.add(root)
    Q.append(root)
    
    while len(Q) is not 0:
        current = Q.pop()
        if current