FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
async/async/graph.py at master · gitpython-developers/async · GitHub
This repository was archived by the owner on Apr 14, 2024. It is now read-only.
gitpython-developers
async
Repository navigation
Code
Issues
Pull requests
Actions
Security and quality
Insights
Expand file tree
Breadcrumbs
async
/
async
/
graph.py
Copy path
More file actions
More file actions
Latest commit
History
History
History
130 lines (106 loc) · 4 KB
Breadcrumbs
async
/
async
/
graph.py
Copy path
File metadata and controls
130 lines (106 loc) · 4 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
# Copyright (C) 2010, 2011 Sebastian Thiel (byronimo@gmail.com) and contributors
#
# This module is part of async and is released under
# the New BSD License: http://www.opensource.org/licenses/bsd-license.php
"""Simplistic implementation of a graph"""
__all__
=
(
'Node'
,
'Graph'
)
class
Node
(
object
):
"""A Node in the graph. They know their neighbours, and have an id which should
resolve into a string"""
__slots__
=
(
'in_nodes'
,
'out_nodes'
,
'id'
)
def
__init__
(
self
,
id
=
None
):
self
.
id
=
id
self
.
in_nodes
=
list
()
self
.
out_nodes
=
list
()
def
__str__
(
self
):
return
str
(
self
.
id
)
def
__repr__
(
self
):
return
"%s(%s)"
%
(
type
(
self
).
__name__
,
self
.
id
)
class
Graph
(
object
):
"""A simple graph implementation, keeping nodes and providing basic access and
editing functions. The performance is only suitable for small graphs of not
more than 10 nodes !"""
__slots__
=
"nodes"
def
__init__
(
self
):
self
.
nodes
=
list
()
def
__del__
(
self
):
"""Deletes bidericational dependencies"""
for
node
in
self
.
nodes
:
node
.
in_nodes
=
None
node
.
out_nodes
=
None
# END cleanup nodes
# otherwise the nodes would keep floating around
def
add_node
(
self
,
node
):
"""Add a new node to the graph
:return: the newly added node"""
self
.
nodes
.
append
(
node
)
return
node
def
remove_node
(
self
,
node
):
"""Delete a node from the graph
:return: self"""
try
:
del
(
self
.
nodes
[
self
.
nodes
.
index
(
node
)])
except
ValueError
:
return
self
# END ignore if it doesn't exist
# clear connections
for
outn
in
node
.
out_nodes
:
del
(
outn
.
in_nodes
[
outn
.
in_nodes
.
index
(
node
)])
for
inn
in
node
.
in_nodes
:
del
(
inn
.
out_nodes
[
inn
.
out_nodes
.
index
(
node
)])
node
.
out_nodes
=
list
()
node
.
in_nodes
=
list
()
return
self
def
add_edge
(
self
,
u
,
v
):
"""Add an undirected edge between the given nodes u and v.
:return: self
:raise ValueError: If the new edge would create a cycle"""
if
u
is
v
:
raise
ValueError
(
"Cannot connect a node with itself"
)
# are they already connected ?
if
u
in
v
.
in_nodes
and
v
in
u
.
out_nodes
or
\
v
in
u
.
in_nodes
and
u
in
v
.
out_nodes
:
return
self
# END handle connection exists
# cycle check - if we can reach any of the two by following either ones
# history, its a cycle
for
start
,
end
in
((
u
,
v
), (
v
,
u
)):
if
not
start
.
in_nodes
:
continue
nodes
=
start
.
in_nodes
[:]
seen
=
set
()
# depth first search - its faster
while
nodes
:
n
=
nodes
.
pop
()
if
n
in
seen
:
continue
seen
.
add
(
n
)
if
n
is
end
:
raise
ValueError
(
"Connecting u with v would create a cycle"
)
nodes
.
extend
(
n
.
in_nodes
)
# END while we are searching
# END for each direction to look
# connection is valid, set it up
u
.
out_nodes
.
append
(
v
)
v
.
in_nodes
.
append
(
u
)
return
self
def
input_inclusive_dfirst_reversed
(
self
,
node
):
"""Return all input nodes of the given node, depth first,
It will return the actual input node last, as it is required
like that by the pool"""
stack
=
[
node
]
seen
=
set
()
# depth first
out
=
list
()
while
stack
:
n
=
stack
.
pop
()
if
n
in
seen
:
continue
seen
.
add
(
n
)
out
.
append
(
n
)
# only proceed in that direction if visitor is fine with it
stack
.
extend
(
n
.
in_nodes
)
# END call visitor
# END while walking
out
.
reverse
()
return
out
Back
|
FazBrowse Home
|
New Git URL