function varargout = Wegsuche(varargin)
% WEGSUCHE M-file for Wegsuche.fig
%      WEGSUCHE, by itself, creates a new WEGSUCHE or raises the existing
%      singleton*.
%
%      H = WEGSUCHE returns the handle to a new WEGSUCHE or the handle to
%      the existing singleton*.
%
%      WEGSUCHE('CALLBACK',hObject,eventData,handles,...) calls the local
%      function named CALLBACK in WEGSUCHE.M with the given input arguments.
%
%      WEGSUCHE('Property','Value',...) creates a new WEGSUCHE or raises the
%      existing singleton*.  Starting from the left, property value pairs are
%      applied to the GUI before Wegsuche_OpeningFcn gets called.  An
%      unrecognized property name or invalid value makes property application
%      stop.  All inputs are passed to Wegsuche_OpeningFcn via varargin.
%
%      *See GUI Options on GUIDE's Tools menu.  Choose "GUI allows only one
%      instance to run (singleton)".
%
% See also: GUIDE, GUIDATA, GUIHANDLES

% Edit the above text to modify the response to help Wegsuche

% Last Modified by GUIDE v2.5 28-Jul-2011 16:28:11

% Begin initialization code - DO NOT EDIT
gui_Singleton = 1;
gui_State = struct('gui_Name',       mfilename, ...
                   'gui_Singleton',  gui_Singleton, ...
                   'gui_OpeningFcn', @Wegsuche_OpeningFcn, ...
                   'gui_OutputFcn',  @Wegsuche_OutputFcn, ...
                   'gui_LayoutFcn',  [] , ...
                   'gui_Callback',   []);
if nargin && ischar(varargin{1})
    gui_State.gui_Callback = str2func(varargin{1});
end

if nargout
    [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
else
    gui_mainfcn(gui_State, varargin{:});
end
% End initialization code - DO NOT EDIT


% --- Executes just before Wegsuche is made visible.
function Wegsuche_OpeningFcn(hObject, eventdata, handles, varargin)
% This function has no output args, see OutputFcn.
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
% varargin   command line arguments to Wegsuche (see VARARGIN)

% Choose default command line output for Wegsuche
handles.output = hObject;

% Update handles structure
guidata(hObject, handles);

% UIWAIT makes Wegsuche wait for user response (see UIRESUME)
% uiwait(handles.figure1);


% --- Outputs from this function are returned to the command line.
function varargout = Wegsuche_OutputFcn(hObject, eventdata, handles) 
% varargout  cell array for returning output args (see VARARGOUT);
% hObject    handle to figure
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Get default command line output from handles structure
varargout{1} = handles.output;



function edit2_Callback(hObject, eventdata, handles)
% hObject    handle to edit2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit2 as text
%        str2double(get(hObject,'String')) returns contents of edit2 as a double


% --- Executes during object creation, after setting all properties.
function edit2_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end



function edit3_Callback(hObject, eventdata, handles)
% hObject    handle to edit3 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit3 as text
%        str2double(get(hObject,'String')) returns contents of edit3 as a double


% --- Executes during object creation, after setting all properties.
function edit3_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit3 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end



function edit4_Callback(hObject, eventdata, handles)
% hObject    handle to edit4 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit4 as text
%        str2double(get(hObject,'String')) returns contents of edit4 as a double


% --- Executes during object creation, after setting all properties.
function edit4_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit4 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end


% --- Executes on selection change in listbox1.
function listbox1_Callback(hObject, eventdata, handles)
% hObject    handle to listbox1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: contents = cellstr(get(hObject,'String')) returns listbox1 contents as cell array
%        contents{get(hObject,'Value')} returns selected item from listbox1


% --- Executes during object creation, after setting all properties.
function listbox1_CreateFcn(hObject, eventdata, handles)
% hObject    handle to listbox1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: listbox controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end

%============================================================
%           OK
%============================================================
% --- Executes on button press in pushbutton1.
function pushbutton1_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton1 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
string = get(handles.listbox1,'String');
start=get(handles.edit5,'String');
ziel=get(handles.edit6,'String');
if isValidNode(start)==false
    
elseif isempty(start)
    msgbox('Bitte geben Sie einen Knoten als Startpunkt der Wegsuche ein.');
elseif isempty(ziel)
    msgbox('Bitte geben Sie einen Knoten als Endpunkt der Wegsuche ein.');
else
    
    [m n] = size(string);
    kantenliste=[];
    for i=1:m
       str= regexpi(string(i,:),'->','split');
       a=regexpi(char(str(2)),':','split');
       kantenliste=[kantenliste;str2num(char(str(1))),str2num(char(a(1))),str2num(char(a(2)))];
    end
    [m n] = size(kantenliste);
    knotenanzahl=max([kantenliste(:,1);kantenliste(:,2)]);
    c=[];
    A=zeros(knotenanzahl,m);
    for i=1:m
        c=[c,kantenliste(i,3)];
        A(kantenliste(i,1),i)=1;
        A(kantenliste(i,2),i)=-1;
    end
    b= zeros(knotenanzahl,1);
    start =str2num(start);
    ziel=str2num(ziel);
    b(start)=1;
    b(ziel)=-1;
    [i j] = size(A);
    B=[A,eye(i,i),zeros(i,i+1),b;A,zeros(i,i),-eye(i,i),zeros(i,1),b;c,zeros(1,i+i),1,0];
    [n m] = size(B);
    [InMatrix] = simplexmethod( B, n, m );
    [solution costs] = displaySolution(A,InMatrix,c);
    C=zeros(j,3);
    for u=1:j
       row = find(A(:,u)==1) ;
       col = find(A(:,u)==-1) ;
       C(u,1)=row;
       C(u,2)=col;
       C(u,3)=c(u);
    end
    wegeplot(C,solution);
    out=[];
    for i = 1:length(solution)-1
       if solution(i) ~= 0
          out = [out , C(i,1),C(i,2)]; 
       end
    end
	str = mat2str(out);
    
    Msgbox(strcat('Der optimale Weg führt über die Knoten: ',str, ' und hat die Gesamtkosten: ' , mat2str(costs)));
end


%============================================================
%           Abbrechen
%============================================================
% --- Executes on button press in pushbutton2.
function pushbutton2_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton2 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
close(Wegsuche);

%============================================================
%           Löschen
%============================================================
% --- Executes on button press in pushbutton3.
function pushbutton3_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton3 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
position = get(handles.listbox1,'value');
string = get(handles.listbox1,'String');
string(position,:)=' ';
set(handles.listbox1,'String',string);

%============================================================
%           Hinzufügen
%============================================================
% --- Executes on button press in pushbutton4.
function pushbutton4_Callback(hObject, eventdata, handles)
% hObject    handle to pushbutton4 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)
startknoten = get(handles.edit2,'String');
zielknoten = get(handles.edit3,'String');
kosten = get(handles.edit4,'String');
if (isempty(str2num(kosten)) == false && str2num(kosten) > 0)
    if isValidNode(startknoten) && isValidNode(zielknoten)
        str = strcat(startknoten,'->' , zielknoten, ': ' , kosten);
        string = char(get(handles.listbox1,'string'));
        values = strvcat(string,str);
        set(handles.listbox1,'String',values);
        set(handles.edit2,'String','');
        set(handles.edit3,'String','');
        set(handles.edit4,'String','');
    end
else
    msgbox('Bitte geben Sie eine reelle Zahl zur Beschreibung der Kosten eines Weges ein.');
end


function b = isValidNode(node)
b = false;
if isempty(str2num(node)) == false
    node = str2num(node);
    if ((node ~= floor(node)) || (node <= 0))
        Msgbox('Bitte verwenden Sie nur natürliche Zahlen zur Eingabe der Knoten.');
    else
        b = true;
    end
else
    Msgbox('Bitte verwenden Sie nur natürliche Zahlen zur Eingabe der Knoten.');
end



function edit5_Callback(hObject, eventdata, handles)
% hObject    handle to edit5 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit5 as text
%        str2double(get(hObject,'String')) returns contents of edit5 as a double


% --- Executes during object creation, after setting all properties.
function edit5_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit5 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end



function edit6_Callback(hObject, eventdata, handles)
% hObject    handle to edit6 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    structure with handles and user data (see GUIDATA)

% Hints: get(hObject,'String') returns contents of edit6 as text
%        str2double(get(hObject,'String')) returns contents of edit6 as a double


% --- Executes during object creation, after setting all properties.
function edit6_CreateFcn(hObject, eventdata, handles)
% hObject    handle to edit6 (see GCBO)
% eventdata  reserved - to be defined in a future version of MATLAB
% handles    empty - handles not created until after all CreateFcns called

% Hint: edit controls usually have a white background on Windows.
%       See ISPC and COMPUTER.
if ispc && isequal(get(hObject,'BackgroundColor'), get(0,'defaultUicontrolBackgroundColor'))
    set(hObject,'BackgroundColor','white');
end

%====================================================================
% Die Methoden simplexmethod und pivot sind von der Website
% www.zweigmedia.com und das Copyright liegt bei Stefan Waner
%====================================================================
function [InMatrix] = simplexmethod( InMatrix, rows, cols )
%%%%
% Exogene Variablen:
numVariables=cols-1;
 maxSteps=50;
 epsilon=0.00000000000001;
starred=ones(1,rows);
 numRows = rows;
numConstraints = rows-1;
NumCols = numVariables + 1;
%displayFinalStatus: Ausgabe je nach Fehlermeldung bzw.gibt Lösung aus
%%%%%
negIndicator=false;
testRatio=[];
theRow=0;
singular=false;
phase1 = true;
TableauNumber = 1;
%Phase I
while ( (phase1==true) && (TableauNumber<=maxSteps)  )
checkingForZeros=true;
foundAZero=false;
    while checkingForZeros==true
        checkingForZeros=false;
            for i=1:numRows-1
                if (starred(i)==1)
                    break;
                end
            end
     theRowx=i;
        if ((InMatrix(theRowx, cols)==0)&&(starred(theRowx)==1))
         checkingForZeros=true;
         foundAZero=true;
            for j=1:cols-1
           InMatrix(theRowx,j)= -InMatrix(theRowx,j);
            end
         starred(theRowx)=0;
         TableauNumber=TableauNumber+1;  
        end  
    end
 phase1=false;
 for i=1:numConstraints
    if starred(i)==1
        phase1=true;
        break;  
    end
 end
 
 if phase1==true
    if foundAZero==false
        rowmax=0;
        for i=1:numRows-1
            if starred(i)==1
                break;
            end
        end
            theRowx=i;
            for j=1:NumCols-2
               numx=InMatrix(i,j);
               if numx>rowmax
                   rowmax=numx;
                   theColx=j;
               end
            end
            if rowmax==0
               singular=true;
            else
                for i=1:rows-1
                    testRatio(i)=-1;
                    
                    if abs(InMatrix(i, theColx))>0
                        if InMatrix(i, cols)<epsilon
                            InMatrix(i, cols)=0;
                        end
                        testRatio(i)=InMatrix(i,cols)/(InMatrix(i,theColx));
                    end
                end
                
              minRatio= 10000000000000;
               theRow=0;
                    for i=1:rows-1
                        if ((testRatio(i)>0) && (testRatio(i)<minRatio))
                            minRatio=testRatio(i);
                            theRow=i;
                        elseif ((testRatio(i) >=0) &&(testRatio(i)==minRatio))
                            if starred(i)==1
                                theRow=i;
                            elseif rand(1)>0.5
                                theRow=i;
                            end % tie breaker
                            
                        end
                        
                    end
                    
            end
       if theRow==0 
         singular=true;
       end %escape clause
       InMatrix=pivot (InMatrix, rows, cols, theRow, theColx);  
    end % Ende der Pivotisierung
   TableauNumber=TableauNumber+1;
 end
end %Ende Phase 1
    
 phase1=false; % to prevent inf loops
 %%%%%%%%% PHASE II
testnum=0;
for i=1:cols-1
    testnum=InMatrix(rows,i);
    if testnum <0
        negIndicator=true;
    end
end
theCol=0;
if negIndicator==true
    minval=0;
    for i=1:cols-1
        testnum=InMatrix(rows,i);
        if testnum<minval
            minval=testnum;
            theCol=i;
        end
    end
end

while ((negIndicator==true)&&(TableauNumber<=maxSteps))
    for i=1:rows-1
        testRatio(i)=-1;
        if InMatrix(i,theCol)>0
            if abs(InMatrix(i,cols))<epsilon
                InMatrix(i,cols)=0;
            end
            testRatio(i)=InMatrix(i,cols)/(InMatrix(i,theCol));
        end
    end
    minRatio = 10000000000000;
    theRow=0;
    for i=1:rows-1;
        if ((testRatio(i)>=0) && (testRatio(i)<minRatio))
            minRatio=testRatio(i);
            theRow=i;
        elseif ((testRatio(i) >= 0) && (testRatio(i) == minRatio))
            if rand(1)>0.5
                 theRow=i; %tie breaker
            end
        end
    end
   if (theRow == 0) 
       singular = true;
   end
   InMatrix = pivot(InMatrix,rows,cols,theRow,theCol);
   TableauNumber=TableauNumber+1;
   
   negIndicator = false;
   for i=1:cols-1
       if InMatrix(rows,i)<0
           negIndicator=true;
       end
   end
   %Error Correction below
   if negIndicator==true
       minval =0;
       for i=1:cols-1
           testnum=InMatrix(rows,i);
           if testnum<minval
               minval=testnum;
               theCol=i;
           end
       end
       
   end
   
end % Ende Phase II

function Matrix = pivot(InMatrix,rows,cols,theRow,theCol)
thePivot = InMatrix(theRow,theCol);
for i=1:cols
   InMatrix(theRow,i)=InMatrix(theRow,i)/thePivot; 
end
for i =1:rows
   if ((i~=theRow)&&(InMatrix(i,theCol)~=0))
      factr = InMatrix(i,theCol);
      for j=1:cols
          InMatrix(i,j)=InMatrix(i,j)-factr*InMatrix(theRow,j);
      end
   end
end
Matrix=InMatrix;
%====================================================================

function [solution costs]=displaySolution(A,B,c)
[m,n]=size(B);
[o,p]=size(A);
solution=zeros(1,p);
%Suche nun alle Einträge in der letzten Spalte identisch 1:
fitting_rows=[];
for i=1:m
   test= B(i,n);
   if B(i,n)==1
      fitting_rows=[fitting_rows;i]; 
   end
end
%suche nun für diese Zeilen den vordersten Wert gleich 1, und setze diese
%Spaltennummer
%in den Lösungsvektor  an der richtigen Stelle ein
[k l]=size(fitting_rows);
for i=1:k
    solution(find(B(fitting_rows(i),1:p)==1,1))=1;
end %for
% Die Weglänge ergibts sich aus dem Kostenvektor c und dem Lösungsvektor
% solution
costs=solution*c';
% Ausgabe des Lösungsvektors und der Kosten

function []=wegeplot(A,lsg)
% ich gehe davon aus, dass A die Matrix ist, in der die Punktstrecken
% festgehalten sind. und zwar derart, dass in einer zeile a und b
% eingetragen sind und für den weg von a nach b stehen
% lsg ist der vektor, der die reihenfolge der punkte des optimalen weges
% enthält

m=max(max(A(:,1)),max(A(:,2))); % Anzahl der ecken
[n,~]=size(A);                  % Anzahl der wege
f=@(x) 0.4*([sin(x),cos(x)])+[0.5,0.5]; % funktoin zur bestimmung der position der eckpunkte


B=zeros(m,2);
for j=1:m  %Eckpunkte errechnen
    B(j,:)=f(2*pi*j/m);
end
figu=figure;

plot(B(:,1),B(:,2),'o','Markersize',2.5,'LineWidth',4,'MarkerEdgeColor','b')
% Eckpunkte plotten, danach achsen einrichten
axis equal
axis off

%hier sind eineige verschiedenen hintergrund farben, das erste ist wieß,
%dann hellblau und hell grün, frei wählbar
%set(figu,'Color',[1,1,1])
set(figu,'Color',[0.8,0.85,1])
%set(figu,'Color',[0.85 1 0.75]) 

for j=1:m % Beschriftung der ecken
    str = int2str(j);
    p=position(B(j,:));
    text(p(1),p(2),str,'EdgeColor','b')
end
hold on

for i=1:n % Kanten plotten
    x=B(A(i,1),:);  % Startpunkt des i-ten pfeils
    y=B(A(i,2),:);  % Endpunkt dazu
    [z,ort]=pfeil(x,y);
    plot(z(:,1),z(:,2),'k','LineWidth',1.3)
end

%ich mache aus der reihenfolge der punkte eine matrix wie für die ersten
%pfeile...
AA=[];
for i=1:length(lsg)-1
    if lsg(i) ==1
        AA=[AA;A(i,1),A(i,2)];
    end
end
 %... und plotte diese
 [a ~] = size(AA);
for i=1:a
    x=B(AA(i,1),:);
    y=B(AA(i,2),:);
    [z,ort]=pfeil(x,y);
    plot(z(:,1),z(:,2),'m','LineWidth',3)
end


function [z,ort]=pfeil(x,y)
% x,y sind zeilenvektoren,z hat vier zeilen, 2 spalten, also eine reihe
% entspricht einem punkt.
% hierbei sind x und y anfangs- und endpunkt des pfeils, der von x nach y
% zeigt. z wird eine matrix, in der punkte abgespeichert sind, die einfach
% nur noch geplottet werden müssen. d.h. diese function schreibt nur die
% koordinaten von x und y zu einer reihe von punkten, die geplottet einen
% pfeil ergeben

% der kopf soll 0.05 lang sein

richtung=y-x;
lang=sqrt(richtung(1)^2+richtung(2)^2);
senkrecht=[-richtung(2),richtung(1)]/lang;
langsoll=lang-0.03;
g=@(t) t*y+(1-t)*x;   % t zwischen 0 und 1
t=langsoll/lang;
s=0.1/lang;
ort=g(s);
hilfspunkt=g(t);
seitenpunkt1=hilfspunkt+0.008*senkrecht;
seitenpunkt2=hilfspunkt-0.008*senkrecht;
z=[x;y;seitenpunkt1;y;seitenpunkt2;y];


function [p]=position(b)
% b bezeichnet die position des grünen punktes, zu dem wir gerade die
% position der numerierung generieren wollen
m=[0.5,0.5];    % m ist der mittelpunkt des regulären n-ecks
p=m+(0.45/0.4)*(b-m);

