50 views

Skip to first unread message

Aug 26, 2024, 3:27:12 PMAug 26

to networkx-discuss

I've been working on a problem of finding Hamiltonian path in a fairly simple network and found things that defied my understanding of what is a tournament graph. To get to the bottom of it, I condensed the code to the simplest test I could think of.

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3,0)])

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.remove_edge(3,0)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.remove_edge(2,3)

G.remove_node(3)

G.add_edge(2,0)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.remove_edge(2,0)

G.add_node(3)

G.add_edge(2,3)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.add_edge(3,0)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

When I run it in on Python 3.9.19 with NetworkX 3.2.1 in anaconda3 environment, I get the following results:

(base) C:\My Documents\Notes>python TourTest.py

DiGraph with 4 nodes and 4 edges

[(0, 1), (1, 2), (2, 3), (3, 0)]

Is G tournament ? False

DiGraph with 4 nodes and 3 edges

[(0, 1), (1, 2), (2, 3)]

Is G tournament ? False

DiGraph with 3 nodes and 3 edges

[(0, 1), (1, 2), (2, 0)]

Is G tournament ? True

DiGraph with 4 nodes and 3 edges

[(0, 1), (1, 2), (2, 3)]

Is G tournament ? False

DiGraph with 4 nodes and 4 edges

[(0, 1), (1, 2), (2, 3), (3, 0)]

Is G tournament ? False

(base) C:\My Documents\Notes>

Please, explain to me what is wrong with this picture, as my understanding is that there must be a bug in the is_tournament() function. I have not seen any mentions of the size limitations on tournament graphs (3 nodes and edges OK, but 4 not acceptable ?)

Regards,

E.Z. Polch

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3,0)])

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.remove_edge(3,0)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.remove_edge(2,3)

G.remove_node(3)

G.add_edge(2,0)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.remove_edge(2,0)

G.add_node(3)

G.add_edge(2,3)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

G.add_edge(3,0)

print (G)

print (G.edges)

print("Is G tournament ?", nx.is_tournament(G))

When I run it in on Python 3.9.19 with NetworkX 3.2.1 in anaconda3 environment, I get the following results:

(base) C:\My Documents\Notes>python TourTest.py

DiGraph with 4 nodes and 4 edges

[(0, 1), (1, 2), (2, 3), (3, 0)]

Is G tournament ? False

DiGraph with 4 nodes and 3 edges

[(0, 1), (1, 2), (2, 3)]

Is G tournament ? False

DiGraph with 3 nodes and 3 edges

[(0, 1), (1, 2), (2, 0)]

Is G tournament ? True

DiGraph with 4 nodes and 3 edges

[(0, 1), (1, 2), (2, 3)]

Is G tournament ? False

DiGraph with 4 nodes and 4 edges

[(0, 1), (1, 2), (2, 3), (3, 0)]

Is G tournament ? False

(base) C:\My Documents\Notes>

Please, explain to me what is wrong with this picture, as my understanding is that there must be a bug in the is_tournament() function. I have not seen any mentions of the size limitations on tournament graphs (3 nodes and edges OK, but 4 not acceptable ?)

Regards,

E.Z. Polch

Aug 26, 2024, 3:38:51 PMAug 26

to networkx...@googlegroups.com

Dear Ewaryst

By definition from the official documentation (as well as the definition from Wikipedia)

A tournament is a directed graph, with neither self-loops nor multi-edges, in which there is exactly one directed edge joining each pair of distinct nodes.

I don't see anything wrong with your example. In your original example

G = nx.DiGraph([(0, 1), (1, 2), (2, 3), (3,0)])

G is not a tournament because there is no directed edge between 0 and 2. You can use the function nx.draw(G) to visualize G and observe that as well.

On the other hand, if

G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])

then G is a tournament.

I hope this helps.

Best wishes, Tung

--

You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/4dc83027-bdd6-4cf2-8bd1-aff378072be6n%40googlegroups.com.

Tung T. Nguyen, Ph.D

Email: tun...@uchicago.edu

Aug 26, 2024, 4:08:40 PMAug 26

to networkx...@googlegroups.com

According to the networkx docs on Tournament Graphs (with a further link to wikipedia) a tournament graph is a complete oriented graph -- meaning a DiGraph with all pairs of nodes connected in one (and only one) orientation. So, moving from 3 nodes to 4 nodes to maintain a tournament graph, we need to add edges from the new node to each of the other nodes -- those edges can be in either direction.

import networkx as nx

G = nx.DiGraph([(0, 1), (1, 2), (2, 0)])

nx.is_tournament(G) # -> True

G.add_node(3)

nx.is_tournament(G) # -> False

G.add_edges_from([(3, n) for n in range(3)])nx.is_tournament(G) # -> True

Aug 26, 2024, 4:48:02 PMAug 26

to networkx-discuss

Thank you very much, Tung, for pointing out my misunderstanding. I missed the part of definition about edges joining EACH pair of distinct nodes. So in my example, I was missing not only (0,2) edge, but also (1,3), before the graph becomes tournament.

This restriction makes it quite difficult to apply tournament graph functionality in my application (I'd need to generate a lot of additional edges to make my original graph tournament). This brings up the question of whether the search for Hamiltonian paths in non-tournament graphs will be available in NetworkX (or under what conditions it is theoretically possible)?

This restriction makes it quite difficult to apply tournament graph functionality in my application (I'd need to generate a lot of additional edges to make my original graph tournament). This brings up the question of whether the search for Hamiltonian paths in non-tournament graphs will be available in NetworkX (or under what conditions it is theoretically possible)?

Regards,

E.Z.

Aug 26, 2024, 7:02:40 PMAug 26

to networkx...@googlegroups.com

See the travelling_salesman_problem (and ask to visit all nodes)

Aug 27, 2024, 1:39:40 PMAug 27

to networkx-discuss

Thank you very much, Dan, for your pointer. It helped me steer in the right direction and find alternative solution to my problem: brute-force use of simple paths with their length selection as a filter.

Thank you both gentlemen for your patience with a guy who doesn't do his homework first, before using tools outside his field of expertise ;-)

Best Regards,

E.Z.

Aug 28, 2024, 1:58:22 AMAug 28

to networkx...@googlegroups.com

On Mon, 26 Aug 2024, 22:48 'Ewaryst Polch' via networkx-discuss, <networkx...@googlegroups.com> wrote:

Thank you very much, Tung, for pointing out my misunderstanding. I missed the part of definition about edges joining EACH pair of distinct nodes. So in my example, I was missing not only (0,2) edge, but also (1,3), before the graph becomes tournament.

This restriction makes it quite difficult to apply tournament graph functionality in my application (I'd need to generate a lot of additional edges to make my original graph tournament). This brings up the question of whether the search for Hamiltonian paths in non-tournament graphs will be available in NetworkX (or under what conditions it is theoretically possible)?

You can find theorems on the conditions under the Bondy–Chvátal theorem heading: https://en.wikipedia.org/wiki/Hamiltonian_path

As for algorithms, the TSP is probably what you want:

Although it won't guarantee it is Hamiltonian, but if such a path exists, it will hopefully find it.

/David

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/0269755a-1a9e-48d8-9f30-c7569a2409dan%40googlegroups.com.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu