Durchläufe durch Graphen SS12

Aus ProgrammingWiki

Archivierte Version vom 2012-05-10T20:16:17+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Wiederholung
2 Unterscheidung von Durchlaufproblemen
- 2.1 Durchlauf aller Knoten
- 2.2 Durchlauf aller Kanten
3 Tiefendurchlauf/ -suche
4 Breitendurchlauf/ -suche
5 Iterative Tiefensuche
6 Anwendung/ weiterführende Themen
7 Java-Test

Text vor TOC, evtl. Intro etc.

Note: Durchlauf (traversal) $\neq$ Suche (search)!

Wiederholung

Bezug auf:

Graphenrepräsentation: Arten und Darstellung \rightarrow abhängig!

Sortierte Folgen: Bäume und Preorder

w. Datenstrukturen: Stack und Queue

Unterscheidung von Durchlaufproblemen

Durchlauf aller Knoten

Durchlauf aller Kanten

Tiefendurchlauf/ -suche

Breitendurchlauf/ -suche

Iterative Tiefensuche

Anwendung/ weiterführende Themen

Starke Zusammenhangskomponenten

Topologisches Sortieren

TSP und CPP

Java-Test

//note to self: code verstecken funktioniert auch innerhalb methoden
//note to self2: applet: http://www.cosc.canterbury.ac.nz/mukundan/dsal/GraphAppl.html meh~
//note to self2.1: dfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/DFSApplet.html
//note to self2.2: bfs-applet: http://www.lupinho.net/lupinho.de/gishur/html/BFSApplet.html
//w00t~
//note to self3: eu/hm-applets zum knobeln: http://www.cut-the-knot.org/Curriculum/Combinatorics/GraphPractice.shtml

public Object Stack()
{
   int groesse = 20;
   int[] elemente = new int[groesse];
   int top = -1;

   public void push(int j)
      {elemente[++top] = j;}

   public int pop()
      {return elemente[top--];}

   public int peek()
      {return elemente[top];}

   public boolean istLeer()
      {return (top == -1);}
   
   return this;

}

public Object Queue()
{
   int[] elemente = new int[0];
   int top;  
   int groesse = elemente.length;
    
   public boolean istLeer()
   {
      groesse = elemente.length;
      return groesse == 0;
   }
    
   public int peek()
   {
      top = elemente[0];
      return top;
   }
    
   public void enqueue(int element)
   {
      groesse = elemente.length;
      int[] neu = new int[groesse +1];
    	
      for (int i=0; i<=groesse-1; i++)
         neu[i] = elemente[i];
    	
      neu[groesse] = element;
      elemente = neu;
      top = elemente[0];
   }
    
   public int dequeue()
   {
      top = elemente[0];
      groesse = elemente.length;
      int[] neu = new int[groesse-1];
    	
      for(int i = 0; i < groesse-1; i++)
         neu[i] = elemente[i+1];
    	
      elemente = neu;
      return top;
   }

   return this; 
}

public Object Vertex (char label)
{
   char label = label;
   boolean bereitsBesucht = false;
   String farbe = "weiss";
   int gefunden = -1;
   int abgearbeitet = -1;
   char vorgaenger = '#';

   return this;
}

public Object Graph(int max, String a)
{
   int knotenanzahl = max;
   Object[] knotenliste = new Object[knotenanzahl];
   int knoten = 0;
   int[][] adjazenzMatrix = new int[knotenanzahl+1][knotenanzahl+1];
   String art = a;
   int zeit = 0;

   Object stacky = Stack();
   Object queuey = Queue();
  
   Object topologie = Stack();

   for(int i =0; i<=knotenanzahl; i++)
      for(int j=0; j<=knotenanzahl; j++)
         adjazenzMatrix[i][j] = 0;
   
   public void addEdge(int start, int end)
   {
      if(this.art == "ungerichtet"){
         adjazenzMatrix[start-1][end-1] = 1;
         adjazenzMatrix[end-1][start-1] = 1;
      }

      if(this.art == "gerichtet")
         adjazenzMatrix[start-1][end-1] = 1;
   }

   public void addVertex(char lab)
   {
      knotenliste[knoten++] = Vertex(lab);
   }

   public void displayVertex(int v)
   {
      System.out.print(knotenliste[v].label);
   }


public void displayVertexEX(int v)
   {
      System.out.print("Label: " + knotenliste[v].label + " ");
      System.out.print("Farbe: " + knotenliste[v].farbe + " ");
      System.out.print("Voriges Element: " + knotenliste[v].vorgaenger + " ");
      System.out.print("Wann entdeckt: " + knotenliste[v].gefunden + " ");
      System.out.print("Wann geschlossen: " + knotenliste[v].abgearbeitet + " ");
   }


   public void dfs()
   {
      System.out.print("\n\nDFS-Durchlaufordnung: ");

      knotenliste[0].bereitsBesucht=true;
      displayVertex(0);
      stacky.push(0);

      while (!stacky.istLeer())
      {
         int v = getAdjUnvisitedVertex(stacky.peek());
         if(v == -1) stacky.pop();
         else 
         {
            knotenliste[v].bereitsBesucht = true;
            displayVertex(v);
            stacky.push(v);
         }
      }

      for(int j=0; j<knoten; j++)
         knotenliste[j].bereitsBesucht = false;
   }
public void dfsrek(int start)     //indizierung gleich natuerlicher stelle bei eingabe
   	{       start=start-1;
		System.out.println("\n\nDFS-Durchlaufordnung(rekursiv):\n\n");
		
     		for(int j=0; j<knoten; j++)				//anfang leer init
			{						
			knotenliste[j].farbe="weiss";			
      			knotenliste[j].vorgaenger='#';			
			}
		zeit = 0;						//ende leer init
		
     		for(int j=start; j<knoten; j++)										
			{
			if (knotenliste[j].farbe=="weiss")
				
      				dfsvisit(j);	
			}
                if (start!=0)
                        for(int j=0; j<start; j++)										
			{
			if (knotenliste[j].farbe=="weiss")
				
      				dfsvisit(j);
			};

		for(int j=0; j<knoten; j++)				//ausgabe endzustand
			{
			displayVertexEX(j);
                        System.out.println();
      			};
			System.out.println("\n\n");

	}

public void dfsvisit(int u)    
	{       
                System.out.println(" "+knotenliste[u].label+" ");
		knotenliste[u].farbe="grau";
		zeit++;
		knotenliste[u].gefunden=zeit;
		for(int j=0; j<knoten; j++)
        		if(adjazenzMatrix[u][j] == 1 && knotenliste[j].farbe=="weiss")
				{
				knotenliste[j].vorgaenger=knotenliste[u].label;
                                
				dfsvisit(j);
				};
           	knotenliste[u].farbe="schwarz";
		zeit++;
		knotenliste[u].abgearbeitet=zeit;
                topologie.push(u+1);
	}

public void displayTopo()
   {  System.out.println("Topologisch sortiert: ");
      for(int j=0; j<knoten ; j++)
         {
         System.out.print(topologie.peek() +" ");
         topologie.pop();
         
         }
   }

   public void bfs()
   {
      System.out.print("\n\nBFS-Durchlaufordnung: ");
	  
      knotenliste[0].bereitsBesucht = true;
      displayVertex(0);
      queuey.enqueue(0);

      while( !queuey.istLeer() )
      {
         int v = getAdjUnvisitedVertex( queuey.peek() );
         if(v == -1)
            queuey.dequeue();
         else
         {
            knotenliste[v].bereitsBesucht = true;
            displayVertex(v);
            queuey.enqueue(v);
         }
      }
      
      for(int j=0; j<knoten; j++)
          knotenliste[j].bereitsBesucht = false;
    }
   

   public int getAdjUnvisitedVertex(int v)
   {
      for(int j=0; j<knoten; j++)
        if(adjazenzMatrix[v][j] == 1 && knotenliste[j].bereitsBesucht==false)
           return j;
      return -1;
   }

   public void zeigeAdjMatrix()
   {  
      System.out.println("\nAdjazenzmatrix:");

      Object[][] showMat = new Object[knotenanzahl+1][knotenanzahl+1];

      showMat[0][0] = ' ' ; 

      for(int i=0; i<knotenanzahl; i++){
         for(int row=1; row<=knotenanzahl; row++){
            showMat[0][row] = this.knotenliste[row-1].label; 
            showMat[i+1][row] = this.adjazenzMatrix[i][row-1];}

         for(int col=1; col<=knotenanzahl; col++){
            showMat[col][0] = this.knotenliste[col-1].label;
            showMat[col][i+1] = this.adjazenzMatrix[col-1][i];}}

      for (int k = 0; k<=knotenanzahl; ++k) {
        for (int l = 0; l<=knotenanzahl; ++l) {
           System.out.print(showMat[k][l] + "\t");}
        System.out.println("");}
   }

   public void pruefeGrad()
   {
	   System.out.println("\n\nEin- und Ausgangsgrade:");
	   
	   int countIndegree=0, countOutdegree=0;
	   int[] In = new int[knotenanzahl];
	   int[] Out = new int[knotenanzahl];
		  
	   for(int i=0; i<knotenanzahl; i++){
		   for(int j=0; j<knotenanzahl;j++){
			   if (adjazenzMatrix[j][i] ==1)
				   countIndegree++;
			   if(adjazenzMatrix[i][j] == 1)
				   countOutdegree++;
		    	}
			   
		   In[i]=countIndegree;
		   Out[i]=countOutdegree;
		   System.out.print("Eingangsgrad von Knoten " + knotenliste[i].label + ": " + countIndegree + "\t");
		   System.out.print("Ausgangsgrad von Knoten " + knotenliste[i].label + ": " + countOutdegree + "\n");
		    	  
		   countIndegree=0;
		   countOutdegree=0;
	   }	  
		     
	   int ungerade=0;
	   
	   for (int l=0; l<knotenanzahl; l++){
	      if(Out[l]%2 !=0)
	         ungerade++;
	      }
	   
	   System.out.println("\n--> Anzahl Knoten ungeraden Ausgangsgrades: " + ungerade);
	      
	   if(ungerade== 0)
		   System.out.println("==> Eulerkreis möglich!");
	   else if(ungerade==2)
		   System.out.println("==> Eulerpfad möglich!");
	   else 
		   System.out.println("==> Weder Eulerkreis noch -pfad möglich!");
	     
	   int test=0;
		  
	   for(int k=0; k<knotenanzahl; k++){
		   if((In[k] != 0) && (Out[k] != 0))
			   test++;}
				  
	   if(test==knotenanzahl)
		   System.out.println("==> Hamiltonpfad und/ oder -kreis möglich!");
	   else
		   System.out.println("==> Kein Hamiltonkreis, jedoch Hamiltonpfad möglich!");
   }
   
   return this;
}

//G1 von S.145
//zur differenzierung ungeeignet - bfs & dfs liefern gleiche ordnung!
//G aus PDF-09 besser!!
theGraph = Graph(6, "gerichtet");

theGraph.addVertex('A');    // 1  (start)
theGraph.addVertex('B');    // 2
theGraph.addVertex('C');    // 3
theGraph.addVertex('D');    // 4
theGraph.addVertex('E');    // 5
theGraph.addVertex('F');    // 6

theGraph.addEdge(1, 2);     // A-B
theGraph.addEdge(1, 4);     // A-D
theGraph.addEdge(1, 6);     // A-F

theGraph.addEdge(2, 3);     // B-C
theGraph.addEdge(2, 4);     // B-D

theGraph.addEdge(3, 4);     // C-D
theGraph.addEdge(3, 5);	    // C-E 
theGraph.addEdge(3, 6);	    // C-F 

theGraph.addEdge(4, 5);	    // D-E
theGraph.addEdge(4, 3);	    // D-C

theGraph.addEdge(5, 6);     // E-F

theGraph.zeigeAdjMatrix();

theGraph.dfs();


theGraph.dfsrek(1);

theGraph.bfs();

theGraph.pruefeGrad();

//funktioniert prinzipiell
/* TODO:
 * konstruktor mit parameterübergabe                         (x)
 * nutzereingabe optimieren (d.h. edge 1 = array-index 1)    (x)
 * adjazenzmatrix darstellen (mit rand)                      (x)
 * queue implementieren + bfs                                (x)
 * fallunterscheidung gerichtet-ungerichtet                  (x)
 * YAY~ :D
 * eulerprüfung(code) mit pfadangabe(pseudo)                 (~)
 * hamiltonprüfung(code) mit pfadangabe(pseudo)              (~)
 * DFS von beliebigem startknoten                            (~)
 * SCC                                                       ( )
*/

nikolaus = Graph(5, "ungerichtet");
nikolaus.addVertex('A');    // 1  (start)
nikolaus.addVertex('B');    // 2
nikolaus.addVertex('C');    // 3
nikolaus.addVertex('D');    // 4
nikolaus.addVertex('E');    // 5

nikolaus.addEdge(1, 2);     // A-B
nikolaus.addEdge(1, 3);     // A-D
nikolaus.addEdge(1, 4);     // A-F

nikolaus.addEdge(2, 3);     // B-C
nikolaus.addEdge(2, 4);     // B-D

nikolaus.addEdge(3, 4);     // C-D
nikolaus.addEdge(3, 5);	    // C-E 

nikolaus.addEdge(4, 5);	    // D-E

nikolaus.zeigeAdjMatrix();

nikolaus.pruefeGrad();

sachen = Graph(9,"gerichtet");
sachen.addVertex('A'); //1//Unterhose
sachen.addVertex('B'); //2//Hose
sachen.addVertex('C'); //3//Guertel
sachen.addVertex('D'); //4//Hemd
sachen.addVertex('E'); //5//Kravatte
sachen.addVertex('F'); //6//Jacket
sachen.addVertex('G'); //7//Socken
sachen.addVertex('H'); //8//Schuhe
sachen.addVertex('I'); //9//Uhr

sachen.addEdge(1,2);
sachen.addEdge(1,8);

sachen.addEdge(2,8);
sachen.addEdge(2,3);

sachen.addEdge(3,6);

sachen.addEdge(7,8);

sachen.addEdge(4,3);
sachen.addEdge(4,5);

sachen.addEdge(5,6);

sachen.dfsrek(1);

sachen.displayTopo();

<maxima> load(graphs)$ g: create_graph([1,2,3],[[1,2],[2,3],[1,3]])$ print_graph(g1); </maxima>