Fastest algorithm for cyclic linked list builder

Question

I have two questions:

1) What is the fastest algorithm for placing this list in a "connecting" order?
2) Is this an existing problem / algorithm and what name does it have?

The nodes are always connected in a circular way, so my initial identifier does not matter.

Given this list:

id node1 node2 A 4 9 B 6 1 C 1 3 D 3 10 E 7 2 F 4 2 G 9 8 H 10 5 I 7 5 J 6 8 

node1 and node2 are not in a specific order, so id A can be 4 - 9, as well as 9 - 4.

The output should be like this (it doesn't matter if it starts with A while the output is a chain).

 node ids: 4 - 9 - 8 - 6 - 1 - 3 - 10 - 5 - 7 - 2 - 4 ids: AGJBCDHIEF 

(I write my code in C #, but pseudocode in any language will do)

Answer 1

You can do it as follows:

 static IEnumerable<Edge<T>> OrderEdges<T>(this IEnumerable<Edge<T>> edges) where T : IEquatable<T> { Debug.Assert(edges.Any()); var map = new Dictionary<T, Edge<T>>(); foreach (var e in edges) { if (map.ContainsKey(e.Node1)) { Debug.Assert(!map.ContainsKey(e.Node2)); map.Add(e.Node2, e); } else { map.Add(e.Node1, e); } } var current = edges.First(); var orderedEdges = new HashSet<Edge<T>>(); while (true) { orderedEdges.Add(current); yield return current; if (orderedEdges.Count == map.Count) break; var next = map[current.Node2]; current = orderedEdges.Contains(next) ? map[current.Node1] : next; } } 

If the Edge<T> class is simple:

 class Edge<T> where T: IEquatable<T> { public T Node1 { get; } public T Node2 { get; } public string Name { get; } public Edge(string name, T node1, T node2) { Name = name; Node1 = node1; Node2 = node2; } public override string ToString() => Name; } 

If we run this little guy:

 var edges = new List<Edge<int>>() { new Edge<int>("A", 4, 9), new Edge<int>("B", 6, 1), new Edge<int>("C", 1, 3), new Edge<int>("D", 3, 10), new Edge<int>("E", 7, 2), new Edge<int>("F", 4, 2), new Edge<int>("G", 9, 8), new Edge<int>("H", 10, 5), new Edge<int>("I", 7, 5), new Edge<int>("J", 6, 8) }; Console.WriteLine(string.Join(" -> ", edges.OrderEdges())); 

We get the expected result:

 A -> G -> J -> B -> C -> D -> H -> I -> E -> F 

Note that this solution assumes the input is well-formed.

Answer 2

I believe that you are looking for the Euler path

Answer 3

I do not know if there is any named mathematical problem. Here is the pseudo code that solves the problem in the O (N) manner (complexity and memory usage).

1) Create an array (we assume that the nodes have unique identifiers from the range [0..N-1] and fill it with nodes (the node with the identifier should be placed at id)

2) select any Node and click it in a separate list (it will contain Node in a circular order). The last Node on this list will be called the processed Node.

3) iterations from 1 to N -1 at each step, select the neighbor that has not been processed by the processed Node. Click such an un-moved Node into a circular list. Continue the process

Note: checking the property “failed” can be performed using O (1). Just look where it is already in the circular list. It must be a neighbor of the last (processed) node

The main drawback is the assumption of such an algorithm - the existence of a unique Euler path.

Answer 4

Here is a sentence using a dictionary (hash table) for calculations.

I called the “cell” the sheet row contained in the question (but we don’t know your data structure).

O (n) seems to be, since dictionaries provide O (1) extraction.

All this assumes that the source data is consistent with the problem (as I understand it, at least).

The code is in C # and commented out. Tell me if comments are not enough for an explanation.

 class Program { class Cell { public string Id { get; set; } public int Node1 { get; set; } public int Node2 { get; set; } public int Min { get { return Math.Min( Node1, Node2 ); } } public Cell( string name, int node1, int node2 ) { Id = name; Node1 = node1; Node2 = node2; } public override string ToString() { return Id + "(" + Node1.ToString() + "," + Node2.ToString() + ")"; } } static void Main( string[] args ) { var A = new Cell( "A", 4, 9 ); var B = new Cell( "B", 6, 1 ); var C = new Cell( "C", 1, 3 ); var D = new Cell( "D", 3, 10 ); var E = new Cell( "E", 7, 2 ); var F = new Cell( "F", 4, 2 ); var G = new Cell( "G", 9, 8 ); var H = new Cell( "H", 10, 5 ); var I = new Cell( "I", 7, 5 ); var J = new Cell( "J", 6, 8 ); var cells = new List<Cell>() { A, B, C, D, E, F, G, H, I, J }; // A dictionary to store the cells corresponding to each node values Dictionary<int, List<Cell>> dict = new Dictionary<int, List<Cell>>(); // Add all the cells to the dictionary foreach ( var cell in cells ) AddCell( dict, cell ); // Start with arbitrary first cell and remove it from the dictionary var currentCell = GetCell( dict, A.Node1 ); RemoveCell( dict, currentCell ); // The result is a list of cells initialized with the first cell var result = new List<Cell>() { currentCell }; // Calculation loop bool doContinue = true; while ( doContinue ) { // Tries to get a next cell from the node1 of current cell... var nextCell = GetCell( dict, currentCell.Node1 ); // ... or if not found, tries to get it from node2 if ( nextCell == null ) nextCell = GetCell( dict, currentCell.Node2 ); if ( nextCell == null ) // If not found, we stop { doContinue = false; } else // If found { // Add the next cell to the result result.Add( nextCell ); // Remove the cell RemoveCell( dict, nextCell ); } // The next cell becomes the current cell currentCell = nextCell; } } // Adding a cell puts the cell against its two nodes values static void AddCell( Dictionary<int, List<Cell>> dict, Cell cell ) { List<Cell> cells = null; if ( dict.TryGetValue( cell.Node1, out cells ) == false ) { cells = new List<Cell>(); dict[cell.Node1] = cells; } cells.Add( cell ); if ( dict.TryGetValue( cell.Node2, out cells ) == false ) { cells = new List<Cell>(); dict[cell.Node2] = cells; } cells.Add( cell ); } // Gets a cell from a node value static Cell GetCell( Dictionary<int, List<Cell>> dict, int node ) { var cell = null as Cell; var cells = dict[node]; if ( cells.Count > 0 ) cell = cells.First(); return cell; } // Removes a cell from the dictionary for both node1 and node2 entries. static void RemoveCell( Dictionary<int, List<Cell>> dict, Cell cell ) { dict[cell.Node1].Remove( cell ); dict[cell.Node2].Remove( cell ); } } 

Answer 5

The starting point is a list or array, for example:

  1 {A, 4, 9} 2 {B, 6, 1} 3 {C, 1, 3} 4 {D, 3,10} 5 {E, 7, 2} 6 {F, 4, 2} 7 {G, 9, 8} 8 {H,10, 5} 9 {I, 7, 5} 10 {J, 6, 8} 

If we can change this to a list or array, for example:

  1 {C, 1, 3} 2 {F, 2, 4} (nodes swapped) 3 {D, 3,10} 4 {A, 4, 9} 5 {I, 5, 7} (nodes swapped) 6 {B, 6, 1} 7 {E, 7, 2} 8 {J, 8, 6} (nodes swapped) 9 {G, 9, 8} 10 {H,10, 5} 

which is ordered by node1, then we can read this list or array as a linked list:

 start with item 1: {C, 1, 3} read node2: 3 skip to item 3: {D, 3,10} read node2: 10 skip to item 10: {H,10, 5} ... skip to item 6: {B, 6, 1} read node2: 1 end of list result: CDHIEFAGJB 

Creating this second version of the list can be done in place by replacing items in the list or by copying items to a new list (if you have a space).

The only thing you need to pay attention to is that sometimes you have to change both nodes. When re-ordering on the spot, it may look like this:

 look at item 1: {A, 4, 9} if item 4 has a node1 different from 4, swap item 1 and 4 else, change item 1 to {A, 9, 4} and swap item 1 and 9 (-> item 1 and 4 swapped) while current item is already in-place, skip to next (-> stay at item 1) look at new item 1: {D, 3,10} if item 3 has a node1 different from 3, swap item 1 and 3 else, change item 1 to {D,10, 3} and swap item 1 and 10 (-> item 1 and 3 swapped) while current item is already in-place, skip to next (-> item 1 is now {C, 1, 3}, so skip to item 2) ... 

When creating a new list or array, this should be even simpler:

 look at item 1: {A, 4, 9} if new list has no item 4, copy item 1 as item 4 to the new list else, change item 1 to {A, 9, 4} and copy as item 9 to the new list move to next item 

As you can see, there is no need to iterate over the list several times; each element is replaced or copied once, and its purpose is determined by its node1 or node2.

---

UPDATE

I just realized that the number of steps for ordering items can be (much) more than described above. If, for example, you start by moving {A, 4.8} to location 4 and {B, 5.9} to location 5, and then you come across {C, 4,5}, you get stuck. Then you have to swap {C, 4,5} with one of the other two elements, swap in another element and move them into place. This new place can already be taken, and so on, so there would be no way to find out which of the two options is the lesser evil. In the worst case, the number of swaps would be close to N ² .

---

UPDATE 2

The above problem, of course, can be solved by storing the items in a doubly linked list. When you come across, for example, {A, 4,8}, you store {A, 8} as element 4 and {A, 4} as element 8, and then for {B, 5,9} you store {B, 9 } element 5 and {B, 5} as point 9, and then for {C, 4,5}, you add to the already saved elements, so that element 4 becomes {A, 8, C, 5}, and element 5 becomes {B, 9, C, 4}. Then you can cross the doubly linked list in both directions. This will increase the work that needs to be done and the space used, but it is still linear for the number of items in the list.