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'}} ?

EXO
  • 65
  • 2
  • 7
  • And how would you say let's say for example `graph = {'x':['y'], 'y':['x', 'z'], 'z': ['y']}` ? – Jerska Jul 17 '15 at 01:07
  • 2
    @EXO, it seems to fit the model of an adjacency list – Alejandro Jul 17 '15 at 01:14
  • @Jerska, `graph = {{x, y}, {y, z}}` – EXO Jul 17 '15 at 01:14
  • @Alejandro, Thanks for the term but why use one over the other? – EXO Jul 17 '15 at 01:20
  • 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. – John Coleman Jul 17 '15 at 01: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. – Barmar Jul 17 '15 at 01:27
  • @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 Jul 17 '15 at 01:42
  • @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 Jul 17 '15 at 01:50
  • @Barmar, so do undirected dictionaries exist? If so that would be super helpful. Then you could represent it as graph = {{'y'}<->{'x', 'z'}} – EXO Jul 17 '15 at 02:01
  • 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? – Barmar Jul 17 '15 at 02:07
  • 2
    So if that's what you want, you could easily write a class to encapsulate it. – Barmar Jul 17 '15 at 02:08
  • You are speaking a bit over my head. I suppose create a set of all elements in the graph? Or map every element to where it occurs in the graph? – EXO Jul 17 '15 at 02:09
  • You could just [use an existing library](https://stackoverflow.com/questions/606516/python-graph-library). – Anonymous Jul 17 '15 at 02:19
  • They don't fit my needs. – EXO Jul 17 '15 at 02:22
  • With billions of nodes, you're going to need to write your own class. Anything that doesn't take advantage of some underlying structure will be too slow and memory intensive to be useful. But asking "why do people recommend" isn't really going to get you anything useful if you've already decided the usual recommendation doesn't suit your needs. Figure out what you really need, why the existing solutions don't fulfill it, (and in your case, what underlying structure you can take advantage of). – Teepeemm Jul 17 '15 at 12:30

3 Answers3

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?

Anonymous
  • 11,740
  • 3
  • 40
  • 50
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.

fferri
  • 18,285
  • 5
  • 46
  • 95
  • 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. – John Coleman Jul 17 '15 at 01:33
  • 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. – fferri Jul 17 '15 at 01:45
  • I'm upvoting this because it does answer the question, but I agree with @JohnColeman . – Jerska Jul 17 '15 at 02:24
  • @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. – John Coleman Jul 17 '15 at 14:55
  • The "good" implementation of a graph highly depends on the intended use : adjacency matrix, incidence matrix, adjacency lists, incidence lists, etc. See [Wikipedia](https://en.wikipedia.org/wiki/Graph_theory#Graph-theoretic_data_structures). – Tom Cornebize Jul 20 '15 at 11:33
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'}
fferri
  • 18,285
  • 5
  • 46
  • 95
  • 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. – EXO Jul 17 '15 at 01:53
  • 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) – fferri Jul 17 '15 at 01:56
  • _@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_ – EXO Jul 17 '15 at 01:58
  • If there is an undirected dictionary then how would you have to tradeoff? I feel like this should be possible. – EXO Jul 17 '15 at 01:59
  • what's an "*undirected dictionary*"? – fferri Jul 17 '15 at 15:07
  • A dictionary that has undirected mapping. – EXO Jul 19 '15 at 02:51
  • There is no such thing in Python, unless you cook your implementation like I did in `UndirectedGraph` class, or like it has been done in [`bidict`](https://bidict.readthedocs.org/en/latest/intro.html) – fferri Jul 20 '15 at 00:19