[BUG] Inconsistent behavior between AdjacencyGraph.Vertices and AdjacencyGraph.TryGetOutEdges

[AxelMarquez]

Describe the bug When a vertex is added multiple times AdjacencyGraph.Vertices returns the first declaration whereas AdjacencyGraph.TryGetOutEdges returns the last one; see the next example.

To Reproduce

class Person
{
    public string Name { get; set; }
    public int Age { get; set; }

    public override int GetHashCode() => Name.GetHashCode();
    public override bool Equals(object obj) => Name.Equals(((Person)obj).Name);
}

static void Main(string[] args)
{
    var graph = new AdjacencyGraph<Person, Edge<Person>>();

    graph.AddVerticesAndEdge(
        new Edge<Person>(
            new Person { Name = "Axel", Age = 10 },
            new Person { Name = "son" }
        )
    );

    graph.AddVerticesAndEdge(
        new Edge<Person>(
            new Person { Name = "parent" },
            new Person { Name = "Axel", Age = 20 }
        )
    );

    var edges = Enumerable.Empty<Edge<Person>>();
    graph.TryGetOutEdges(graph.Vertices.Single(v => v.Name == "parent"), out edges);

    var success = graph.Vertices.Single(v => v.Name == "Axel").Age == edges.Single().Target.Age;
}

Notice how graph.Vertices.Single(v => v.Name == "Axel").Age returns 10 but edges.Single().Target.Age returns 20.

An interesting remark is that if you invert the AddVerticesAndEdge statements so that the vertices are created as parent -> Axel -> son then both graph.Vertices and edges agree that Axel.Age is 10.

A workaround is to only instantiate Axel Person once.

Expected behavior AdjacencyGraph.Vertices and AdjacencyGraph.TryGetOutEdges should return the same vertex.

[KeRNeLith]

Hello,

Thank you for your interest to QuikGraph!

The scenario your describing is a bit fishy indeed. BTW I'm not really sure about how we can prevent such situation since we're working on different instances, and each of them is setup differently.

About reversing order of AddVerticesAndEdge, the result is both saying Axel.Age is 20 and not 10.

What you should know is that graph are updated this way when calling AddVerticesAndEdge, first it tries to add both vertices, first edge source and then edge target, then it add the edge. Note that each add operation can be cancelled if there is already the corresponding entity in the graph. Here is a bit of explanations, for situation 1 (Add Axel -> son, next add parent -> Axel) and situation 2 (Add parent -> Axel, next add Axel -> son). When referring to Axel vertex object instance there is one with age 10 (instance1) and one with age 20 (instance2).

• Situation 1:

  • Call 1: You add vertex Axel (instance1) to the set of vertices. You add vertex son to the set of vertices. You add edge Axel (instance1) -> son to the set of edges.

  • Call 2: You add vertex parent to the set of vertices. You TRY to add vertex Axel (instance2) to the set of vertices but is NOT added because of equals. You add edge parent -> Axel (instance2) to the set of edges.

So graph is composed of: Vertices: parent, Axel (instance1), son Edges: parent -> Axel (instance2) and Axel (instance1) -> son

• Situation 2:

  • Call 1: You add vertex parent to the set of vertices. You add vertex Axel (instance2) to the set of vertices. You add edge parent -> Axel (instance2) to the set of edges.

  • Call 2: You TRY to add vertex Axel (instance1) to the set of vertices but is NOT added because of equals. You add vertex son to the set of vertices. You add edge Axel (instance1) -> son to the set of edges.

So graph is composed of: Vertices: parent, Axel (instance2), son Edges: parent -> Axel (instance2) and Axel (instance1) -> son

Conclusion

In both cases you have 2 edges with "equivalent" vertices content in the graph but not the same object instance. But the main difference is that in one case the Axel vertex is used in an in-edge and and in the other case it is used in an out-edge. That's why you get different results based on the call order, because in the situation 2 the graph vertices is composed of the vertex (instance2) being in out-edges of parent, but in situation 1 the graph vertices is not composed of the vertex (instance2) in out-edges of parent but in in-edge of Axel (instance1).

As you can see order induced that the graph contains "different" content in term of object instances, but also the content itself involve different things, and that explains why you have such result in the end. BTW the graph content is coherent with the information that were given as inputs.

Note that since your feeding a graph with object considered equivalent but that in fact are not really it's quite difficult to maintain coherent results :s