I've been trying sort the path of a graph.

For example, I have the following list in python.

graph = [
  [4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [1, 0], [0, 2], [4, 1]
]

The result needs to be,

graph = [
  [0, 2], [2, 5], [5, 7], [7, 3], [3, 8], [8, 6], [6, 4], [4, 1], [1, 0]
]

0 -> 2 -> 5 -> 7 -> 3 -> 8 -> 6 -> 4 -> 1 -> 0

The premise is that the path begins with an edge whose initial value is zero (0) and ends with an edge whose last element is also zero.

Here is another example:

graph = [
  [0, 4], [4, 6], [8, 3], [3, 7], [5, 2], [2, 1], [1, 0], [7, 6], [5, 8]
]

The result needs to be:

graph = [
  [0, 1], [1, 2], [2, 5], [5, 8], [8, 3], [3, 7], [7, 6], [6, 4], [4, 0]
]

0 -> 1 -> 2 -> 5 -> 8 -> 3 -> 7 -> 6 -> 4 -> 0

The direction doesn't matter.

I started with this code.

def sort_graph(graph):
  sorted_graph = []
  for edge in graph:
    if edge[0] == 0:
      sorted_graph.append(edge)
  for edge in graph:
    if edge[0] != 0:
      sorted_graph.append(edge)
  return sorted_graph

but I'm not sure where to go from here.

CodePudding user response：

For each node in the cycle, keep track of its two neighbors. You can then walk through these neighbors to produce an ordering of the nodes. Once you've reached a node where both neighbors have already been visited, you're done.

neighbors = {}
for fst, snd in graph:
    neighbors.setdefault(fst, []).append(snd)
    neighbors.setdefault(snd, []).append(fst)

seen_both_neighbors = False
current = 0
path = []
seen = set()
while not seen_both_neighbors:
    path.append(current)
    fst, snd = neighbors[current]

    if fst not in seen:
        seen.add(current)
        current = fst
    elif snd not in seen:
        seen.add(current)
        current = snd
    else:
        seen_both_neighbors = True
    
result = list(map(list, zip(path, path[1:]   [path[0]])))
print(result)

For both of your examples, this produces the correct answer down to ordering.

CodePudding user response：

That was a fun problem to solve! Here's my idea for the approach:

1. Find all pairs (forward and backward)
2. Create a lookup table to easily navigate them
3. Start at 0, iterate through and remove nodes you've already visited

from itertools import chain
import random

graph = [
  [4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [1, 0], [0, 2], [4, 1]
]

# find all pairs independent of their direction
all_pairs = [*graph, *([t, f] for f, t in graph)]

# find all nodes
nodes = set(chain(*all_pairs))

# create a lookup dictionary for each point to show where you could go to
lookup = {node: {to_ for (from_, to_) in all_pairs if from_ == node} for node in nodes}


# simple solution - take a random path
from_ = 0
to_ = None

sorted_graph = []
while to_ != 0:
    # select a random next point
    to_ = random.choice(list(lookup[from_]))
    
    # make sure to delete it so it doesn't get used again
    lookup[from_].remove(to_)
    lookup[to_].remove(from_)
    
    # add to output
    sorted_graph.append((from_, to_))
    
    # tick one step forward
    from_ = to_

print(sorted_graph)

CodePudding user response：

If you're not restricted by dependency, networkx has a method that finds cycles.

import networkx as nx
graph = [
  [4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [1, 0], [0, 2], [4, 1]
]

# build a graph object
G = nx.Graph(graph)
# find a cycle starting from node 0
nx.find_cycle(G, source=0)
# [(0, 1), (1, 4), (4, 6), (6, 8), (8, 3), (3, 7), (7, 5), (5, 2), (2, 0)]

Source

CodePudding user response：

You could also implement cycle,as below:

def cycle(vec):
    result = [vec[0]]
    s = vec[1:]
    index = 0
    while s:
        if result[-1][0] == 0: 
            start = index
        for i,v in enumerate(s):
            if result[-1][1] in v:
                del s[i]
                result.append(v if v[0] == result[-1][1] else v[::-1])
                break
        index  = 1
    return result[start:]   result[:start]

cycle(graph)
 [[0, 1], [1, 4], [4, 6], [6, 8], [8, 3], [3, 7], [7, 5], [5, 2], [2, 0]]