Skip to content

[BUG] Edge_subgraph fails due to implicitly caring about edge directionality on undirected graphs #175

Description

@JoeyT1994

In the current version of the library (0.12), edge_subgraph(g::NamedGraph, es::AbstractVector) is returning incorrect results.

For instance the last assertion here fails.

using NamedGraphs
using NamedGraphs.NamedGraphGenerators: named_hexagonal_lattice_graph
using NamedGraphs: NamedEdge, edges
using NamedGraphs.GraphsExtensions: edge_subgraph

g = named_hexagonal_lattice_graph(3, 3)
#Ring of six edges in the graph
es = NamedEdge.([(1, 1) => (2, 1), (2, 1) => (3, 1), (3, 1) => (3, 2), (2, 2) => (3, 2), (1, 2) => (2, 2), (1, 1) => (1, 2)])

#They are all in `g` (and specified in the correct direction)
@assert all([e ∈ edges(g) for e in es])

#Build the subgraph from these edges
eg = edge_subgraph(g,es)

#But now one of them is missing from the subgraph they induce...
@assert length(edges(eg)) == length(es)

but passes on older versions of the library (0.7 for instance).

This appears to be due to the fact that internally in edge_subgraph the call to _g = subgraph(g, vs) builds a subgraph with edges that may be defined in reverse compared to the original graph g and then the edge subgraph is built by removing a setdiff(edges(g), es) from _g which cares about edge directionality.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't working

    Type

    No type

    Fields

    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions