delete_vertices does not work on subclassed graph

[chaosflaws]

Describe the bug

I have subclassed Graph and added a custom __init__ method by:

1. Creating an instance of the subclassed Graph
2. Calling igraph.Graph.__init__
3. Merging the existing graph into the new one

but this apparently fails when trying to delete vertices. The edge set is not updated properly. In the test, the graph is:

0 -> 0
1 -> 1

and the first edge has prop set to a while the second edge has prop set to b. Now, if I delete the first vertex, it would be expected that graph.es['prop'] returns b, but it returns a in the subclass case.

Fwiw, delete_vertices deals with vertex properties correctly and delete_edges seems to work fine as well.

To reproduce

Test case:

import unittest
from igraph import Graph


class TestSubclass(Graph):
    @staticmethod
    def __new__(cls, graph=None, *args, **kwargs):
        instance = super().__new__(cls, directed=True, *args, **kwargs)
        super().__init__(instance, directed=True, *args, **kwargs)

        if graph is not None:
            instance = instance.union(graph)

        return instance

    def __init__(self, graph=None, *args, **kwargs) -> None:
        pass


class SubclassTest(unittest.TestCase):
    def test_deleteVertices_igraph(self) -> None:
        graph = Graph(2, [(0, 0), (1, 1)], directed=True)
        graph.es['prop'] = ["a", "b"]

        graph.delete_vertices({1})

        self.assertEqual(["a"], graph.es['prop'])

    def test_deleteVertices_subclass(self) -> None:
        graph = Graph(2, [(0, 0), (1, 1)], directed=True)
        automaton = TestSubclass(graph)
        automaton.es['prop'] = ["a", "b"]

        automaton.delete_vertices({1})

        self.assertEqual(["a"], automaton.es['prop'])

    def test_incident_igraph(self) -> None:
        graph = Graph(4, [(0, 0), (1, 1), (2, 2), (3, 3)], directed=True)
        graph.es['prop'] = ["a", "b", "c", "d"]

        self.assertEqual(["a"], graph.es(_incident=[0])['prop'])

    def test_incident_subclass(self) -> None:
        graph = Graph(4, [(0, 0), (1, 1), (2, 2), (3, 3)], directed=True)
        automaton = TestSubclass(graph)
        automaton.es['prop'] = ["a", "b", "c", "d"]

        self.assertEqual(["a"], automaton.es(_incident=[0])['prop'])

    def test_deleteVertices_subclass_deleteEdge(self) -> None:
        graph = Graph(2, [(0, 0), (1, 1)], directed=True)
        automaton = TestSubclass(graph)
        automaton.es['prop'] = ["a", "b"]

        automaton.delete_edges({1})

        self.assertEqual(["a"], automaton.es['prop'])

    def test_deleteVertices_subclass_vertexSet(self) -> None:
        graph = Graph(2, [(0, 0), (1, 1)], directed=True)
        automaton = TestSubclass(graph)
        automaton.vs['prop'] = ["c", "d"]

        automaton.delete_vertices({1})

        self.assertEqual(["c"], automaton.vs['prop'])

Version information

igraph 0.9.8 on Python 3.9, also tested on igraph 0.9.1

[ntamas]

Thanks, I'll look into this before the upcoming 0.9.9 release, due in a few days.

[chaosflaws]

On further inspection, it appears that no graph manipulation is needed. graph.es(_incident=...) already seems to return wrong results. It looks like the list of propositions is in reverse order in some situations.

I have added test cases.

[ntamas]

Thanks! I'm not sure that it matters, but in the rare cases when I ever needed to override the __new__ method on any Python object, I did not declare it as @staticmethod so I've removed that from your test case, although it did not seem to make a difference.

Another thing that looks weird to me is to call super.__init__() from within the __new__ method. I haven't seen any Python code anywhere that does that, and I'm not sure whether it's legal or not. Sure, the current python-igraph implementation crashes without that when you call instance.union(), and it definitely shouldn't, but I guess that it should be solved in the C layer such that calling a method on the graph in __init__ does not crash the runtime.

May I ask what your original goal is with the subclassing? Maybe there's an easier way to solve your original goal while I sort out the underlying problem.

[ntamas]

Okay, I figured it out. There's nothing wrong with the code; the problem is that Graph.union() does not guarantee that it keeps the order of edges for the second graph that is merged into the first one. In this particular case, the order of edges in the second graph get reversed, and it seems like this is consistent across different graphs, but the documentation of the C core does not say anything about the edge ordering so it's not guaranteed to be this way. Anyhow, here is a simpler test case that uses the union() method only:

self = <tests.test_operators.OperatorTests testMethod=testUnionMethodWithEmptyGraph>

    def testUnionMethodWithEmptyGraph(self):
        g = Graph()
        g2 = Graph.Tree(7, 2)
>       self.assertEqual(g2.get_edgelist(), g.union(g2).get_edgelist())
E       AssertionError: Lists differ: [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)] != [(2, 6), (2, 5), (1, 4), (1, 3), (0, 2), (0, 1)]
E
E       First differing element 0:
E       (0, 1)
E       (2, 6)
E
E       - [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
E       + [(2, 6), (2, 5), (1, 4), (1, 3), (0, 2), (0, 1)]

I'll close this, but it would be great if you could explain your specific use-case to see if there is a simpler or more idiomatic solution. Is your goal to extend the Graph constructor in a way that it lets you specify another "seed" graph to overlay on top of the existing graph?

[chaosflaws]

Hi,

thanks for the investigation and sorry for my late comment. You're right, my original intention was to allow the subclass constructor to "enhance" an existing graph, adding properties and methods to the graph instance.

Sure, the current python-igraph implementation crashes without that when you call instance.union(), and it definitely shouldn't, but I guess that it should be solved in the C layer such that calling a method on the graph in __init__ does not crash the runtime.

This is precisely what put me off track here and led to the solution of calling the superclass' __init__ early (in __new__).

As it turns out, achieving my original goal only by overriding __init__ is possible, and it's not too un-ideomatic either (I think). The correct recipe for subclassing igraph with custom vertex and edge properties and a custom initializer would be:

class IgraphSub(Graph):
    instance_attr: bool

    def __init__(self, *args, vertex_property_list: List[bool] = None, **kwargs) -> None:
        super().__init__(*args, **kwargs)

        # set properties of vertices
        self.vs['property'] = vertex_property_list or [False] * len(self.vs)

        # set instance variables
        self.instance_attr = False

and using an existing graph instance is as easy as:

class SubclassTest(unittest.TestCase):
    def test_subclass(self) -> None:
        lattice = Graph.Lattice(dim=[4, 4])
        graph = IgraphSub(n=len(lattice.vs), edges=lattice.get_edgelist(), vertex_property_list=[True] * 16)

        self.assertEqual([True] * 16, graph.vs['property'])
        self.assertEqual(False, graph.instance_attr)

For some reason, though, this didn't work when I tried half a year ago (or maybe it did, and I was chasing ghosts back then).

So far, the documentation is silent on subclassing - I suppose adding this bit of code as a recipe to get people started might be a good idea?

[ntamas]

Thanks for the feedback and I'm glad that you managed to make it work by overriding __init__ only. (For what it's worth, the type annotation of vertex_property_list in your code should be Optional[List[bool]] because None is its default value).

I need to think about it a bit before deciding on how to include this in the docs. In general, I usually favour composition over inheritance so I wasn't thinking too much about subclassing the Graph object. Judging from the structure of the C code that binds the high-level Python Graph object to low-level igraph primitives in C, it seems like the rules would be something like this:

• overriding __new__ in a subclass is not supported
• overriding __init__ is supported, but you need to call super().__init__() first before doing anything with the graph, otherwise bad things may happen
• if you do happen to override __new__ despite the warnings, you need to call super.__new__() first, you are not allowed to call methods on the instance returned from super.__new__() before also calling super().__init__() on it, and you are not allowed to return anything but this instance from __new__

I think that in 99.99% of the cases you should be able to achieve what you want by overriding __init__() only. What I need to make sure is that igraph doesn't crash when you try to call a method on the graph before invoking super.__init__().

[iosonofabio]

The nuclear option would be to autodecorate all methods of Graph so they check if __init__ has been called (through a private property) and fail otherwise... It feels evil though

[ntamas]

Nah, I've made it so that an empty graph is created unconditionally in __new__, so if you call anything in __init__ before calling __init__ on the superclass, you will end up querying this empty graph instead. The "real" init then add vertices or edges as needed.

[iosonofabio]

hehe cleaner solution for sure