CODEWITHSUNDEEP
python
user1191510
user1191510

Reputation: 21

Data structure to find components in undirected graphs in python

an undirected graph from is represented as a pair of nodes:

edges = (A,B),(B,C),(D,E),(F,E),(G,E),(G,I),(H,G)

What should be the best data structure in python to find the components of a

specific sub graph given a starting edge (e.g.

(D,E))?. I am thinking in using depth first search as the searching algorithm.

Upvotes: 2

Views: 882

Answers (2)

KobeJohn
KobeJohn

Reputation: 7545

If you just want a lightweight data structure, you can use a doubly linked (effectively undirected) pair of dictionaries.

Node Structure:

{"name": "something" , "connections": [list of connected nodes]}

some nodes from your data:

e = {"name": "E"}
d = {"name": "D"}
f = {"name": "F"}
g = {"name": "G"}

e["connections"] = [d,f,g]
#... etc with whatever code you want to build the graph itself

Then use whatever algorithm you want. If you want to know the algorithm, please adjust your question. As mvanveen mentioned, use a graph library if you can. This is well-tread territory.

Upvotes: 0

mvanveen
mvanveen

Reputation: 10028

Have you checked out the networkx library? If you're not starting from scratch it provides great primitives data structure for graphs of all shapes and sizes.

Included is the Graph.subgraph method which you can read up on here.

From the docs:

>>> G = nx.Graph()   # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_path([0,1,2,3])
>>> H = G.subgraph([0,1,2])
>>> H.edges()
[(0, 1), (1, 2)]

Upvotes: 4

Related Questions