network 3.2.1 is_tournament() function bug

[Ewaryst Polch]

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

[Tung T. Nguyen]

Dear Ewaryst

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

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.tournament.is_tournament.html

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

Website: https://tungprime.github.io/

[Dan Schult]

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

[Ewaryst Polch]

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)?

Regards,

E.Z.

[Dan Schult]

See the travelling_salesman_problem (and ask to visit all nodes)

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem.html

[Ewaryst Polch]

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.

[David Menéndez Hurtado]

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:

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.traveling_salesman.traveling_salesman_problem.html

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.