ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 25 Sep 2024 14:08:31 +0200Error while computing gomory hu tree of graph using LPhttps://ask.sagemath.org/question/79320/error-while-computing-gomory-hu-tree-of-graph-using-lp/Hello,
I have an issue with the Gomory Hu tree computation and hope that someone can help me.
I load a graph and pass it to the gomory hu tree computation function using the algorithm „LP“, after around 10 seconds I get the following error and the computation aborts.
Traceback (most recent call last):
File ".../treewidth-playground/main.py", line 13, in <module>
hu = graph.gomory_hu_tree(algorithm="LP")
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/.../anaconda3/envs/sage2/lib/python3.11/site-packages/sage/graphs/graph.py", line 8697, in gomory_hu_tree
g = self._gomory_hu_tree(frozenset(self.vertex_iterator()), algorithm=algorithm)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
File "/home/.../anaconda3/envs/sage2/lib/python3.11/site-packages/sage/graphs/graph.py", line 8579, in _gomory_hu_tree
for uu, vv, capacity in edges:
^^^^^^^^^^^^^^^^
ValueError: not enough values to unpack (expected 3, got 2)
an executable example can be found here under the tag „Sage_question_01“:
https://gitlab.com/Telijas/treewidth-playground/-/blob/Sage_question_01/main.py?ref_type=tags
The applications basically consists of loading the graph and applying the algorithm:
import load.file_loader as file_loader
import processing.process
from sage.all import *
# file_name = "./resources/USA-road-d.NY.gr"
file_name = "./resources/AProVE07-03.gaifman.gr"
graph = file_loader.load(file_name)
print("Vertices found:", graph.order(), "and edges:", graph.size())
print("Start computation of gomory hu")
hu = graph.gomory_hu_tree(algorithm="LP")
print("Done computation of gomory hu")
print("Done")TelijasWed, 25 Sep 2024 14:08:31 +0200https://ask.sagemath.org/question/79320/Find all cycles in an undirected graphhttps://ask.sagemath.org/question/69318/find-all-cycles-in-an-undirected-graph/For **directed** graphs, we have a built-in command `all_simple_cycles` to search for specific length cycles or all cycles. However, it is indeed strange that there is no readily available command for undirected graphs. Although, we can convert an undirected graph into a directed graph by assigning two directions to each edge. For example:
g = graphs.CompleteGraph(4).to_directed();
all_cycles=g.all_simple_cycles()
print(all_cycles)
`[[0, 1, 0], [0, 2, 0], [0, 3, 0], [1, 2, 1], [1, 3, 1], [2, 3, 2], [0, 1, 2, 0], [0, 1, 3, 0], [0, 2, 1, 0], [0, 2, 3, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 2, 3, 1], [1, 3, 2, 1]]`
allcycles = []
for array in all_dcycles:
if len(array)>=4:
reversed_array = array[::-1]
if reversed_array not in allcycles:
allcycles.append(array)
print(allcycles)
`[[0, 2, 1, 0], [0, 3, 1, 0], [0, 3, 2, 0], [1, 3, 2, 1], [0, 3, 2, 1, 0], [0, 2, 3, 1, 0], [0, 3, 1, 2, 0]]`
Reversing lists and eliminating all 2-cycles seems tedious. Does SageMath provide a direct command for undirected graphs to find all cycles or cycles of a specific length? It's somewhat similar to Mathematica's `FindCycle` (`FindCycle[CompleteGraph[4], Infinity, All]`).lichengWed, 21 Jun 2023 10:21:09 +0200https://ask.sagemath.org/question/69318/The function crossing_number runs too slowly?https://ask.sagemath.org/question/63863/the-function-crossing_number-runs-too-slowly/In graph theory, the crossing number *cr(G)* of a graph *G* is the lowest number of edge crossings of a plane drawing of the graph *G*. In general, determining the crossing number of a graph is hard. However, for graphs with a small number of vertices and a small number of edges, some efficient procedures exist to compute them.
The *exact* and **non-heuristic** programs that I know of are the following:
- sagemath
- web crossing number (http://crossings.uos.de/) #Recent login is not available, the website may be under maintenance, or maybe not to provide services in the future.
- [OGDF](https://ogdf.uos.de/) (that is a self-contained C++ library for graph algorithms, in particular for (but not restricted to) automatic graph drawing.)
I see an example of mathoverflow from 10 years ago, which is to compute the cross number of the Grötzsch graph.
- [cross number of the Grötzsch graph](https://mathoverflow.net/questions/94282/crossing-number-of-the-gr%c3%b6tzsch-graph)
Jamie J. Taylor says in the answer that OGDF can be used. But we don't see the corresponding code. I know that Sagemath has the crossing_number, Unfortunately, it may be too slow.
G = graphs.GrotzschGraph()
G.crossing_number()
It took me about 12 hours, and I haven't gotten a result yet. Perhaps there is some way to improve it?lichengWed, 31 Aug 2022 03:28:51 +0200https://ask.sagemath.org/question/63863/