Copy of digraph gives badrecord error

Questions / Help
,
1

After more than a year of not really coding anything for a variety of reasons, I tried to get back in the swing a little bit this weekend. I have a digraph that is created in one function and passed to various helper functions in a series of processing steps. The initialization of the digraph starts with edges connecting every node to every other node. Each processing step goes through and prunes these edges according to a series of constraints. Some of the constraints are straight forward: from group A only X is connected to Y from group B. Other constraints are more complex as 3 groups are involved. So if there’s a group of number 1..5, a group of letters a..e, and a group of capital letters Z..V, then you could have a constraint that says letter b is connected to a number one more than the number capital letter Y is connected to. I can easily write the constraint rule that prunes the edge from b to 1, because Y cannot be connected to one less than 1. Similarly I can write the constraint that prunes the edge from Y to 5 because b cannot be connected to one more than 5. I’m left with combinations of [{{b,2},{Y,1}}, {{b,3},{Y,2}}, {{b,4},{Y,3}}, {{b,5},{Y,4}}]. These combinations can only be further pruned by applying other constraints. What I’ve tried to do is branch the logic for each remaining combination and seeing if it is possible to satisfy the other constraints with that path. I thought I could do this by copying the digraph as a maximal subgraph for each branch. This leads to a step where I should have a list of graphs that applied all constraints, but when I try to check the graphs for correctness I’m getting a badrecord error. Hopefully this code is enough to show what I’m trying to accomplish.

def init() do 
  g = :digraph.new()
  categories = [@letters, @capital_letters, @numbers, @colors]
  categories
  |> Enum.each(fn items -> 
        items
        |> Enum.each(fn item -> 
             categories -- [items]
             |> Enum.each(fn items2 ->
                  items2
                  |> Enum.each(fn item2 ->
                       :digraph.add_vertex(g, item)
                       :digraph.add_vertex(g, item2)
                       :digraph.add_edge(g, {item, item2}, item, item2, [])
                     end)
                 end)
            end)
       end)
  g
end

def solve() do
  g = init()
  
  soln = apply_rules(g)

  Enum.find(soln, fn s -> check(s) end) # badrecord
end

def apply_rules(g) do 
  g
  |> apply_straight_forward_rule() # returns g
  |> apply_complex_rule() # returns [g, g2, g3, ...]
end

def apply_complex_rule(g) do 
  g2 = :digraph_utils.subgraph(g, :digraph.vertices(g))
  [left_branch(g), right_branch(g2)] # each branch returns the digraph reference
end
2

I’d start by checking the return type of the init function - I don’t think it’s what you think it is.

Remember that Elixir is a functional programming language, as well - if you don’t store the return values from function calls, such as when you add vertices or edges to your graph, it will get thrown away.

Either this code has been heavily simplified from the real code, or it would error long before you say it does…

1 Like
3

:digraph is ETS based, so this doesn’t apply. g is just an opaque reference, not a datastructure to build upon.

2 Likes
4

Huh, really? I could have sworn I ran into multiple issues with this in the past - I remember it being one of the reasons I switched to the Digraph library. TIL!

5

All true but @sevenseacat 's first paragraph is still the root cause since init is returning :ok from the Enum.each. it should return g instead.

def init() do
  g = ...
  Enum.each(...)

  g
end
6

The init function does return g. Transcription error on my part.

Updated OP to reflect that.