[FR] Construct a graph corresponding to a binary relation

[nsajko]

Homogeneous relations are equivalent to directed graphs, while relations that are additionally symmetric are more economically represented with undirected graphs.

I think it'd be nice if Graphs.jl provided an interface for constructing a graph from a finite relation. The relation could be described by a finite iterator and a binary predicate. The function would also take a graph type, the desired return type.

Does this seem like something that fits Graphs.jl?

[nsajko]

To be clear, I'm proposing the addition of a function like so:

"""
    from_finite_binary_relation(predicate, G::Type, finite_iterator)::G

Construct a graph of type `G` from a binary relation on `finite_iterator` defined by the predicate `predicate`.
"""
function from_finite_binary_relation end

[nsajko]

Not sure how to handle symmetric relations, perhaps there should be another function like from_finite_symmetric_relation?

[nsajko]

My motivation for this feature request is that I want an easy way to visualize partial order relations (like Julia's subtyping relation). It'd be nice if I could construct a SimpleDiGraph from my relation, then use transitivereduction to compute the covering relation/Hasse diagram.

[gdalle]

Thank you for the suggestion! I feel like that is easily achieved without adding custom logic to Graphs.jl:

julia> using Graphs

julia> julia> predicate((i, j)) = (i - j) % 3 == 0
predicate (generic function with 1 methods)

julia> edge_iter = Iterators.map(Edge, Iterators.filter(predicate, Iterators.product(1:10, 1:10)));

julia> g = SimpleGraphFromIterator(edge_iter)
{10, 22} undirected simple Int64 graph

julia> adjacency_matrix(g)
10×10 SparseArrays.SparseMatrixCSC{Int64, Int64} with 34 stored entries:
 2  ⋅  ⋅  1  ⋅  ⋅  1  ⋅  ⋅  1
 ⋅  2  ⋅  ⋅  1  ⋅  ⋅  1  ⋅  ⋅
 ⋅  ⋅  2  ⋅  ⋅  1  ⋅  ⋅  1  ⋅
 1  ⋅  ⋅  2  ⋅  ⋅  1  ⋅  ⋅  1
 ⋅  1  ⋅  ⋅  2  ⋅  ⋅  1  ⋅  ⋅
 ⋅  ⋅  1  ⋅  ⋅  2  ⋅  ⋅  1  ⋅
 1  ⋅  ⋅  1  ⋅  ⋅  2  ⋅  ⋅  1
 ⋅  1  ⋅  ⋅  1  ⋅  ⋅  2  ⋅  ⋅
 ⋅  ⋅  1  ⋅  ⋅  1  ⋅  ⋅  2  ⋅
 1  ⋅  ⋅  1  ⋅  ⋅  1  ⋅  ⋅  2