Calculating the sum of weights of edges(libgraph)

Hi,
So I’m using libgraph to make a directed graph with specified edges, and what I want to do is to calculate the sum of the edges between two vertices. So for example if I have three vertices a, b, and c, where the weight of a–>b is 5 and b–> c is 3, I want to find the sum of weights of edges between a to c (which will be 8 in this case). How do I do that?

Something like this should do the trick (not tested):

graph
|> Graph.get_paths(:from, :to)
|> Enum.map(&sum_path/1)
|> Enum.sum()

Where sum_path/1 takes a list of vertices you can then pass pair-wise to Graph.get_edge/2 to get the weights and then sum them (I’ll put an example together soon)

Hi, thank you so much for your answer! While I do understand sum_path/1, I’m not really sure how to implement it. Could you please help me with that too?

Here’s what I believe is a working example:

Code

defmodule PathWeight do
  @graph Graph.new |> Graph.add_edges([
    {:a, :b, weight: 1}, {:b, :c, weight: 1}, {:c, :d, weight: 1}, {:b, :d, weight: 1}, {:c, :a, weight: 1}
  ])

  def calc(graph \\ @graph, from \\ :a, to \\ :d) do
    graph
    |> Graph.get_paths(from, to)
    |> IO.inspect(label: "Paths from #{inspect from} to #{inspect to}")
    |> Enum.map(&sum_path(graph, &1, 0))
    |> IO.inspect(label: "Weight of each path")
    |> Enum.sum()
    |> IO.inspect(label: "Sum of paths")
  end

  def sum_path(_graph, [_vertex], sum) do
    sum
  end

  def sum_path(graph, [a, b | rest], sum) do
    weight =
      graph
      |> Graph.edge(a, b)
      |> Map.get(:weight, 0)

    sum_path(graph, [b | rest], sum + weight)
  end
end

Example

iex> PathWeight.calc
Paths from :a to :d: [[:a, :b, :c, :d], [:a, :b, :d]]
Weight of each path: [3, 2]
Sum of paths: 5
5
5 Likes

thank you for the example! but I think sum_path wouldn’t work because the first one would catch all of the examples

The first function clause is only applied if the list has only one element. It has only one element when we have calculated all of the edge weights. And therefore it returns the sum of weights for the given path. The example I showed illustrates this (run it and you will see).

Your example seems to work, the problem is probably from something else in my code. Thank you so much for your help, it is very much appreciated!

Hi sorry to bother you again, I think my problem is that I am using an undirected graph and so get_paths does not return anything. Is there any alternatives for it for undirected graphs?

get_paths/3 doesn’t note any limitation on graph type but then I’ve not used the library in anger. Are you able to post an example graph or code I can experiment with?

sorry, I cannot post the code because of academic integrity. But I was able to solve the problem by using it on a directed graph and reversing :from and :to whenever the list was returned empty. But still thank you very much!

1 Like