# GraphsLibHelperFunctions.jl

May 10th, 2014
472
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #####
2. ### The code below is written by Benjamin Lind under CC: BY-NC-SA 3.0
3. ### If you use or develop this code, please provide proper attribution.
4. ### You may contact me at lind.benjamin//at//gmail//d0t//com
5. ### You may also find me @benjaminlind on Twitter
6. #####
7.
8. using Graphs
9.
10. #####
11. ### Convenient helper functions for the Graphs library in the language of Julia
12. ### These do not call on any other library and are written entirely in Julia
14. #####
15.
16. ### To load these functions:
18.
19.
20. ### el_2_graph converts an edgelist to a GenericGraph type
21. ## They vary based upon string or integer inputs.
22. ## They can accept the number of vertices or vertex names are supplied.
23. ## If the number of vertices or names are not supplied, then the information is inferred from the edgelist
24.
25. function el_2_graph(n::Int, el::Array{Int, 2}; directed::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
26. # _n_ refers to the number of vertices in the graph
27. # _el_ is an integer only edgelist
28.
29. vertexnames = [el[:,1], el[:,2]]
30. vertexnames = unique(vertexnames)
31. if (minimum(vertexnames) < 1) | (n < 1)
32. error("The number of vertices ('n') and the vertex indices must be greater than or equal to 1.")
33. end
34. n = ifelse(maximum(vertexnames) > n, maximum(vertexnames), n)
35. ne = size(el, 1)
36. if vtype == KeyVertex
37. vlist = Array(vtype{Int}, n)
38. for i = 1:n
39. vlist[i] = vtype(i, i)
40. end
41. elseif vtype == ExVertex
42. vlist = Array(vtype, n)
43. for i = 1:n
44. vlist[i] = vtype(i, string(i))
45. end
46. else
47. error("'vtype' must be either KeyVertex or ExVertex")
48. end
49. elist = Array(etype{typeof(vlist[1])}, ne)
50. for i = 1:ne
51. elist[i] = etype(i, vlist[el[i, 1]], vlist[el[i, 2]])
52. end
53. return graph(vlist, elist, is_directed = directed)
54. end
55.
56. function el_2_graph(el::Array{Int, 2}; directed::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
57. # _el_ is an integer only edgelist
58.
59. vertexnames = [el[:,1], el[:,2]]
60. vertexnames = unique(vertexnames)
61. n = maximum(vertexnames)
62. return el_2_graph(n, el; directed = directed, vtype = vtype, etype = etype)
63. end
64.
65. function el_2_graph(v::Array{String, 1}, el::Array{String, 2}; directed::Bool = true, label::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
66. # _v_ is a list of vertex "names"
67. # _el_ is an edgelist of vertex "names"
68.
69. v = unique(v) #In case of double entries
70. vertexnames = [el[:,1], el[:,2]]
71. vertexnames = unique(vertexnames)
72. for i = 1:length(vertexnames)
73. if in(vertexnames[i], v) == false
74. vunnamed = vertexnames[i]
75. warn("Vertex \$vunnamed appears in the edge list 'el' but not in the vertex list 'v'. Including \$vunnamed in 'v'.")
76. push!(v, vunnamed)
77. end
78. end
79. n = length(v)
80. ne = size(el, 1)
81. if label
82. if vtype == KeyVertex
83. vlist = Array(vtype{typeof(v[1])}, n)
84. elseif vtype == ExVertex
85. vlist = Array(vtype, n)
86. else
87. error("'vtype' must be either KeyVertex or ExVertex")
88. end
89. for i = 1:n
90. vlist[i] = vtype(i, v[i])
91. end
92. else
93. if vtype == KeyVertex
94. vlist = Array(vtype{Int}, n)
95. for i = 1:n
96. vlist[i] = vtype(i, i)
97. end
98. elseif vtype == ExVertex
99. vlist = Array(vtype, n)
100. for i = 1:n
101. vlist[i] = vtype(i, string(i))
102. end
103. else
104. error("'vtype' must be either KeyVertex or ExVertex")
105. end
106. end
107. elist = Array(etype{typeof(vlist[1])}, ne)
108. for i = 1:ne
109. elist[i] = etype(i, vlist[findin([v], [el[i, 1]])[1]], vlist[findin([v], [el[i, 2]])[1]])
110. end
111. return graph(vlist, elist, is_directed = directed)
112. end
113.
114. function el_2_graph(el::Array{String, 2}; directed::Bool = true, label::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
115. # _el_ is an edgelist of vertex "names"
116. v = unique([el[:,1], el[:,2]])
117. return el_2_graph(v, el, directed = directed, label = label, vtype = vtype, etype = etype)
118. end
119.
120. function el_2_graph(v::Array{String, 1}, el::Array{Int, 2}; directed::Bool = true, label::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
121. # _v_ is a list of vertex "names"
122. # _el_ is an integer only edgelist
123. if any(el .> length(v))
124. error("The number of indexes referenced in 'el' exceeds the number of vertices provided.")
125. end
126. eldim = size(el)
127. newel = Array(String, eldim[1], eldim[2])
128. for i = 1:eldim[1]
129. newel[i,:] = [v[el[i, 1]], v[el[i, 2]]]
130. end
131.
132. return el_2_graph(v, newel, directed = directed, label = label, vtype = vtype, etype = etype)
133. end
134.
135. function el_2_graph(v::Array{UTF8String, 1}, el::Array{UTF8String, 2}; directed::Bool = true, label::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
136. v = convert(Array{String, 1}, v)
137. el = convert(Array{String, 2}, el)
138. return el_2_graph(v, el, directed = directed, label = label, vtype = vtype, etype = etype)
139. end
140.
141. function el_2_graph(el::Array{UTF8String, 2}; directed::Bool = true, label::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
142. el = convert(Array{String, 2}, el)
143. return el_2_graph(el, directed = directed, label = label, vtype = vtype, etype = etype)
144. end
145.
146. function el_2_graph(v::Array{UTF8String, 1}, el::Array{Int, 2}; directed::Bool = true, label::Bool = true, vtype::DataType = KeyVertex, etype::DataType = Edge)
147. v = convert(Array{String, 1}, v)
148. return el_2_graph(v, el, directed = directed, label = label, vtype = vtype, etype = etype)
149. end
150.
151.
152. ### graph_2_el takes a GenericGraph and returns a two-column edgelist.
153.
154. function graph_2_el(g::GenericGraph, label::Bool = true)
155. if in(:key, names(g.vertices[1]))
156. vtype = KeyVertex
157. elseif in(:label, names(g.vertices[1]))
158. vtype = ExVertex
159. else
160. vtype = Int
161. label = false
162. end
163. ne = num_edges(g)
164. nv = num_vertices(g)
165. alledges = edges(g)
166. allsamekeytype = true
167. if vtype == KeyVertex
168. if nv > 1
169. firstkey = typeof(g.vertices[1].key)
170. vcounter = 2
171. while (vcounter <= nv) & allsamekeytype
172. if typeof(g.vertices[vcounter].key) != firstkey
173. allsamekeytype = false
174. end
175. vcounter += 1
176. end
177. end
178. end
179. if label & (vtype == KeyVertex) & allsamekeytype
180. el = Array(typeof(g.vertices[1].key), ne, 2)
181. for i = 1:num_edges(g)
182. el[i, 1] = source(alledges[i], g).key
183. el[i, 2] = target(alledges[i], g).key
184. end
185. elseif label & (vtype == ExVertex)
186. el = Array(typeof(g.vertices[1].label), ne, 2)
187. for i = 1:num_edges(g)
188. el[i, 1] = source(alledges[i], g).label
189. el[i, 2] = target(alledges[i], g).label
190. end
191. else
192. el = Array(Int, ne, 2)
193. for i = 1:num_edges(g)
194. el[i, 1] = source(alledges[i], g).index
195. el[i, 2] = target(alledges[i], g).index
196. end
197. end
198. return el
199. end
200.
201. ### These next four functions convert the vertex and edge types.
202.
203. function keyvertex_2_exvertex(g::GenericGraph)
204. if in(:key, names(g.vertices[1])) == false
205. error("GenericGraph 'g' must have vertices of type KeyVertex.")
206. end
207. nv, ne = num_vertices(g), num_edges(g)
208. vlist = Array(ExVertex, nv)
209. for i = 1:nv
210. vlist[i] = ExVertex(g.vertices[i].index, string(g.vertices[i].key))
211. end
212. etype = ifelse(in(:attributes, names(g.edges[1])), ExEdge, Edge)
213. elist = Array(etype{typeof(vlist[1])}, ne)
214. for i = 1:ne
215. elist[i] = etype(i, vlist[g.edges[i].source.index], vlist[g.edges[i].target.index])
216. end
217. return graph(vlist, elist, is_directed = g.is_directed)
218. end
219.
220. function exvertex_2_keyvertex(g::GenericGraph)
221. if in(:label, names(g.vertices[1])) == false
222. error("GenericGraph 'g' must have vertices of type ExVertex.")
223. end
224. nv, ne = num_vertices(g), num_edges(g)
225. vlist = Array(KeyVertex, nv)
226. for i = 1:nv
227. vlist[i] = KeyVertex(g.vertices[i].index, g.vertices[i].label)
228. end
229. etype = ifelse(in(:attributes, names(g.edges[1])), ExEdge, Edge)
230. elist = Array(etype{typeof(vlist[1])}, ne)
231. for i = 1:ne
232. elist[i] = etype(i, vlist[g.edges[i].source.index], vlist[g.edges[i].target.index])
233. end
234. return graph(vlist, elist, is_directed = g.is_directed)
235. end
236.
237. function edge_2_exedge(g::GenericGraph)
238. vlist = g.vertices
239. ne = num_edges(g)
240. elist = Array(ExEdge{typeof(vlist[1])}, ne)
241. for i = 1:ne
242. elist[i] = ExEdge(i, vlist[g.edges[i].source.index], vlist[g.edges[i].target.index])
243. end
244. return graph(vlist, elist, is_directed = g.is_directed)
245. end
246.
247. function exedge_2_edge(g::GenericGraph)
248. vlist = g.vertices
249. ne = num_edges(g)
250. elist = Array(Edge{typeof(vlist[1])}, ne)
251. for i = 1:ne
252. elist[i] = Edge(i, vlist[g.edges[i].source.index], vlist[g.edges[i].target.index])
253. end
254. return graph(vlist, elist, is_directed = g.is_directed)
255. end
256.
257. #####
258. ### These following two functions create subgraphs.
259. ### The first creates subgraphs by vertex index.
260. ### The second creates subgraphs by edge index.
261. #####
262.
263. function subgraph_vertices(g::GenericGraph, vind::Array{Int, 1})
264. if num_vertices(g) == 0
265. error("The number of vertices in 'g' equals zero. Cannot base new graph off of it.")
266. end
267. newg = deepcopy(g)
268. vlist = deepcopy(vertices(newg)[vind])
269. for i = 1:length(vlist)
270. newvert = vlist[i]
271. setfield!(newvert, :index, i)
272. vlist[i] = newvert
273. end
274. oldedges = deepcopy(edges(newg))
275. elist = typeof(oldedges[1])[]
276. nedges = num_edges(newg)
277. ecount = 1
278. if nedges > 0
279. for i = 1:nedges
280. sourceinsubgraph = in(vertex_index(source(oldedges[i])), vind)
281. targetinsubgraph = in(vertex_index(target(oldedges[i])), vind)
282. if sourceinsubgraph & targetinsubgraph
283. sv = vlist[find(vertex_index(source(oldedges[i])) .== vind)[1]]
284. tv = vlist[find(vertex_index(target(oldedges[i])) .== vind)[1]]
285. newedge = typeof(oldedges[i])(ecount, sv, tv)
286. push!(elist, newedge)
287. ecount += 1
288. end
289. end
290. end
291. newg = graph(vlist, elist, is_directed = is_directed(g))
292. return newg
293. end
294.
295. function subgraph_edges(g::GenericGraph, eind::Array{Int, 1})
296. ne = num_edges(g)
297. if ne == 0
298. error("The number of edges in 'g' equals zero. Cannot base new graph off of it.")
299. end
300. newg = deepcopy(g)
301. elist = deepcopy(edges(newg)[eind])
302. ne = length(elist)
303.
304. sources = Array(typeof(vertex_index(source(elist[1]))), ne)
305. targets = Array(typeof(vertex_index(target(elist[1]))), ne)
306. for i = 1:ne
307. sources[i] = vertex_index(source(elist[i]))
308. targets[i] = vertex_index(target(elist[i]))
309. end
310. vind = unique([sources, targets])
311. vlist = deepcopy(vertices(newg)[vind])
312. for i = 1:length(vlist)
313. newvert = vlist[i]
314. setfield!(newvert, :index, i)
315. vlist[i] = newvert
316. end
317. for i = 1:ne
318. sv = vlist[find(vertex_index(source(elist[i])) .== vind)[1]]
319. tv = vlist[find(vertex_index(target(elist[i])) .== vind)[1]]
320. newedge = typeof(elist[i])(i, sv, tv)
321. elist[i] = newedge
322. end
323. newg = graph(vlist, elist, is_directed = is_directed(g))
324. return newg
325. end
326.
327. #####
328. ### Attribute methods
329. ### Vertex and edge attributes
330. ### Both sets of attributes have set, get, list, and remove functions
331. ### The indexes can be specified, though if left empty they default to all vertices or edges
332. ### Problems
333. ### Setting attvalue as type Array{Any, 1} in the functions produce methods errors; I've left it out
334. ### The set and remove functions could/should be made mutable.
335. #####
336.
337. ### Vertex attribute functions
338.
339. function set_vertex_attribute(g::GenericGraph, attname::String, attvalue, vertexind::Array{Int, 1})
340. if in(:label, names(g.vertices[vertexind[1]])) == false
341. warn("GenericGraph 'g' has vertices of type ExVertex. Converting them to ExVertex now.")
342. g = keyvertex_2_exvertex(g)
343. end
344. if length(attvalue) != length(vertexind)
345. error("Length of 'attvalue' does not equal the length of 'vertexind'.")
346. end
347. for i = 1:length(vertexind)
348. g.vertices[vertexind[i]].attributes[attname] = attvalue[i]
349. end
350. return g
351. end
352.
353. function set_vertex_attribute(g::GenericGraph, attname::String, attvalue)
354. vertexind = [1:num_vertices(g)]
355. return set_vertex_attribute(g, attname, attvalue, vertexind)
356. end
357.
358. function set_vertex_attribute(g::GenericGraph, attname::String, attvalue, vertexind::Int)
359. vertexind = [vertexind]
360. attvalue = [attvalue]
361. return set_vertex_attribute(g, attname, attvalue, vertexind)
362. end
363.
364. function set_vertex_attribute(g::GenericGraph, attname::String, attvalue, vertexind::UnitRange{Int})
365. vertexind = [vertexind]
366. return set_vertex_attribute(g, attname, attvalue, vertexind)
367. end
368.
369. function get_vertex_attribute(g::GenericGraph, attname::String, vertexind::Array{Int, 1})
370. if in(:label, names(g.vertices[vertexind[1]])) == false
371. error("Vertices in GenericGraph 'g' are not of type ExVertex.")
372. end
373. if in(attname, collect(keys(g.vertices[vertexind[1]].attributes))) == false
375. end
376. nind = length(vertexind)
377. retvec = Array(typeof(g.vertices[vertexind[1]].attributes[attname]), nind)
378. for i = 1:nind
379. retvec[i] = g.vertices[vertexind[i]].attributes[attname]
380. end
381. return retvec
382. end
383.
384. function get_vertex_attribute(g::GenericGraph, attname::String)
385. vertexind = [1:num_vertices(g)]
386. return get_vertex_attribute(g, attname, vertexind)
387. end
388.
389. function get_vertex_attribute(g::GenericGraph, attname::String, vertexind::UnitRange{Int})
390. vertexind = [vertexind]
391. return get_vertex_attribute(g, attname, vertexind)
392. end
393.
394. function get_vertex_attribute(g::GenericGraph, attname::String, vertexind::Int)
395. vertexind = [vertexind]
396. return get_vertex_attribute(g, attname, vertexind)[1]
397. end
398.
399. function list_vertex_attributes(g::GenericGraph)
400. if in(:label, names(g.vertices[1])) == false
401. error("Vertices in GenericGraph 'g' are not of type ExVertex.")
402. end
403. retvec = UTF8String[]
404. for i = 1:length(g.vertices)
405. attkeys = collect(keys(g.vertices[i].attributes))
406. nattkeys = length(attkeys)
407. if nattkeys > 0
408. for j = 1:nattkeys
409. push!(retvec, attkeys[j])
410. end
411. end
412. end
413. retvec = sort(unique(retvec))
414. return retvec
415. end
416.
417. function remove_vertex_attributes(g::GenericGraph, attname::String, vertexind::Array{Int, 1})
418. if in(:label, names(g.vertices[vertexind[1]])) == false
419. error("Vertices in GenericGraph 'g' are not of type ExVertex.")
420. end
421. for i = vertexind
422. attkeys = collect(keys(g.vertices[i].attributes))
423. if in(attname, attkeys)
424. tempvertex = ExVertex(g.vertices[i].index, g.vertices[i].label)
425. for j = 1:length(attkeys)
426. if attkeys[j] != attname
427. tempvertex.attributes[attkeys[j]] = g.vertices[i].attributes[attkeys[j]]
428. end
429. end
430. g.vertices[i] = tempvertex
431. else
432. warn("Attribute '\$attname' is not an attribute at vertex index \$i of graph 'g'.")
433. end
434. end
435. return g
436. end
437.
438. function remove_vertex_attributes(g::GenericGraph, attname::String)
439. vertexind = [1:num_vertices(g)]
440. return remove_vertex_attributes(g, attname, vertexind)
441. end
442.
443. function remove_vertex_attributes(g::GenericGraph, attname::String, vertexind::Int)
444. vertexind = [vertexind]
445. return remove_vertex_attributes(g, attname, vertexind)
446. end
447.
448. function remove_vertex_attributes(g::GenericGraph, attname::String, vertexind::UnitRange{Int})
449. vertexind = [vertexind]
450. return remove_vertex_attributes(g, attname, vertexind)
451. end
452.
453. ### Edge attribute functions
454.
455. function set_edge_attribute(g::GenericGraph, attname::String, attvalue, edgeind::Array{Int, 1})
456. if in(:attributes, names(g.edges[edgeind[1]])) == false
457. warn("Edges in GenericGraph 'g' are not of type ExEdge. Converting them to ExEdge now.")
458. g = edge_2_exedge(g)
459. end
460. if length(attvalue) != length(edgeind)
461. error("Length of 'attvalue' does not equal the length of 'edgeind'.")
462. end
463. for i = 1:length(edgeind)
464. g.edges[edgeind[i]].attributes[attname] = attvalue[i]
465. end
466. return g
467. end
468.
469. function set_edge_attribute(g::GenericGraph, attname::String, attvalue)
470. edgeind = [1:num_edges(g)]
471. return set_edge_attribute(g, attname, attvalue, edgeind)
472. end
473.
474. function set_edge_attribute(g::GenericGraph, attname::String, attvalue, edgeind::Int)
475. attvalue = [attvalue]
476. edgeind = [edgeind]
477. return set_edge_attribute(g, attname, attvalue, edgeind)
478. end
479.
480. function set_edge_attribute(g::GenericGraph, attname::String, attvalue, edgeind::UnitRange{Int})
481. edgeind = [edgeind]
482. return set_edge_attribute(g, attname, attvalue, edgeind)
483. end
484.
485. function get_edge_attribute(g::GenericGraph, attname::String, edgeind::Array{Int, 1})
486. if in(:attributes, names(g.edges[edgeind[1]])) == false
487. error("Edges in GenericGraph 'g' are not of type ExEdge.")
488. end
489. if in(attname, collect(keys(g.edges[edgeind[1]].attributes))) == false
491. end
492. ninds = length(edgeind)
493. retvec = Array(typeof(g.edges[edgeind[1]].attributes[attname]), ninds)
494. for i = 1:ninds
495. retvec[i] = g.edges[edgeind[i]].attributes[attname]
496. end
497. return retvec
498. end
499.
500. function get_edge_attribute(g::GenericGraph, attname::String)
501. edgeind = [1:num_edges(g)]
502. return get_edge_attribute(g, attname, edgeind)
503. end
504.
505. function get_edge_attribute(g::GenericGraph, attname::String, edgeind::UnitRange{Int})
506. edgeind = [edgeind]
507. return get_edge_attribute(g, attname, edgeind)
508. end
509.
510. function get_edge_attribute(g::GenericGraph, attname::String, edgeind::Int)
511. edgeind = [edgeind]
512. return get_edge_attribute(g, attname, edgeind)[1]
513. end
514.
515. function list_edge_attributes(g::GenericGraph)
516. if in(:attributes, names(g.edges[1])) == false
517. error("Edges in GenericGraph 'g' are not of type ExEdge.")
518. end
519. retvec = UTF8String[]
520. for i = 1:length(g.edges)
521. attkeys = collect(keys(g.edges[i].attributes))
522. nattkeys = length(attkeys)
523. if nattkeys > 0
524. for j = 1:nattkeys
525. push!(retvec, attkeys[j])
526. end
527. end
528. end
529. retvec = sort(unique(retvec))
530. return retvec
531. end
532.
533. function remove_edge_attributes(g::GenericGraph, attname::String, edgeind::Array{Int, 1})
534. if in(:attributes, names(g.edges[edgeind[1]])) == false
535. error("Edges in GenericGraph 'g' are not of type ExEdge.")
536. end
537. for i = edgeind
538. attkeys = collect(keys(g.edges[i].attributes))
539. if in(attname, attkeys)
540. tempedge = ExEdge(g.edges[i].index, g.vertices[g.edges[i].source.index], g.vertices[g.edges[i].target.index])
541. for j = 1:length(attkeys)
542. if attkeys[j] != attname
543. tempedge.attributes[attkeys[j]] = g.edges[i].attributes[attkeys[j]]
544. end
545. end
546. g.edges[i] = tempedge
547. else
548. warn("Attribute '\$attname' is not an attribute at edge index \$i of graph 'g'.")
549. end
550. end
551. return g
552. end
553.
554. function remove_edge_attributes(g::GenericGraph, attname::String)
555. edgeind = [1:num_edges(g)]
556. return remove_edge_attributes(g, attname, edgeind)
557. end
558.
559. function remove_edge_attributes(g::GenericGraph, attname::String, edgeind::Int)
560. edgeind = [edgeind]
561. return remove_edge_attributes(g, attname, edgeind)
562. end
563.
564. function remove_edge_attributes(g::GenericGraph, attname::String, edgeind::UnitRange{Int})
565. edgeind = [edgeind]
566. return remove_edge_attributes(g, attname, edgeind)
567. end
568.
569. #####
570. ### Loop identification functions
571. #####
572.
573. function is_loop(g::GenericGraph)
574. ne = num_edges(g)
575. loopbool = Array(Bool, ne)
576. for i = 1:ne
577. loopbool[i] = g.edges[i].source.index == g.edges[i].target.index
578. end
579. return loopbool
580. end
581.
582. function is_loop(g::GenericGraph, eind::Int)
583. loopbool = g.edges[eind].source.index == g.edges[eind].target.index
584. return loopbool
585. end
586.
587. function is_loop(g::GenericGraph, eind::Array{Int, 1})
588. nindlen = length(eind)
589. loopbool = Array(Bool, nindlen)
590. for i = 1:nindlen
591. loopbool[i] = g.edges[eind[i]].source.index == g.edges[eind[i]].target.index
592. end
593. return loopbool
594. end
595.
596. function has_loop(g::GenericGraph)
597. return any(is_loop(g))
598. end
599.
600. #####
601. ### Multiple edge identification function
602. #####
603.
604. function has_multiple(g::GenericGraph)
605. ne = num_edges(g)
606. el = Array((Int, Int), ne)
607. if is_directed(g)
608. for i = 1:ne
609. testedge = edges(g)[i]
610. sv = vertex_index(source(testedge))
611. tv = vertex_index(target(testedge))
612. el[i] = (sv, tv)
613. end
614. else
615. for i = 1:ne
616. testedge = edges(g)[i]
617. sv = vertex_index(source(testedge))
618. tv = vertex_index(target(testedge))
619. if sv < tv # Ensures consistent ordering
620. el[i] = (sv, tv)
621. else
622. el[i] = (tv, sv)
623. end
624. end
625. end
626. return length(el) > length(unique(el))
627. end
628.
629. #####
631. #####
632.
633. function dyad_census(g::GenericGraph) # About 10x slower than the version imported from igraph on the Coleman data.
634. nv = num_vertices(g)
635. ne = num_edges(g)
636. if g.is_directed == false
637. npossible = nv * (nv - 1) / 2
638. npossible = convert(Int, npossible)
639. warn("You are conducting a dyad census on a directed graph. No asymmetric dyads are possible.")
640. return (nv, 0, npossible - nobs)
641.
642. else
643. el1 = Array((Int, Int), ne)
644. el2 = Array((Int, Int), ne)
645. for i = 1:ne
646. el1[i] = (g.edges[i].source.index, g.edges[i].target.index)
647. el2[i] = (g.edges[i].target.index, g.edges[i].source.index)
648. end
649. dc = ["Mut" => 0, "Asym" => 0, "Null" => 0]
650. isrecip = Array(Bool, ne)
651. for i = 1:ne
652. if in(el1[i], el2)
653. dc["Mut"] +=1
654. end
655. end
656. dc["Asym"] = ne - dc["Mut"]
657. dc["Mut"] = int(dc["Mut"] / 2)
658. dc["Null"] = int((nv * (nv - 1) / 2) - (dc["Mut"] + dc["Asym"]))
659. return dc
660. end
661. end
662.
663. function reciprocity(g::GenericGraph; ignoreloops::Bool = true, mode::String = "default")
664. if g.is_directed == false
665. warn("You know that g is undirected, right? Of course its reciprocity will equal 1.0.")
666. return(1.0)
667. else
669. if !in(mode, acceptablemodes)
670. error("mode must be in \$acceptablemodes")
671. end
673. nv = num_vertices(g)
674. ne = num_edges(g)
675. if (ignoreloops == false) & (mode != "dyadic")
676. warn("Sorry, but loop handling is implemented only in the 'dyadic' mode. Ignoring loops...")
677. end
678. if in(mode, ["default", "edgewise"]) # 2 * Mut / (Asym + 2 * Mut)
679. grecip = 2 * dc["Mut"] / (dc["Asym"] + (2 * dc["Mut"])) # I don't know how to measure it with loops
681. grecip = dc["Mut"] / (dc["Mut"] + dc["Asym"])
682. elseif in(mode, ["edgewise.lrr", "edgewise log ratio reciprocity", "edgewiselrr"])
683. ewr = 2 * dc["Mut"] / (dc["Asym"] + (2 * dc["Mut"]))
684. den = ne / (nv * (nv -1))
685. grecip = log(ewr / den)
687. if ignoreloops
688. grecip = (dc["Mutual"] + dc["Null"]) / (dc["Mutual"] + dc["Asym"] + dc["Null"])
689. else #I think I'm doing the loops right here, but not 100%.
690. nloops = sum(is_loop(g))
691. grecip = (dc["Mutual"] + dc["Null"] + nloops) / (dc["Mutual"] + dc["Asym"] + dc["Null"] + nv)
692. end
693. end
694. return grecip
695. end
696. end