Class: SubSpawn::Internal::Bigraph

Inherits:
Object
  • Object
show all
Defined in:
lib/subspawn/graph_helper.rb

Instance Method Summary collapse

Constructor Details

#initialize ⇒ Bigraph

Returns a new instance of Bigraph.



5
6
7
8
 
# File 'lib/subspawn/graph_helper.rb', line 5

def initialize
	@fwd = {}
	@rev = {}
end

Instance Method Details

#delete(head, tail) ⇒ Object 



82
83
84
85
 
# File 'lib/subspawn/graph_helper.rb', line 82

def delete(head, tail)
	@fwd[head].delete(tail)
	@rev[tail].delete(head).map(&:data)
end

#delete_outgoing(head) ⇒ Object 



79
80
81
 
# File 'lib/subspawn/graph_helper.rb', line 79

def delete_outgoing(head)
	@fwd[head].flat_map{|t, k|delete(head, t)}
end

#find_cycle ⇒ Object 



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
# File 'lib/subspawn/graph_helper.rb', line 51

def find_cycle
	unmark!
	# we have a forest, do for each forestry
	rts = roots_h
	if rts.empty? # probably have a loop
		#puts "empt"
		rts = [@fwd.keys.first]
	end
	at, rts = *rts
	while at
		#puts "searching at #{at} with #{rts}"
		tmp = find_cycle_next(at)
		return tmp unless tmp.nil?
		at, rts = *rts
	end
end

#find_cycle_next(start) ⇒ Object 



67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/subspawn/graph_helper.rb', line 67

def find_cycle_next(start)
	@fwd[start]&.each do |t, list|
		#puts "cc = [#{start} -> #{t}]"
		if list.any?(&:marker)
			return t 
		end
		list.each(&:mark)
		tmp = find_cycle_next(t)
		return tmp unless tmp.nil?
	end
	return nil
end

#find_unmarked ⇒ Object 



86
87
88
89
90
91
92
93
 
# File 'lib/subspawn/graph_helper.rb', line 86

def find_unmarked
	@fwd.each do |h, ts|
		ts.each do |t, lst|
			return [h, t] unless lst.first.marker
		end
	end
	return nil
end

#insert(head, tail, data) ⇒ Object 



9
10
11
12
13
 
# File 'lib/subspawn/graph_helper.rb', line 9

def insert(head, tail, data)
	node = BiNode.new(head, tail, data)
	((@fwd[head] ||= {})[tail] ||= []) << node
	((@rev[tail] ||= {})[head] ||= []) << node
end

#leaves ⇒ Object 



41
42
43
44
45
46
47
48
49
50
 
# File 'lib/subspawn/graph_helper.rb', line 41

def leaves
	unmark!
	leaves = []
	@fwd.each do |h, ts|
		ts.each do |t, lst|
			leaves += lst unless @fwd.key? t
		end
	end
	leaves
end

#ordered_kahn ⇒ Object 



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
131
 
# File 'lib/subspawn/graph_helper.rb', line 94

def ordered_kahn
	unmark!
	# now traverse the tree until we hit a junction, ensuring
	# dependencies are met
	# Note this assumes you removed all the cycles from your code
	# returns each graph seperately as a sort of forest
	l = []
	s = Set.new(roots_h)

	until s.empty?
		n = s.first
		#puts "checking #{n} in #{s}"
		s.delete(n)
		@fwd[n]&.each do |e, ms|
			next if ms.any?(&:marker) # already visited
			ms.each(&:mark)
			# no incoming edges
			unless @rev[e]&.any?{|nh, lst| !lst.first.marker}
				# nil -> add
				# any(unmarked) true -> none
				# all(marked) -> add
				s << e
				l += ms
				#puts "blank incoming #{e}"
			else
				#puts "had incoming #{e}: #{@rev[e]}"
			end
		end
	end

	if find_unmarked#.tap{|x| p x, "um"}
		puts to_dot
		#raise "Unmarked graph edges, an unresolved cycle probably exists. This is a bug in SubSpawn"
		nil
	else
		return l.map(&:data)
	end
end

#roots ⇒ Object 



21
22
23
24
25
26
27
28
29
30
 
# File 'lib/subspawn/graph_helper.rb', line 21

def roots
	unmark!
	roots = []
	@rev.each do |t, hs|
		hs.each do |h, lst|
			roots += lst unless @rev.key? h
		end
	end
	roots
end

#roots_h ⇒ Object 



31
32
33
34
35
36
37
38
39
40
 
# File 'lib/subspawn/graph_helper.rb', line 31

def roots_h
	unmark!
	roots = []
	@rev.each do |t, hs|
		hs.each do |h, lst|
			roots << h unless @rev.key? h
		end
	end
	roots.uniq
end

#to_dot ⇒ Object

for debugging



134
135
136
137
138
139
140
141
 
# File 'lib/subspawn/graph_helper.rb', line 134

def to_dot
	body = @fwd.map do |h, ts|
		ts.map do |t, lst|
			"\"#{h}\" -> \"#{t}\" ;" #{lst.first&.marker};"
		end
	end.join("\n")
	return "digraph G {\n#{body}\n}"
end

#unmark! ⇒ Object 



14
15
16
17
18
19
20
 
# File 'lib/subspawn/graph_helper.rb', line 14

def unmark!
	@fwd.each do |h, ts|
		ts.each do |t, lst|
			lst.each {|n| n.marker = nil}
		end
	end
end