CODEWITHSUNDEEP
python
thorwhalen
thorwhalen

Reputation: 2282

Checking if a python iterable is empty without relying on `len` or consuming the iterator

I've written the following code to reverse the edges of a graph, expressed as an adjacency list Mapping.

from typing import Mapping, Any, Sized
from collections import defaultdict

def edge_reversed_graph(g: Mapping[Any, Sized]):
    d = defaultdict(set)
    for src, dst_nodes in g.items():
        if len(dst_nodes):
            for dst in dst_nodes:
                d[dst].add(src)
        elif src not in d:
            d[src] = set()
    return d

Example:

>>> graph = dict(a='c', b='cd', c='abd', e='')
>>> assert edge_reversed_graph(graph) == {'c': {'a', 'b'}, 'd': {'c', 'b'}, 'a': {'c'}, 'b': {'c'}, 'e': set()}

I'd like to be able to just require the graph to be Mapping[Any, Iterable], that is the adjacency "list" not to necessarily have to have a length. This is achievable using a flag variable, but I'm looking for a more elegant and efficient solution, otherwise making the function work with a larger group of objects wouldn't be worth it to me.

Upvotes: 0

Views: 407

Answers (2)

MisterMiyagi
MisterMiyagi

Reputation: 51979

Checking whether the container/iterable of outgoing edges is empty is a red herring: Each node must always be ensured to exist.

  • If there are ingoing edges, it might have been added before. The node may not be overwritten even if it has no outgoing edges.
  • If there are outgoing but no ingoing edges, it must still be added. The node must exist regardless of ingoing edges.

This removes the need to check whether there are outgoing edges: Always add the src node if it does not exist. Always iterate all outgoing edges, of which there might be none.

from typing import Mapping, TypeVar, Iterable, Set
from collections import defaultdict

T = TypeVar('T')

def edge_reversed_graph(g: Mapping[T, Iterable[T]]) -> Mapping[T, Set[T]]:
    d = defaultdict(set)
    for src, dst_nodes in g.items():
        d.setdefault(src, set())  # add node if not present
        for dst in dst_nodes:     # empty iterable does nothing
            d[dst].add(src)
    return d

Upvotes: 1

Kelly Bundy
Kelly Bundy

Reputation: 27629

Similar to what I assume you mean with flag (having a bool variable set to True inside the loop), but more efficient:

def edge_reversed_graph(g: Mapping[Any, Iterable]):
    d = defaultdict(set)
    none = object()
    for src, dst_nodes in g.items():
        dst = none
        for dst in dst_nodes:
            d[dst].add(src)
        if dst is none:
            d[src] = set()
    return d

Upvotes: 0

Related Questions