Hasse Diagrams with NetworkX

[Jax]

Hi there,

I just found networkx a couple days ago. Seems like an awesome
library.

I was wondering if we have an easy way to generate so called Hasse
Diagrams with networkx.

Here's how they look: http://en.wikipedia.org/wiki/Hasse_diagram
Specifically the first diagram you see there à la: The power set of
{ x, y, z } partially ordered by inclusion, has the Hasse diagram...

Say i have an alphabet: L = set(['A', 'B', 'C', 'D']) and would like
to generate the Hasse Diagram for it, do we have an easy way in
networkx? I see a lot of algorithms for graph generation, but nothing
related to this.

Have a nice new year!

Gabe

[Dan Schult]

If I understand correctly, you'd like a way to create a Hasse Diagram
graph by specifying a set of nodes and a partial ordering. The other
way to interpret your question is whether networkx can draw it.

The hard part of generating the graph seems to be specifying the
partial ordering. If you can get a function that returns True if the
input
pair is ordered then you could do something like:

G=nx.DiGraph()
L=set(['A','B','C','D'])
G.add_edges_from( (a,b) for a in L for b in L if p_order(a,b) )

Drawing it requires getting a layout of the nodes (which is hard in
general).
NetworkX has some simple layout routines (see http://
networkx.lanl.gov/gallery.html)
and it has some hooks into Graphviz (via pygraphviz or pydot) that
can return layouts.
Dan

> --
>
> You received this message because you are subscribed to the Google
> Groups "networkx-discuss" group.
> To post to this group, send email to networkx-
> dis...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discuss
> +unsub...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/
> group/networkx-discuss?hl=en.
>
>

[Jax]

Thanks for your answer!

I'm not so interested in drawing it, even though graphviz does draw it
correctly (I currently have an algorithm to make such
a Hasse Diagram based on itertools).

It's probably quite ugly, but this how it works:

# chain and combinations is from itertools
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3)
(1,2,3)"
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)
+1))

u = list(powerset(L))
# gives [(), ('A',), ('C',), ('B',), ('D',), ('A', 'C'), ('A', 'B'),
('A', 'D'), ('C', 'B'), ('C', 'D'), ('B', 'D'), ('A', 'C', 'B'), ('A',
'C', 'D'), ('A', 'B', 'D'), ('C', 'B', 'D'), ('A', 'C', 'B', 'D')]

then, since it's ordered, i just do something like this to create the
networkx DiGraph:
graph = nx.DiGraph()
for node_tiny in u:
for node_big in u:
# Connect the predecessor with any successor of a layer 1
above
if len(node_tiny) == len(node_big)-1:
# only connect if it's a subset of the bigger node
if frozenset(node_tiny) < frozenset(node_big):
graph.add_edge(node_tiny, node_big)

that seems to work but i have no idea if it's really efficient or
not..

I was also wondering if it's possible to easily get the nodes that do
not have any outgoing edges, i.e THE maximal node in such a Hasse
Diagram as above.

Many thanks for your help.

Gabe

[Dan Schult]

If you always need it for a powerset, then you can build the graph
while you build the powerset:

def powerset_hasse_diagram(L):
G=nx.DiGraph()
G.add_node(())

for n in L:
newedges=[] # need to avoid changing G in next loop
for s in G:
n2=s+(n,)
newedges.append( (s,n2) )
for p in G.pred[s]:
newedges.append( (p+(n,),n2) )
G.add_edges_from(newedges)
return G

G=powerset_hasse_diagram(range(4))
print G.edges()
# gives [((0, 1), (0, 1, 2)), ((0, 1), (0, 1, 3)), ((1, 2), (0, 1,
2)), ((1, 2), (1, 2, 3)), ((0,), (0, 1)), ((0,), (0, 3)), ((0,), (0,
2)), ((1,), (0, 1)), ((1,), (1, 2)), ((1,), (1, 3)), ((0, 1, 2), (0,
1, 2, 3)), ((2,), (1, 2)), ((2,), (2, 3)), ((2,), (0, 2)), ((3,), (0,
3)), ((3,), (1, 3)), ((3,), (2, 3)), ((0, 1, 3), (0, 1, 2, 3)), ((0,
2, 3), (0, 1, 2, 3)), ((), (2,)), ((), (0,)), ((), (3,)), ((), (1,)),
((2, 3), (0, 2, 3)), ((2, 3), (1, 2, 3)), ((1, 3), (1, 2, 3)), ((1,
3), (0, 1, 3)), ((0, 3), (0, 2, 3)), ((0, 3), (0, 1, 3)), ((1, 2, 3),
(0, 1, 2, 3)), ((0, 2), (0, 1, 2)), ((0, 2), (0, 2, 3))]