-
Notifications
You must be signed in to change notification settings - Fork 1
/
graph.cljc
91 lines (74 loc) · 2.29 KB
/
graph.cljc
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
(ns blossom.graph
(:require [loom.graph :as lg]
[blossom.constants :as c]
[blossom.context]
[clojure.spec.alpha :as s]))
(def no-node? #(= c/NO-NODE %))
(def some-node? #(not= c/NO-NODE %))
(def no-edge? #(= c/NO-EDGE %))
(def some-edge? #(not= c/NO-EDGE %))
(defprotocol PGraph
(edge [g k]))
(defprotocol PWeightedEdge
(src [edge] "Returns the source node of the edge")
(dest [edge] "Returns the dest node of the edge")
(weight [edge] "Returns the weight of the edge"))
(extend-type #?(:clj clojure.lang.IPersistentVector
:cljs cljs.core.PersistentVector)
PWeightedEdge
(src [edge] (get edge 0))
(dest [edge] (get edge 1))
(weight [edge] (get edge 2)))
(extend-type blossom.context.Context
PGraph
(edge [g k]
(nth (:edges g) k)))
(defn edges-with-weights
([g]
(map #(conj % (lg/weight g %)) (lg/edges g))))
(defn star-graph
"Return the star graph
The star graph consists of one center node connected to n outer nodes.
Parameters
----------
n : int
node labels are 0 to n with center 0.
Notes
-----
The graph has n+1 nodes for integer n."
[n]
(lg/add-edges* (lg/weighted-graph)
(for [i (range n)]
[0 (inc i)])))
(defn max-vertex-id [edges]
(->> edges
(mapcat (fn [[i j _]] [i j]))
(reduce max)))
(defn max-weight [edges]
(->> edges
(map last)
(reduce max)))
(defn integer-weights? [edges]
(s/valid? (s/coll-of int?) (map last edges)))
(defn compute-endpoint [edges]
(vec (mapcat (fn [[i j _]]
[i j])
edges)))
(defn compute-neighbend [edges]
(reduce (fn [neighbend [idx [i j _]]]
(-> neighbend
(update i conj (inc (* 2 idx)))
(update j conj (* 2 idx))))
(vec (repeat (inc (max-vertex-id edges)) []))
(map-indexed vector edges)))
(defn initialize [edges]
(let [[nedge max-vertex-id endpoint neighbend max-weight integer-weights?]
((juxt count max-vertex-id compute-endpoint compute-neighbend max-weight integer-weights?) edges)
nvertex (inc max-vertex-id)]
{:edges edges
:nedge nedge
:nvertex nvertex
:endpoint endpoint
:neighbend neighbend
:max-weight max-weight
:integer-weights? integer-weights?}))