5

Python does not have direct support for graphs but a lot of sources are saying they can be represented using dictionaries eg. 

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

since this is an undirected graph and dictionaries are directional mapping, it seems really inconcise. Is it really better to say graph = {'x':['y'], 'y':['x']} rather than graph = {{'x', 'y'}} ?

Improve this question
15
  • 2
    @EXO, it seems to fit the model of an adjacency list Commented Jul 17, 2015 at 1:14
  • 2
    Many graph algorithms involve scanning the set of edges which radiate from a given node. It is incredibly useful to have a representation that makes that easy, even at the cost of a certain amount of redundancy. Commented Jul 17, 2015 at 1:27
  • 2
    Think about what you do with a graph. You start at a node, and you want to know what nodes you can get to from it. How would you do that with your notation? You would have to search the list of tuples, looking for any pair that contains the starting node. Commented Jul 17, 2015 at 1:27
  • 2
    An undirected dictionary would almost certainly have to be implemented internally as the dictionary in your question. Every time you added an a<=>b entry, it would actually push b onto the a=>[] list and push a onto the b=>[] list. Otherwise, how would you make the lookups by a and b both efficient? Commented Jul 17, 2015 at 2:07
  • 2
    So if that's what you want, you could easily write a class to encapsulate it. Commented Jul 17, 2015 at 2:08

3 Answers 3

Reset to default
2

Storing them as connections makes it very easy to walk:

vertex = 'x'
connected_to = graph[vertex]
second_degree_connections = {p for subset in graph[p] for p in connected_to}

Try doing that efficiently with a set of two-tuples. Not very easy, right?

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

If the graph is undirected, a set of 2-elements sets is more suitable to represent it:

graph = set()

Add edge:

>>> graph.add(frozenset(('a', 'b')))

(note: you have to use frozenset() which is immutable, because set() is not hashable due to its mutability)

Check if an edge is in graph:

>>> {'b', 'a'} in graph
True

Add more edges:

>>> graph.add(frozenset(('a', 'c')))
>>> graph.add(frozenset(('c', 'd')))
>>> graph.add(frozenset(('d', 'e')))
>>> graph.add(frozenset(('d', 'f')))

Get edges touching 'd':

>>> set(x for x in graph if 'd' in x)
{frozenset({'c', 'd'}), frozenset({'f', 'd'}), frozenset({'d', 'e'})}

However, for the last operation, a representation using dictionaries is more efficient in terms of time.

Improve this answer

5 Comments

Not a bad answer (certainly not worthy of a downvote) but in many ways your last sentence contradicts your first. Unless the graphs are so incredibly large that memory is an issue, it is a slam-dunk that ordered pairs rather than 2-element sets are more useful.
I don't see the contradiction. However yes I don't feel very much to recommend this answer of mine. In most cases an approach using double dictionaries is better. I'll add it in another answer.
I'm upvoting this because it does answer the question, but I agree with @JohnColeman .
@mescalinum The sense in which it is a (partial) contradiction is that the first sentence was unqualified but that last sentence gave a qualification which (in many applications -- especially ones for which Python is appropriate) undermines the first. Nevertheless, it seems that OP is interested in an application in which memory use is more important than speed, so I'll upvote it as well.
The "good" implementation of a graph highly depends on the intended use : adjacency matrix, incidence matrix, adjacency lists, incidence lists, etc. See Wikipedia.
0

An undirected graph is a particular type of directed graph, where for each edge (a, b) there exists also (b, a).

So you can implement it storing edges twice (normal and reversed), but better write a class to keep it consistent:

from collections import defaultdict

class UndirectedGraph:
    def __init__(self):
        self.edge = defaultdict(set)

    def add_edge(self, a, b):
        self.edge[a].add(b)
        self.edge[b].add(a)

    def remove_edge(self, a, b):
        self.edge[a].remove(b)
        self.edge[b].remove(a)

    def has_edge(self, a, b):
        return b in self.edge[a] or a in self.edge[b]

    def neighbours(self, a):
        return set(self.edge[a])

This is very basic, and depending on the operations you want to do, you may remove some method or you may need to add others.

>>> g=UndirectedGraph()
>>> g.add_edge('a','b')
>>> g.add_edge('a','c')
>>> g.add_edge('c','d')
>>> g.add_edge('a','d')
>>> g.remove_edge('a','d')
>>> g.has_edge('a','d')
False
>>> g.has_edge('a','c')
True
>>> g.neighbours('c')
{'a', 'd'}
Improve this answer

7 Comments

yes, maybe it's true you can represent an "undirected edge" using two directed edges but the point is to make it efficient and not take up unnecessary memory and time.
there is a tradeoff: either you choose to store twice the edges or equivalently to have two indices for accessing vertices neighbours on O(1), or you are memory efficient but slower, i.e. O(n)
@JohnColeman, so do bidirectional or undirected dictionaries exist? If so that would be super helpful. Then you could represent it as graph = {'y'<->{'x', 'z'}} or maybe graph = {{'y'}<->{'x', 'z'}} Im not sure – EXO 12 mins ago @JohnColeman, also the graph/graph of graphs will contain millions to billions of nodes that doesn't even include edges and my harddrive is only 1.5 terabytes so its vital to construct this as concise and compressed as possible. – EXO 4 mins ago
If there is an undirected dictionary then how would you have to tradeoff? I feel like this should be possible.
what's an "undirected dictionary"?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.