mXSCNT
- 310
- 1
I ran some tests, adding edges randomly and independently of one another. If the expected number of hookups for any given person is around 1, for a few hundred people you do typically get one large component, which is almost a tree (very few cycles)--so perhaps the lack of cycles is not noteworthy.
My source code (python):
My source code (python):
Code:
import random
from copy import deepcopy
# create a graph with numnodes nodes, where each edge has a probability
# of existing such that the expected number of edges to a given node
# is avgconnects
# graph is stored as an adjacency list dict
# no self-edges
def randgraph(numnodes,avgconnects):
graph = {}
nodes = range(numnodes)
prob = float(avgconnects)/(numnodes-1)
for x in nodes:
graph[x] = set([])
for x in nodes:
for y in nodes[:x]:
if random.random() <= prob:
graph[x].add(y)
graph[y].add(x)
return graph
# create a random graph of boys and girls
# where boy nodes connect only to girl nodes
# and girl nodes connect only to boy nodes
# and the expected number of edges to any node is avgconnects
# (if the number of boys and girls is unequal,
# this may result in higher or lower averages for each gender)
def boygirlgraph(boynum,girlnum,avgconnects):
graph = {}
boys = ['b' + str(x) for x in range(boynum)]
girls = ['g' + str(x) for x in range(girlnum)]
prob = float(avgconnects)*(boynum+girlnum)/(2*boynum*girlnum)
for x in boys + girls:
graph[x] = set([])
for b in boys:
for g in girls:
if random.random() <= prob:
graph[b].add(g)
graph[g].add(b)
return graph
# imperatively remove the node from the graph
# assumes all edges are bidirectional
def removenode(node,graph):
for x in graph[node]:
graph[x].remove(node)
graph.pop(node)
# return a list of connected components, each component being a set of nodes
# the largest components appear first in the list
def componentlist(graph):
components = []
tmpgraph = deepcopy(graph)
while len(tmpgraph) > 0:
(node,adj) = tmpgraph.iteritems().next()
curcomp = set([])
def descend(node):
adj = tmpgraph[node]
curcomp.add(node)
for x in adj:
if not x in curcomp:
descend(x)
descend(node)
components.append(curcomp)
for x in curcomp:
removenode(x,tmpgraph)
components.sort(key=len,reverse=True)
return components
# return the subgraph including only those nodes in the component given
def subgraph(component,graph):
tmpgraph = {}
for x in graph:
if x in component:
tmpgraph[x] = graph[x] & component
return tmpgraph
# In a maximal connected component, how many edges would need to be removed
# to turn the component into a tree?
def numcycles(component, graph):
nedges = 0
for x in component:
nedges += len(graph[x])
nedges /= 2
# tree has len(component) - 1 edges
return nedges - len(component) + 1
# convert to graphviz/dot format
def dotfmt(graph):
conns = [str(a) + ' -- ' + str(b) + ' ;' for a in graph for b in graph[a] if a < b]
return "graph{\n" + '\n'.join(conns) + '\n}\n'