Hierholzer-Algo+Eulerweg

[jakaj]

Hi.
Ich bin noch stark am Anfang aber hänge da schon fest
Also ich soll den mit dem Hierholzeralgo den Eulerweg ermitteln, da ich von dem Algo bisher nix gehört hatte, hab ich die gängigen Suchmaschinen Befragt und sogar einen Pseudocode gefunden.
Nur versteh ich gerad den Code irgendwie nicht

Den Code gibt es hier: HierholzerCode < Allgemeines

Was bedeutet der Pfeil nach links, also v <- v(1), L <- Ø
ich hab das bisher noch nie gesehen, wäre nett wenn mir jemand sagen könnte wie man das liest/spricht und was die Bedeuten...

mfg avaj

 

[Marco13]

Das ist einfach eine Zuweisung:
Vertex v = vertices.get(1); // v <- v(1)

 

[jakaj]

Dieses Vertex ist laut wiki eine Art Richtungsangabe, aber ich dachte das sei ein Code für einen ungerichteten Graphen...

Oder was genau macht Vertex?

 

[Marco13]

Ein Vertex hat nichts mit einer Richtung zu tun. "Vertex" ist das englische Wort für "Knoten" (in einem Graphen). Deswegen auch "v"

 

[jakaj]

AHHHHH
jetzt wird mir doch glaube einiges klarer
also Bedeutet v <- v(1) das er den nächsten Knoten sucht?
und was bedeutet L <- Ø? Ich weiß nicht mal genau was L ist, nur eine Variable?

 

[Landei]

Scheint zu funktionieren:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Graph<V> {
   Set<V> vertexes = new HashSet<V>();
   Map<V, Set<V>> edges = new HashMap<V,Set<V>>();

   public void addEdge(V v1, V v2) {
       vertexes.add(v1);
       vertexes.add(v2);
       Set<V> e1 = edges.get(v1);
       if(e1 == null) {
           e1 = new HashSet<V>();
           edges.put(v1,e1);
       }
       e1.add(v2);
       Set<V> e2 = edges.get(v2);
       if(e2 == null) {
           e2 = new HashSet<V>();
           edges.put(v2,e2);
       }
       e2.add(v1);
   }

   public void removeEdge(V v1, V v2) {
       Set<V> e1 = edges.get(v1);
       e1.remove(v2);
       if(e1.isEmpty()) {
           edges.remove(v1);
           vertexes.remove(v1);
       }
       Set<V> e2 = edges.get(v2);
       e2.remove(v1);
       if(e2.isEmpty()) {
           edges.remove(v2);
           vertexes.remove(v2);
       }
   }

   public Set<V> getNeighbors(V v) {
       return edges.get(v);
   }
}

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class Hierholzer {

    public static <V> List<V> getPath(Graph<V> graph) {
        List<V> odd = new ArrayList<V>();
        for(V v : graph.vertexes) {
            int grad = graph.getNeighbors(v).size();
            if (grad == 0) {
                throw new IllegalArgumentException("Isolated vertexes");
            }
            if (grad % 2 == 1) {
                odd.add(v);
            }
        }
        if(odd.size() > 2) {
            throw new IllegalArgumentException("More than two odd vertexes");
        }
        List<V> way = new ArrayList<V>();
        V from = odd.size() == 2 ? odd.get(0) : graph.vertexes.iterator().next();
        V to = odd.size() == 2 ? odd.get(1) : from;
        int insertPosition = 0;
        while(graph.edges.size() > 0) {
            List w = findWay(graph, from, to);
            way.addAll(insertPosition, w);
            for(int i = 0; i < way.size(); i++) {
                V v = way.get(i);
                if (graph.vertexes.contains(v)) {
                    from = v;
                    to = v;
                    insertPosition = i;
                    break;
                }
            }
        }
        return way;
    }

    private static <V> List<V> findWay(Graph<V> graph, V from, V to) {
        List<V> way = new ArrayList<V>();
        V current = from;
        do {
            way.add(current);
            Set<V> neighbors = graph.getNeighbors(current);
            V next = neighbors.iterator().next();
            graph.removeEdge(current, next);
            current = next;
        } while(current != to);
        if(!from.equals(to)) {
            way.add(to);
        }
        return way;
    }

    public static void main(String... args) {
        //Nikolaus-Haus
        Graph<String> g = new Graph<String>();
        g.addEdge("A","B");  g.addEdge("A","C");
        g.addEdge("B","C");  g.addEdge("B","D");
        g.addEdge("B","E");  g.addEdge("C","D");
        g.addEdge("C","E");  g.addEdge("D","E");
        System.out.println(getPath(g)); 
        //Ausgabe: [D, B, A, C, B, E, C, D, E]
    }
}

Statt irgendwas zu markieren, lösche ich Kanten und Vertizes einfach knallhart aus dem Graphen. Das gute Stück ist also am Ende leergezutscht.

[edit] Der Pseudocode-Algorithmus ist wirklich schlecht geschrieben, ich hab mich einfach an das grobe Rezept in Wikipedia gehalten.

 

[jakaj]

Sieht ja mal ganz nice aus

hätte da aber noch immer die Frage was L <- Ø bedeutet? bzw das L?

will das versuchen selber zu machen, nur finde ich den Pseudocode auch etwas komisch.
wär cool wenn einer nen einfacheren Pseudocode finden würde

Ansonsten DANKE euch beiden, die Musterlösung heb ich mir für evtl. spätere Fragen noch auf

 

[Landei]

Ø ist die leere Menge. L muss demnach ebenfalls eine Menge sein, was in einem Java-Programm meist als Set (HashSet, TreeSet, LinkedHashSet...) abgebildet wird, es gibt aber auch andere Möglichkeiten.

 

[jakaj]

Ahhh ok, na dann sollte jetzt relativ alles verständlich sein, ich schätze ich meld mich wieder wenn ich nicht weiter weiß.
Aber fürs erste ist mir geholfen.

Danke@alle