CrackingtheCodingInterview/Nodes-Test.py at master · kcmasterpiece/CrackingtheCodingInterview · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
from Nodes import *
from igraph import *
import copy
from Chapter3Stacks import Queue

def createGraphNodesFromGraph(graph):
    myGraph = {}
    for v in g.vs:
        v['label'] = v.index
        if v.index not in myGraph:
            myGraph[v.index] = GraphNode(v.index)
        for n in v.neighbors():
            if n.index not in myGraph:
                myGraph[n.index] = GraphNode(n.index)
            myGraph[v.index].nodes.add(myGraph[n.index])
    return myGraph

def colorPlotBidirectionalSearch(graph, path, startVisited,endVisited, vertexStart, vertexEnd):
    for vertex in startVisited:
        v = graph.vs.find(vertex)
        print(startVisited)
        v['color'] = 'blue'

    for vertex in endVisited:
        print(endVisited)
        v = graph.vs.find(vertex)
        v['color'] = 'green'
    for i in range(len(path)):
        if i == 0:
            continue
        # print(path[i-1],path[i])
        edge = graph.es.find(_between=((path[i-1],), (path[i],)))
        edge['color'] = 'purple'

    vertexStart['color'] = 'purple'
    vertexEnd['color'] = 'purple'
    return

def breadthFirstSearchiGraph(graph, start, end):
    q = Queue()
    bfsVertexStart = graph.vs.find(start)
    bfsVertexEnd = graph.vs.find(end)
    parents = { bfsVertexStart.index : None }
    q.add(GraphNode(bfsVertexStart))
    while q.isEmpty() == False:
        vertex = q.remove().data
        vertex['color'] = 'green'
        vertex['label'] = vertex.index
        if vertex == bfsVertexEnd:
            parent = parents[vertex.index]
            while parent != None:
                parent['color'] = 'blue'
                parent = parents[parent.index]

            bfsVertexStart['color'] = 'purple'
            bfsVertexStart['label'] = bfsVertexStart.index
            bfsVertexEnd['label'] = bfsVertexEnd.index
            bfsVertexEnd['color'] = 'purple'
            layout = graph.layout_fruchterman_reingold()
            plot(graph, layout=layout)
            break
        for v in vertex.neighbors():
            if v['color'] != 'green':
                parents[v.index] = vertex
                # print(dir(v))
                q.add(GraphNode(v))
    return
g = Graph.Erdos_Renyi(n=75, m=75, directed=True)
# g_bfs = copy.deepcopy(g)
# myGraph = createGraphNodesFromGraph(g)
# graphKeys = list(myGraph)
# start = random.choice(graphKeys)
# graphKeys.remove(start)
# end = random.choice(graphKeys)
# vertexStart = g.vs.find(start)
# vertexEnd = g.vs.find(end)
# path, startVisited, endVisited = bidirectionalSearch(myGraph[start], myGraph[end])
# colorPlotBidirectionalSearch(g, path, startVisited,endVisited, vertexStart, vertexEnd)

# label vertices
for v in g.vs:
    v['label'] = v.index
# create arrows
for e in g.es:
    e['arrow_width'] = 0.75
    e['arrow_size'] = 0.75
layout = g.layout_fruchterman_reingold(area=1500000)
plot(g, layout=layout)