This repository has been archived by the owner on Oct 8, 2021. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 184
/
graph.jl
111 lines (93 loc) · 2.57 KB
/
graph.jl
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
type Graph<:AbstractGraph
vertices::UnitRange{Int}
edges::Set{Edge}
finclist::Vector{Vector{Edge}} # [src]: ((src,dst), (src,dst), (src,dst))
binclist::Vector{Vector{Edge}} # [dst]: ((src,dst), (src,dst), (src,dst))
end
function show(io::IO, g::Graph)
if length(vertices(g)) == 0
print(io, "empty undirected graph")
else
print(io, "{$(nv(g)), $(ne(g))} undirected graph")
end
end
function Graph(n::Int)
finclist = Vector{Edge}[]
binclist = Vector{Edge}[]
sizehint!(binclist,n)
sizehint!(finclist,n)
for i = 1:n
# sizehint!(i_s, n/4)
# sizehint!(o_s, n/4)
push!(binclist, Edge[])
push!(finclist, Edge[])
end
return Graph(1:n, Set{Edge}(), binclist, finclist)
end
Graph() = Graph(0)
function Graph{T<:Number}(adjmx::Array{T, 2})
dima, dimb = size(adjmx)
if dima != dimb
error("Adjacency / distance matrices must be square")
else
g = Graph(dima)
for i=1:dima, j=i:dima
if adjmx[i,j] > 0 && !isinf(adjmx[i,j])
add_edge!(g,i,j)
end
end
end
return g
end
function Graph(g::DiGraph)
gnv = nv(g)
h = Graph(gnv)
for e in edges(g)
if !has_edge(h, e)
add_edge!(h, e)
end
end
return h
end