Hello, I am getting some behavior that makes me suspect there is a memory leak happening when removing and adding labels to a graph.

I have some code similar to the following:

[id] = MyApp.Server.get_by_label(label_val) # genserver callback w/ graph reducer
[label] = MyApp.Server.get_label(id) # wraps vertex_labels
new_label = Map.put(label,"foo",true) # update label
MyApp.Server.rm_label(id) # wraps remove_vertex_labels
MyApp.Server.add_label(id,new_label) # wraps label_vertex

This causes BEAM to run out of memory after a few hundred calls to this function.
Let me know if you'd like a self-running example or if theres any tracing/debugging I can do to get more info.

Does it make sense to allow pathfinding in a lazy way? Where the nodes and the edges can be added whilst traversing.

Or is this a silly idea?

Machine: Intel Core i5-8250U (1.60GHz), 16gb RAM
OS: Ubuntu 22.04
Elixir version: Elixir 1.15.0-rc.0
OTP version: 25.0
libgraph version: 0.16.0

I use graph to accumulate pages while I crawl. The crawler is a stream of pages: above page (previous) and sub page (current). Such relationship I have to record to find paths between pages later.

I noticed that from nth node it becomes impossible to compute paths. Literally, when my crawler reached a goal and needed to collect paths from A to B pages, it took all night and there was no calculation result (the calculation was definitely still going on, judging by the load).

I decided to log every thousandth relationship recorded and try to find all paths from the starting page to the current page (I record page to subpage relationship).

The results are as follows (relation a sub page to the above page -> time to find all paths from the first page to the sub page):

• 1000 -> 99µ
• 2000 -> 179µ
• 3000 -> 306µ
• 4000 -> 302µ
• 5000 -> 745µ
• 6000 -> 834µ
• 7000 -> 3018µ
• 8000 -> 3059µ
• 9000 -> 6092µ
• 10000 -> 66057µ
• 11000 -> infinity

I used this to record relationship:

graph
|> Graph.add_vertex(abv_ref, abv)
|> Graph.add_vertex(sub_ref, sub)
|> Graph.add_edge(abv_ref, sub_ref)

Where abv and sub are structs, abv_ref and sub_ref are strings.

Tested like this:

IO.puts("Task now: #{x}")
if rem(x, 1000) === 0 do
  IO.puts("Trying to get all paths from the start to current urls...")

  {d, result} = :timer.tc(fn ->
    Graph.get_paths(graph, start_ref, sub_ref)
  end)

  IO.puts("Got result in #{d}µ (#{div(d, 1_000_000)}s): #{inspect(result)}")
end

Where result is a list of strings, start_ref is string as well.

I don't know if my problem is unique or if it's a general property of the library graph. Is there a benchmark that tests such a large amount of relations? Send links if available. If not, my suggestion is to make one.

Hello @bitwalker , thanks for this lib.

I have been using it and found that Graph.edges/2 does not return edges attached to vertices that don't have only inbound or outbound vertices (but not both).

Example

iex> g = Graph.new |> Graph.add_edges([{:a, :b}, {:b, :c}])
#Graph<type: directed, vertices: [:a, :b, :c], edges: [:a -> :b, :b -> :c]>

All edges are present, as expected.

iex> Graph.edges(g)
[%Graph.Edge{label: nil, v1: :a, v2: :b, weight: 1},
 %Graph.Edge{label: nil, v1: :b, v2: :c, weight: 1}]

I expected this to return [%Graph.Edge{label: nil, v1: :a, v2: :b, weight: 1}] but it returns an empty list

iex> Graph.edges(g, :a)
[ ]

Same thing here

iex> Graph.edges(g, :c)
[ ]

Is this expected behaviour? (Using version 0.11.1)

It might be neat to have a deserializer behavior for converting from edgelists or DOT files or JSON. Is this something you've considered?

I'm getting ~18 ms on vertex deletes in large graphs, is this expected? And if so, is it theoretically possible to do anything about it?

Hi,

I want to do path finding between multiple vertexes. I'm adding edges but my current weight values are decimal. The library returns the following message:

(ArgumentError) invalid value for :weight, must be an integer

I understand that integers are faster and don't have rounding errors. What is the reason that weights must be an integer?

ps: thanks for the lib :-)

Aside from pathfinding issues #37 and #11, several of the Graph functions delegate to Graph.Directed in a way that is inapproriate for undirected graphs:

• is_acyclic?
• components
• strong_components
• reachable
• reachable_neighbors
• reaching
• reaching_neighbors
• preorder
• postorder
• loop_vertices

Hi there, I am just getting started with libgraph but I have noticed that I seem to be getting wrong results for the a_star function.

What I am doing basically:

g = Graph.new(type: :undirected)
|> Graph.add_edges([{:dp1, :dp2, [weight: 3]}, {:dp2, :dp3, [weight: 6]}, {:dp3, :dp4, [weight: 5]}])
|> Graph.add_edges([{:dp4, :dp5, [weight: 4]}, {:dp4, :dp6, [weight: 5]}, {:dp5, :dp6, [weight: 6]}])
|> Graph.add_edges([{:dp6, :dp7, [weight: 5]}, {:dp7, :dp8, [weight: 4]}, {:dp8, :dp9, [weight: 2]}])
|> Graph.add_edges([{:dp9, :dp10, [weight: 6]}, {:dp3, :dp5, [weight: 3]}, {:dp5, :dp1, [weight: 7]}])
|> Graph.add_edges([{:dp6, :dp3, [weight: 7]}])

iex(1)> Graph.a_star(g, :dp1, :dp6, fn v -> 0 end)

The result I get is:

[:dp1, :dp2, :dp3, :dp4, :dp6]

However, the correct result would be:

[:dp1, :dp2, :dp3, :dp6]

Thanks in advance.

PS.: If you need a picture of the graph created above just ask.

Encountered this error (appears to be from ETS) when processing a smallish graph.

** (ArgumentError) argument error
      (stdlib) :ets.update_counter(#Reference<0.2437733789.3691642882.33749>, "heller.name", {2, -1})
    (libgraph) lib/graph.ex:1470: anonymous fn/4 in Graph.decompose_cores/4
      (elixir) lib/enum.ex:1755: Enum."-reduce/3-lists^foldl/2-0-"/3
    (libgraph) lib/graph.ex:1469: anonymous fn/6 in Graph.decompose_cores/4
      (elixir) lib/enum.ex:1755: Enum."-reduce/3-lists^foldl/2-0-"/3
    (libgraph) lib/graph.ex:1467: Graph.decompose_cores/4
    (libgraph) lib/graph.ex:1451: Graph.decompose_cores/1
    (libgraph) lib/graph.ex:1395: Graph.degeneracy/1
...snip...

Using Graph.info tells me that it looks like this: %{num_edges: 201, num_vertices: 101, size_in_bytes: 69504, type: :directed} while the printer representation gives me #Graph<type: directed, num_vertices: 101, num_edges: 201>. Neither of these enable me to send you the graph I'm working with. Any tips on how to serialize the graph for transmission to you?

Happy to provide more info since everything's bogus and simulated anyhow!

Thanks,
+Jonathan

I love this library and have used it for graph analysis and manipulation at work! I was hoping to request k-core detection for graphs. I'd love to be able to do something like Graph.k_cores(some_graph, 5) for finding 5-cores. I was considering a signature like the following:

@spec k_cores(Graph.t(), integer()) :: [Graph.t()]
def k_cores(g, k) do
  ...
end

Can I provide additional information or clarification? Thanks again for making such a wonderful library!

Hi and first of all, thanks for maintaining this library. It has turned out to be essential to me since I started using it.

I'm a big fan of pattern matching over edges in the graph and it's a very intuitive way to write complicated case handling. However I just discovered that I'm getting duplicated edges when I am matching on, eg.

case graph |> Graph.edges(metric_key) do
    %{v1: ^metric_key, v2: ^metric_key} -> ...
    ... other cases
end

From a glance at the code, a possible cause could be if a self-referencing edge could be described by both v_in and v_out:

But the description would have to differ, otherwise the MapSet would make it unique.. Do you think this is a correct cause and if so, is it an intended one?

I don't suppose there is any inherent disadvantage in just matching instead on all edges as such:

case graph |> Graph.edges() do
    %{v1: ^metric_key, v2: ^metric_key} -> ...
    ... other cases
    _ -> [] # not the stuff we're interested in
end |> List.flatten()

Looking at the code, it seems to be pretty much the same amount of work being done -- and in my situation, I always need to flat_map anyway in what I am doing.

However, someone else may be tripped up on it and have a situation where getting duplicates could cause confusion down the line.

Best regards,
Dennis

Graph.edges/2 only returns a single direction of edges from one vertex :a to another vertex :b instead of both directions from the vertex :a to the other vertex :b.

iex(1)> g = Graph.new() |> Graph.add_edges([{:a, :b, label: "label1"}, {:a, :b, label: "label2"}, {:b, :a, label: "label3"}]) |> Graph.edges(:a)
[
  %Graph.Edge{label: "label1", v1: :a, v2: :b, weight: 1},
  %Graph.Edge{label: "label2", v1: :a, v2: :b, weight: 1}
]

Expected:

[
  %Graph.Edge{label: "label1", v1: :a, v2: :b, weight: 1},
  %Graph.Edge{label: "label2", v1: :a, v2: :b, weight: 1},
  %Graph.Edge{label: "label3", v1: :b, v2: :a, weight: 1}
]

Hi bitwalker,
Thank you for this amazing hex package, am looking to create multigraph(multi edges between same ends with diff edges data) and as well label edge coloring.

is there any future plans to support it?

Graph.subgraph/2 is not keeping labels from the source graph around.

There does not seem to be a way to remove/reset/overwrite vertex labels. The only method that appears to be an option is Graph.label_vertex.

graph = Graph.new
graph = Graph.add_vertex(graph, :v1)
graph = Graph.label_vertex(graph, :v1, [:label1])
Graph.vertex_labels(graph, :v1) #=> [:label1]
graph = Graph.label_vertex(graph, :v1, [:label1, :label2])
Graph.vertex_labels(graph, :v1) #=> [:label1, :label1, :label2]

If label_vertex is the only method supplied, I would expect it to overwrite the labels, but it does not. It always adds a new label even if the label already exists. The most correct fix in my opinion is to update label_vertex to simply set the labels for a vertex to the ones passed in, but that may break existing code, so the next best solution may be to add a remove_vertex_labels that would remove all labels for a given vertex. Would you be willing to accept a pull request for either of these approaches and if so, do you have a preference for one over the other?

Update the behavior of Graph.label_vertex:

graph = Graph.new
graph = Graph.add_vertex(graph, :v1)

graph = Graph.label_vertex(graph, :v1, [:label1])
Graph.vertex_labels(graph, :v1) #=> [:label1]

graph = Graph.label_vertex(graph, :v1, [:label2, :label3])
Graph.vertex_labels(graph, :v1) #=> [:label2, :label3]

Add a new method (Graph.remove_vertex_labels):

graph = Graph.new
graph = Graph.add_vertex(graph, :v1)

graph = Graph.label_vertex(graph, :v1, [:label1])
Graph.vertex_labels(graph, :v1) #=> [:label1]

graph = Graph.remove_vertex_labels(graph, :v1)
Graph.vertex_labels(:v1) #=> []

When adding large number of vertices, some of my vertices weren't added to the graph.

For example

vertices = 0..250000 |> Enum.map(& &1)
Graph.add_vertices(Graph.new, vertices)
#Graph<type: directed, num_vertices: 249997, num_edges: 0>

I fixed it for myself by changing the function Graph.Utils.vertex_id(v) to
def vertex_id(v), do: v
instead of
def vertex_id(v), do: :erlang.phash2(v, @max_phash)

Apparently I had duplicate key in my graph otherwise.

The last release was almost three years ago. Is there any reason for not releasing all the latest additions?

Hello @bitwalker ,

I am working on exporting my libgraph graph to Neo4j. I see the way you do that for GraphViz is by using the in-built DOT serializer.

Where should new serializers live? Should they be contributed back to libgraph or should they simply implement the Graph.Serializer behaviour and live in their own libraries?

Thanks.

Good Morning Bitwalker,

First of all , a great job on the library.

One question: did you ever consider porting the libgraph-core to Erlang ??
I saw you are using some erlang-dependencies, but I do not have enough Elixir know-how to deduce how much effort would be needed or if it is possible at all.

Kind regards, and thanks for the library - which might well propel me into the direction of Elixir.

My graph theory's a little rusty, so it might be easy to do using the provided API, but is there an easy way to get a list of all the cycles (either as new Graphs, or as edgelists) in a directed graph?

is_cyclic/1 can tell me if there is a cycle, but I want to know what the actual cycles are (I realise this is computationally expensive, that's fine because I only care about small graphs).

For the following code:

Graph.new(type: :undirected)
|> Graph.add_vertices([:a, :b]) 
|> Graph.add_edge(:a, :b) 
|> Graph.edges(:a, :b)

works as expected [%Graph.Edge{label: nil, v1: :a, v2: :b, weight: 1}] but

Graph.new(type: :undirected) 
|> Graph.add_vertices([:a, :b]) 
|> Graph.add_edge(:a, :b) 
|> Graph.edges(:b, :a)

does return an empty list [].

The currently published version of this package on Hex is 0.13.3. There have been 2 releases since then (0.14.0 was released in 2019). Is there any reason these releases haven't been published?

My use case is to build a Graph from data coming from a DB. When there are changes to it, I want to persist it back to DB.

For this to work, I am currently abusing the labels from vertices and edges. For vertex it is a Keyword list and for edges it is a map.

It would be much more convenient if there was a metadata field for both and a function to set it. Something like:

Graph.put_metadata(g, v, %{id: 1234, comment: "some comment"}) # sets metadata for vertex
Graph.put_metadata(g, v1, v2, l, %{id: 1234, comment: "some comment"}) # sets metadata for edge

I can create a PR if this is a worthwhile feature.

Hello!

Thank you for your work that, cool stuff!
Any reason why not to include in add_vertices/2 API labels, like in case of add_vertex/3?

Cheers,
F.

The following code results in an infinite loop:

Graph.add_vertex(nil, "A")

The iex example is outdented by a space.

Given

graph =
  Graph.new
  |> Graph.add_vertices([1, 2, 4, 6])
  |> Graph.add_edge(1, 2)
  |> Graph.add_edge(2, 4)
  |> Graph.add_edge(4, 6)
  
graph_two = 
  graph
  |> Graph.add_vertices([3, 5, 7])
  |> Graph.add_edge(1, 3)
  |> Graph.add_edge(3, 4)
  |> Graph.add_edge(3, 5)
  |> Graph.add_edge(5, 6)
  |> Graph.add_edge(5, 7)

Test

assert graph == Graph.delete_vertices(graph_two, [3, 5, 7])
# The result is false

Inspect

Map.from_struct graph_two
%{
  edges: %{
    {539485162, 2577631668} => %{nil: 1},
    {1379807339, 3239926044} => %{nil: 1},
    {2577631668, 1379807339} => %{nil: 1}
  },
  in_edges: %{
    1379807339 => #MapSet<[1186525603, 2577631668]>,  #1186525603 dangling reference
    2577631668 => #MapSet<[539485162]>,
    3239926044 => #MapSet<[676967202, 1379807339]> #676967202 dangling reference
  },
  out_edges: %{
    539485162 => #MapSet<[2577631668]>,
    1379807339 => #MapSet<[3239926044]>,
    2577631668 => #MapSet<[1379807339]>
  },
  type: :directed,
  vertex_labels: %{
    539485162 => [],
    1379807339 => [],
    2577631668 => [],
    3239926044 => []
  },
  vertices: %{539485162 => 1, 1379807339 => 4, 2577631668 => 2, 3239926044 => 6}
}

These dangling references also raises nil enumeration errors when performing future operations.

Offending line

Graph.delete_vertex/2 is missing comprehension for in edges

Fix is to add

ie = for {id, ns} <- ie, do: {id, MapSet.delete(ns, v_id)}, into: %{}

How to reproduce:

These return the same ordering. This seems to be because the traversals are relying on Key ordering of the map

Graph.new() |> Graph.add_edges([{"123456", "b"}]) |> Graph.preorder
Graph.new() |> Graph.add_edges([{"123456", "b"}]) |> Graph.postorder

These do not return same ordering

Graph.new() |> Graph.add_edges([{"12345", "b"}]) |> Graph.preorder
Graph.new() |> Graph.add_edges([{"12345", "b"}]) |> Graph.postorder

Dialyzer complains The test [any()] == 'false' can never evaluate to 'true' when I try to check the output of Graph.topsort/1. Apparently the typespec annotation confused it. I guess one could either change the return value to :error | {:ok, sorted_graph} or change the typespec so that Dialyzer doesn't find it problematic? Or am I doing something wrong here.

Hello @bitwalker, thanks for your work on this lib.

I just cloned this repo, run mix deps.get and mix test and got the following error.

$ mix test
** (CompileError) test/model_test.exs:3: module :eqc_gen is not loaded and could not be found
    (eqc_ex) expanding macro: EQC.__using__/1
    test/model_test.exs:3: Graph.Model.Test (module)
    (elixir) expanding macro: Kernel.use/1
    test/model_test.exs:3: Graph.Model.Test (module)
    (eqc_ex) expanding macro: EQC.ExUnit.__using__/1
    test/model_test.exs:3: Graph.Model.Test (module)
    (elixir) expanding macro: Kernel.use/1
    test/model_test.exs:3: Graph.Model.Test (module)
    (elixir) lib/code.ex:370: Code.require_file/2
    (elixir) lib/kernel/parallel_require.ex:57: anonymous fn/2 in Kernel.ParallelRequire.spawn_requires/5

Is there anything more than mix deps.get that needs to be done in order to get up and running?

Thanks.

Environment

Erlang/OTP 20 [erts-9.0] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:10] [hipe] [kernel-poll:false]

Elixir 1.5.1

Ubuntu 16.04

Current behavior

Test is:

1. add a vertex with a non-nil label
2. delete the vertex
3. add the same vertex with nil label
4. get the vertex's label

The comparisons at the end confirms the label is the original one.

v1 = :v1
l1a = :l1a
l1b = nil

g = Graph.new()

g = g |> Graph.add_vertex(v1, l1a)

g = g |> Graph.delete_vertex(v1)

g = g |> Graph.add_vertex(v1, l1b)

l1c = g |> Graph.vertex_label(v1)

true = (l1c == l1a)
false = (l1c == l1b)

A quick look at the graph's stuct shows the old label to have been retained in the vertex_labels after the delete_vertex.

Expected behavior

The nil label should be used.

The DOT serialization feature is really handy! I can see myself adding TGF support in the future (in my copious free time) so there could be other serialization formats coming along.

In the meantime, the label text for edges should be quoted. I have a forward slash in my labels and noticed that it causes dot to spit out an error.

...syntax error in line 10 near '/'

The label looks like [label=HTTP/80; weight=1] but should look something like [label="HTTP/80"; weight=1].

Can I provide additional information or something?

Hi!

I found an example, where get_shortest_path didn't works, where it looks like it should:

g = Graph.new(type: :undirected) |> Graph.add_vertices([1, 2, 3]) |> Graph.add_edge(1, 3) |> Graph.add_edge(3, 2)
Graph.get_shortest_path(g, 1, 2) # => nil

I think, that get_shortest_path should raise on undirected graphs or calculate path correctly.

Hi @bitwalker, thank you for this awesome library. I have a use-case where I'm building up a dependency tree and I want to visit all of the leaf nodes first to resolve those before I bother to visit nodes that I know have unresolved dependencies.

I was thinking that I would fork this repo and open a PR that adds a Graph.leaf_vertices/1 function. I'm guessing that the implementation will look something like iterating through the in_edges keys (things that we know have a dependent) and skipping any items that also appear in the out_edges map. I think that should give me all of the leaf vertices in an efficient way?

I just wanted to check with you first if this was a desirable change to the project before I do the work to open the PR