CODEWITHSUNDEEP
jupyter-notebooknetworkx
Fulla
Fulla

Reputation: 77

Write a function that implements the bridge detection algorithm

Algorithm: Bridge Detection Algorithm

Require: connected graph G(V,E)

  1. return Bridge Edges

  2. bridgeSet={}

3.for e(u,v) ε E do

  1. G'= Remove e from G

  2. Disconnected = False;

  3. if BFS in G' starting at u does not visit v then

  4. Disconnected = True;

  5. end if

  6. if Disconnected then

  7. bridgeSet= bridgeSet U {e}

  8. end if

  9. end for

  10. Return bridgeSet

  1. Imports all relevant modules / packages (like NetworkX, etc.);

  2. Uses the functionnetworkx.read_gmlto load the co-appearance network of characters of the novel“Les Misérable”. The data are available from the homepage of Prof. Mark Newman, which is onlineat www-personal.umich.edu/ mejn/netdata/;

  3. Calls the implemented bridge detection function on theLes Misérablenetwork, and prints all de-tected bridge edges, one edge per line.

I used networkx. Then read:

G=nx.read_gml('lesmis.gml') print (nx.info(G))

I have the idea but don't know how to implement it on jupyter: copy then remove from the copy so we don't have to do any tricks in implementation. I truly need help and I am stuck...

so far this is my output: Name: Type: Graph Number of nodes: 77 Number of edges: 254 Average degree: 6.5974 False

Upvotes: 0

Views: 333

Answers (1)

vurmux
vurmux

Reputation: 10020

NetworkX already has an algorithm for bridges searching: networkx.algorithms.bridges.bridges:

import networkx as nx

G = nx.fast_gnp_random_graph(30, 0.08, directed=False, seed=1)
list(nx.bridges(G))

[(0, 2), (10, 12), (12, 28), (13, 24), (15, 28), (23, 24)]

If you need the source code, you can find it here and here:

@not_implemented_for('multigraph')
@not_implemented_for('directed')
def bridges(G, root=None):
    chains = nx.chain_decomposition(G, root=root)
    chain_edges = set(chain.from_iterable(chains))
    for u, v in G.edges():
        if (u, v) not in chain_edges and (v, u) not in chain_edges:
            yield u, v

Upvotes: 0

Related Questions