# Hierholzer-Algo+Eulerweg



## jakaj (22. Dez 2009)

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 (22. Dez 2009)

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


----------



## jakaj (22. Dez 2009)

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 (22. Dez 2009)

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


----------



## jakaj (22. Dez 2009)

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 (22. Dez 2009)

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 (22. Dez 2009)

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 (22. Dez 2009)

Ø 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 (22. Dez 2009)

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


----------

