Königsberg Bridges using Networkx

Question

I am trying to plot the graph of the famous problem of Königsberg Bridges using NetworkX and Python 3.8

This the code I am using:

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np

G=nx.Graph()

G.add_node(1)  ## Land A
G.add_node(2)  ## Land B
G.add_node(3)  ## Land C
G.add_node(4)  ## Land D

## Connected Edges
G.add_edge(1,3,color='r',weight=1)  ## Bridge 1
G.add_edge(1,3,color='r',weight=1)  ## Bridge 2
G.add_edge(1,4,color='r',weight=1)  ## Bridge 3
G.add_edge(3,4,color='r',weight=1)  ## Bridge 4
G.add_edge(1,2,color='r',weight=1)  ## Bridge 5
G.add_edge(1,2,color='r',weight=1)  ## Bridge 6
G.add_edge(2,4,color='r',weight=1)  ## Bridge 7


colors = nx.get_edge_attributes(G,'color').values()
weights = nx.get_edge_attributes(G,'weight').values()

names = {1:"Land A",2:"Land B",3:"Land C",4:"Land D"}
H=nx.relabel_nodes(G,names)

pos = nx.circular_layout(H)
nx.draw_networkx(H,pos,edge_color=colors,width=list(weights))

plt.savefig("konigsberg_bridges_graph.png")
plt.show()

and the Graph generated is this one:

The problem is that is very different from the graphs that appear on internet:

How can I do a graph similar to that one using NetworkX?

To model the situation, you would need to use a `MultiGraph` rather than a `Graph` object. This works from a modeling point of view, but unfortunately merely replacing `nx.Graph` by `nx.MultiGraph` doesn't lead to a better plot (although it leads to a better data structure). NetworkX plotting algorithms seem to collapse parallel edges into single edges. See [this question](https://stackoverflow.com/q/10379448/4996248) for more. — John Coleman, Jun 26 '20 at 01:51
You should be able to reproduce defining a MultiGraph and exporting to a dot file, see an example [here](https://stackoverflow.com/a/61390499/9698684) — yatu, Jun 26 '20 at 08:43

score 1 · Answer 1 · answered Jun 26 '20 at 13:34

To expand on the comments, you'll need a MultiGraph for multiple edges between two nodes:

G=nx.MultiGraph()

G.add_node(1)  ## Land A
G.add_node(2)  ## Land B
G.add_node(3)  ## Land C
G.add_node(4)  ## Land D

## Connected Edges
G.add_edge(1,3,color='r',weight=1)  ## Bridge 1
G.add_edge(1,3,color='r',weight=1)  ## Bridge 2
G.add_edge(1,4,color='r',weight=1)  ## Bridge 3
G.add_edge(3,4,color='r',weight=1)  ## Bridge 4
G.add_edge(1,2,color='r',weight=1)  ## Bridge 5
G.add_edge(1,2,color='r',weight=1)  ## Bridge 6
G.add_edge(2,4,color='r',weight=1)  ## Bridge 7

colors = nx.get_edge_attributes(G,'color').values()
weights = nx.get_edge_attributes(G,'weight').values()

names = {1:"Land A",2:"Land B",3:"Land C",4:"Land D"}
H=nx.relabel_nodes(G,names)

To visualise the network you could use Graphviz which does display parallel edges. You could write the graph in dot and display the graph with graphviz.Source:

path = 'multig.dot'
nx_pydot.write_dot(H, path)
Source.from_file(path)

great, but just a fussy question: is not possible to arrange the nodes in a way that looks exactly like in the common graph that is used while studying this problem? I know both graphs represent the same thing, and in graph theory, they are actually the same, but I wanted to know if it was possible to arrange nodes the way whatever one would might like, having this extra customization — Dau, Jun 26 '20 at 21:05
Never really done smth like this. I think you should be able to using graphviz, see https://stackoverflow.com/questions/5343899/how-to-force-node-position-x-and-y-in-graphviz @DieDauphin — yatu, Jun 27 '20 at 10:29

score 0 · Accepted Answer · answered Dec 09 '21 at 09:58

I'm not sure if this counts as an answer, but I found easier to do the Königsberg Bridges graph using LaTeX and TikZ

This is the code:

\documentclass{article} 
\usepackage{tikz} 

\begin{document} 

    \begin{tikzpicture}[thick, main/.style = {draw, circle}] 
        \node[main,scale=0.6, label=left:$a$] (a) at (0,0) {}; 
        \node[main,scale=0.6, label=left:$b$] (b) at (0,2) {}; 
        \node[main,scale=0.6, label=left:$c$] (c) at (0,4) {}; 
        \node[main,scale=0.6, label=right:$d$] (d) at (4,2) {}; 
        
        \draw (a) -- (d);
        \draw (b) -- (d);
        \draw (c) -- (d);
        \draw (a) to [out=120,in=240,looseness=1] (b);
        \draw (a) to [out=60,in=300,looseness=1] (b);
        
        \draw (b) to [out=120,in=240,looseness=1] (c);
        \draw (b) to [out=60,in=300,looseness=1] (c);

    \end{tikzpicture} 

\end{document}

The resulted image is:

It's also possible to create a tex file using python, that way it's possible to use NetworkX too, this is the code:

import os
import networkx as nx

G=nx.Graph()

G.add_node('1', land="a")  ## Land A
G.add_node('2', land="b")  ## Land B
G.add_node('3', land="c")  ## Land C
G.add_node('4', land="d")  ## Land D

## Connected Edges
G.add_edge(1, 3)  ## Bridge 1
G.add_edge(1, 3)  ## Bridge 2
G.add_edge(1, 4)  ## Bridge 3
G.add_edge(3, 4)  ## Bridge 4
G.add_edge(1, 2)  ## Bridge 5
G.add_edge(1, 2)  ## Bridge 6
G.add_edge(2, 4)  ## Bridge 7

with open('konigsberg.tex','w') as file:
     file.write('\\documentclass[margin=1mm]{standalone}\n')
     file.write('\\usepackage{tikz} \n')
     file.write('\\begin{document}\n')
     file.write('\\begin{tikzpicture}[thick, main/.style = {draw, circle}] \n')
     file.write('\\node[main,scale=0.6, label=left:$' + G.nodes['1']['land'] + '$] (' + G.nodes['1']['land'] + ') at (0,0) {}; \n')
     file.write('\\node[main,scale=0.6, label=left:$' + G.nodes['2']['land'] + '$] (' + G.nodes['2']['land'] + ') at (0,2) {}; \n')
     file.write('\\node[main,scale=0.6, label=left:$' + G.nodes['3']['land'] + '$] (' + G.nodes['3']['land'] + ') at (0,4) {}; \n')
     file.write('\\node[main,scale=0.6, label=right:$' + G.nodes['4']['land'] + '$] (' + G.nodes['4']['land'] + ') at (4,2) {}; \n')
     file.write('\\draw (' + G.nodes['1']['land'] + ') -- (' + G.nodes['4']['land'] + '); \n')
     file.write('\\draw (' + G.nodes['2']['land'] + ') -- (' + G.nodes['4']['land'] + '); \n')
     file.write('\\draw (' + G.nodes['3']['land'] + ') -- (' + G.nodes['4']['land'] + '); \n')
     file.write('\\draw (' + G.nodes['1']['land'] + ') to [out=120,in=240,looseness=1] (' + G.nodes['2']['land'] + '); \n')
     file.write('\\draw (' + G.nodes['1']['land'] + ') to [out=60,in=300,looseness=1] (' + G.nodes['2']['land'] + '); \n')
     file.write('\\draw (' + G.nodes['2']['land'] + ') to [out=120,in=240,looseness=1] (' + G.nodes['3']['land'] + '); \n')
     file.write('\\draw (' + G.nodes['2']['land'] + ') to [out=60,in=300,looseness=1] (' + G.nodes['3']['land'] + '); \n')
     file.write('\\end{tikzpicture}  \n')
     file.write('\\end{document}\n')

os.system("pdflatex konigsberg.tex")

running this code using Python3 and Ubuntu 20.04 generates the same graph

Königsberg Bridges using Networkx

2 Answers2