how to select two nodes (pairs of nodes) randomly from a graph that are NOT connected to each other
817 views
Skip to first unread message
Muhammad Irfan Ali Shah
Jun 7, 2012, 6:46:40 AM6/7/12
to networkx-discuss
I want to extract two nodes from a graph, the catch being that they
shouldnt be connected i.e. no direct edge exists between them. i know
i can get random edges using "random.choice(g.edges())" but this would
give me random nodes that are connected. I want random pairs of nodes
that are NOT connected to each other (a pair of unconnected edges).
The nodes are connected to the overall graph but not to each other. I
am loading the graph from a gpickle file and need to find "pairs of
nodes" that are not connected to each other. help me out guys...thanx
shouldnt be connected i.e. no direct edge exists between them. i know
i can get random edges using "random.choice(g.edges())" but this would
give me random nodes that are connected. I want random pairs of nodes
that are NOT connected to each other (a pair of unconnected edges).
The nodes are connected to the overall graph but not to each other. I
am loading the graph from a gpickle file and need to find "pairs of
nodes" that are not connected to each other. help me out guys...thanx
Raf Guns
Jun 7, 2012, 6:55:26 AM6/7/12
to networkx...@googlegroups.com
Hi,
With itertools.combinations you can easily obtain all possible node pairs. Just filter out the ones that are already connected, like this:
In [30]: import networkx as nx
In [31]: from itertools import combinations
In [32]: G = nx.path_graph(10)
In [33]: [(u, v) for u, v in combinations(G, 2) if not G.has_edge(u, v)]
Out[33]:
[(0, 2),
(0, 3),
(0, 4),
...
Note though that this may result in very long lists for larger graphs.
Raf
With itertools.combinations you can easily obtain all possible node pairs. Just filter out the ones that are already connected, like this:
In [30]: import networkx as nx
In [31]: from itertools import combinations
In [32]: G = nx.path_graph(10)
In [33]: [(u, v) for u, v in combinations(G, 2) if not G.has_edge(u, v)]
Out[33]:
[(0, 2),
(0, 3),
(0, 4),
...
Note though that this may result in very long lists for larger graphs.
Raf
Muhammad Irfan Ali Shah
Jun 7, 2012, 7:37:12 AM6/7/12
to networkx...@googlegroups.com
Can this be extended to nodes having certain color. i mean i colored the certain types of edges in red and blue...can you think of a way that i can get nodes that dont have a blue colored edge but its ok if the nodes have a red colored edge or no edge at all.
--
--
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.
Regards & Respect,
Muhammad Irfan Ali Shah
General Secretary, GPSG
Daπid
Jun 7, 2012, 9:43:55 AM6/7/12
to networkx...@googlegroups.com
If your graph is not very connected, you can always choose two random
nodes and reject them if there is an edge between them.
On Thu, Jun 7, 2012 at 1:37 PM, Muhammad Irfan Ali Shah
nodes and reject them if there is an edge between them.
On Thu, Jun 7, 2012 at 1:37 PM, Muhammad Irfan Ali Shah
Thomas Capelle
Jun 7, 2012, 10:09:01 AM6/7/12
to networkx...@googlegroups.com
Has anyone implemented a pickup and delivery algorithm in nx?
Raf Guns
Jun 8, 2012, 2:30:48 AM6/8/12
to networkx...@googlegroups.com
How are the edges colored? If you mean that they have an extra attribute 'color' (or sth similar), you could try:
import networkx as nx
from itertools import combinations
G = nx.path_graph(10)
[(u, v) for u, v in combinations(G, 2) if not G.has_edge(u, v) or G.edge[u][v]['color'] == 'red']
import networkx as nx
from itertools import combinations
G = nx.path_graph(10)
[(u, v) for u, v in combinations(G, 2) if not G.has_edge(u, v) or G.edge[u][v]['color'] == 'red']
Reply all
Reply to author
Forward
0 new messages