0

I'm trying to sort simple list in domino style. Looping is guarranteed, but no libraries can make it. Tried to draw polygons from this using like edges, but although solution is not ambigous the plots intersects each other.

pls
Out[1293]: 
[[10464, 27071],
 [22358, 15839],
 [10464, 24781],
 [24781, 22358],
 [19888, 27071],
 [30361, 19784],
 [19784, 19888],
 [30361, 15839]]

Proper ordering is: [30361,19784,19888,27071,10464,24781,22358,15839] Tried this:

import networkx as nx
 
G = nx.DiGraph() 
 G.add_edges_from(pls)       
 nx.draw(G.edges)        
 pol = list(nx.topological_sort(G))

but this sort returned: [30361, 19784, 19888, 10464, 24781, 22358, 15839, 27071] which is wrong. Some web algorithm not work [Sorting tuples in Python like dominoes/ finding vertex connectivity]

I tried some lists and doing this now... maybe someone could help me, because am so tired...

Olivier
  • 13,283
  • 1
  • 8
  • 24
Peter.k
  • 1,475
  • 23
  • 40
  • 1
    Are you allowed to flip the direction of edges? If not, the `[10464, 27071]` and `[19888, 27071]` edges conflict, so that would be a typo. You're looking for an [Eulerian path](https://stackoverflow.com/questions/17467228/looking-for-algorithm-finding-euler-path) on either a directed graph (if edges can't be flipped) or undirected graph (if they can be flipped). – kcsquared Feb 11 '22 at 07:24
  • They must be flipped - no other way to work. You see, there's only one path - each points have it's neighbor in other "element". They are like lines, and paired points are like nodes - creates a polygon. I used directed graph of `networkx`, but it's working dufferently - maybe I don't understand something. Undirected graph doesn;t work with this function of `topological_sort`. Where's Eulerian path? Which library? – Peter.k Feb 11 '22 at 07:35
  • 1
    https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.euler.eulerian_path.html – Stef Feb 11 '22 at 07:42
  • I think this work! `list(nx.eulerian_circuit(G))` when change DiGraph to Graph. Good sugestion. Thank you! – Peter.k Feb 11 '22 at 07:47

0 Answers0