ordering of the vertices of a graph - G.nodes()

[Sudarshan Iyengar]

>>>import networkx as nx
>>>G=nx.Graph()
>>>G.add_edges_from([('10', 'beta'), ('6', 'beta'), ('3', 'alpha'), ('1', 'alpha'), ('beta', '7'), ('beta', '8'), ('beta', '9'), ('beta', 'x'), ('2', 'alpha'), ('5', 'alpha'), ('4', 'alpha'), ('alpha', 'x')])

Now when i say G.nodes() i get the following output

>>>G.nodes()
['10', 'x', '3', '1', 'beta', '2', '5', '8', '7', '6', '9', 'alpha', '4']

In what way are these vertices ordered here? it is not alphabetical it
is not even based on the degrees.

Sudarshan

[Christopher Ellison]

The nodes are keys to a dictionary (G.adj)...and the ordering is
whatever G.adj.iterkeys() returns. Usually, the order matches the input
order, but this is not guaranteed.

On:

http://docs.python.org/library/stdtypes.html#dict.items

there is a comment about the CPython implementation which states that
the order of keys is non-random, but arbitrary, varying across Python
implementations and on the history of insertions and deletions.

If you need them sorted, you must do that separately.

Chris

[Sudarshan Iyengar]

Thank you Chris,

Could you tell me how one can sort the node list of a graph? So that
G.nodes() displays the entries in alphabetical order.?

Sudarshan

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

[Christopher Ellison]

Sudarshan Iyengar wrote the following on 12/02/2009 10:20 PM:
> Thank you Chris,
>
> Could you tell me how one can sort the node list of a graph? So that
> G.nodes() displays the entries in alphabetical order.?
>

Hi,

No problem, but this is no longer a NetworkX question---and general
python inquiries will be more helpful. For example, googling

"sort python list"

brings up:

http://wiki.python.org/moin/HowTo/Sorting

and suggests:

>>> nodes = G.nodes()
>>> nodes.sort()

as an appropriate solution.

Note: it is not possible to dictate how the dictionary stores its keys.
So you cannot make it so that G.nodes() displays the nodes in
alphabetical order. However, you can save the output of G.nodes(), sort
it, and keep it around for future use (as shown above).

Hope that helps,
Chris

[Sudarshan Iyengar]

Oh no! this surely is a networkx question :-)

I would want to sort the nodes in such a way that G.nodes() displays
the sorted order. My work involves removal of certain vertices and
checking the damage created to the graph and every-time i remove a
vertex G.nodes() gets haphazardly permuted.

Is there any way out?

Sudarshan

[Sudarshan Iyengar]

Surprisingly

>>>a=G.nodes()
>>>H=G.copy()
>>>b=H.nodes()

a and b are of different order!

Sudarshan

[Matteo Dell'Amico]

Sudarshan Iyengar ha scritto:

> Surprisingly
>
>>>> a=G.nodes()
>>>> H=G.copy()
>>>> b=H.nodes()
>
> a and b are of different order!

Just like dictionary keys in normal Python, it's just better to assume
that the nodes of a graph are not sorted in any way. G.nodes() is a
standard Python list, and of course you sort it as you do with all
Python lists.

matteo

[Erwin Marsi]

On 3 Dec 2009, at 08:39, Sudarshan Iyengar wrote:

> I would want to sort the nodes in such a way that G.nodes() displays
> the sorted order. My work involves removal of certain vertices and
> checking the damage created to the graph and every-time i remove a
> vertex G.nodes() gets haphazardly permuted.
>
> Is there any way out?
>
> Sudarshan

I'm using networkx for processing *ordered* trees (I know networkx was
not designed with trees in mind, but I like having the added-value of
a well-designed library instead of implementing and maintaining my own
tree class). You can keep the insertion order of the nodes by
replacing the dictionaries used for storing the edges by *ordered*
dictionaries. For the Digraph class, this involves self.pred and
self.succ/self.adj (no need to change self.nodes and self.graph). I
subclass Digraph as an OrderedDiGraph class, and override the
__init__, add_edge, add_edges_from, add_node, and add_nodes_from
methods, making sure that whenever a new dict for edges is created it
is an ordered dict. I imagine you can do the same thing for the other
graph classes.

You can find a pure Python recipe for an ordered dict by Raymond
Hettinger at http://code.activestate.com/recipes/576693/ OrderedDict
will be included in the standard library of Python 2.7 (http://docs.python.org/dev/library/collections.html#ordereddict-objects
). There are also faster alternatives like the ordereddict extension
module by Anton van der Neut (http://www.xs4all.nl/~anthon/Python/ordereddict/
).

Erwin

[Christopher Ellison]

Erwin Marsi wrote the following on 12/03/2009 03:12 AM:
>
> I'm using networkx for processing *ordered* trees (I know networkx was
> not designed with trees in mind, but I like having the added-value of
> a well-designed library instead of implementing and maintaining my own
> tree class). You can keep the insertion order of the nodes by
> replacing the dictionaries used for storing the edges by *ordered*
> dictionaries. For the Digraph class, this involves self.pred and
> self.succ/self.adj (no need to change self.nodes and self.graph). I
> subclass Digraph as an OrderedDiGraph class, and override the
> __init__, add_edge, add_edges_from, add_node, and add_nodes_from
> methods, making sure that whenever a new dict for edges is created it
> is an ordered dict.

This seems like a very nice, concise example of a subclass with general
applicability---ordered trees are certainly a useful data structure. I
wonder if NetworkX should consider including ordered versions of the
standard classes in the library. (There was an experimental
implementation of unordered trees in an earlier version of NetworkX.)
Thoughts anyone?

> You can find a pure Python recipe for an ordered dict by Raymond
> Hettinger at http://code.activestate.com/recipes/576693/ OrderedDict
> will be included in the standard library of Python 2.7 (http://docs.python.org/dev/library/collections.html#ordereddict-objects
> ). There are also faster alternatives like the ordereddict extension
> module by Anton van der Neut (http://www.xs4all.nl/~anthon/Python/ordereddict/
> ).
>

It looks like the Python recipe is API compatible with the OrderedDict
that will be included in Python 2.7. So it should definitely be
possible to write a subclass which transparently uses the most
appropriate version (perhaps even the extension by Anton van der Neut,
when available).

Chris