Een Euleriaans circuit in een Euleriaanse graaf (i.e. een graaf waarin het aantal inkomende bogen gelijk is aan het aantal uitgaande voor elke top) is een cykel die alle bogen van de graaf bevat. Er moet dus met andere woorden een pad bepaald worden in de graaf die elke boog precies eenmaal aandoet en start en eindigt in dezelfde top.

Een Euleriaans circuit in een graaf is niet uniek. Zo is het circuit afhankelijk van de starttop, en kan er onderweg een andere boog worden gekozen om eerst aan te doen. Bij de implementatie van dit algoritme is het voldoende dat je één van de Euleriaanse cykels geeft.

Voorbeeld

Bovenstaande graaf is Euleriaans: het aantal inkomende bogen is in elke top gelijk aan het aantal uitgaande bogen. We kunnen in deze graaf dus een Euleriaans circuit bepalen. We nemen als starttop voor ons circuit een willekeurige top, bijvoorbeeld 1. Een mogelijk Euleriaans circuit in de graaf is dan gegeven door [1, 2, 3, 6, 5, 4, 2, 5, 3, 1]. Merk op dat ook [1, 2, 5, 3, 6, 5, 4, 2, 3, 1] een Euleriaans circuit is met starttop 1.

Het bepalen van een Euleriaans circuit kan op de volgende manier gebeuren:

// find start of eulerian cycle
start = random node
// initialize eulerian cycle with start node
euler = [start]
// initialize set of nodes in current cycle with more unused outgoing edges
nodes = {start}
// continue until all edges have been included in the cycle
while (nodes not empty) {
  // take any node v in current cycle with unused outgoing edges
  v = nodes.iterator().next()
  // initialize empty walk
  walk = []
  // add nodes to walk
  u = v
  while (node u has unused outgoing edges) {
    // take next unused outgoing edge
    e = next unused outgoing edge from u
    // check if all edges are used now
    if(u has no more unused edges){
      nodes.remove(u)
    }
    // move to destination of edge and add to walk
    u = e.destination
    walk.add(u)
    // add u to queue if it has unused outgoing edges
    if(u has unused edges){
      nodes.add(u)
    }
  }
  // insert new walk from v in eulerian cycle
  euler.insert(v, walk)
}

Opgave

Implementeer dit algoritme in een Python-functie create_circuit die een gerichte multigraaf als parameter meekrijgt. Deze methode moet een object van het type Walk teruggeven die de bezochte toppen, in juiste volgorde bevat.

We maken bij deze oefening gebruik van een eenvoudige grafenbibliotheek graphlib. De API van de deze bibliotheek vind je hier¹. Neem eerst en vooral eens de API en de bibliotheek zelf door en stel eventueel vragen hierover voor je begint te programmeren.

Belangrijke opmerking: om met de grafenbibliotheek te kunnen werken in PyCharm moet je het bestand graph_library.py² toevoegen aan dezelfde directory als waarin je ze gebruikt. Dan kun je ze gebruiken door ze te importeren met

from graph_library import *

Dit import statement mag wel niet mee ingediend worden op dodona.

Voorbeeld

>>> graph = directed_multigraph_from_dict({1: [2], 2: [3, 5], 3 : [1, 6], 4: [2], 5: [3, 4], 6: [5]})
>>> create_circuit(graph)
Walk(['Node(1)', 'Node(2)', 'Node(3)', 'Node(6)', 'Node(5)', 'Node(4)', 'Node(2)', 'Node(5)', 'Node(3)', 'Node(1)'])