// 2010_1_4.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

class Graph
{
    class Edge
    {
        public:
            int destination;
            double wage;
        public:
            Edge(int a, double b=0): destination(a), wage(b) {}
            ~Edge() {}
    };

    class Node
    {
        public:
            int number;
            vector<Edge> edges;
            vector<Edge>::iterator it;

        public:

            void add(Edge a)
            {
                it=edges.begin();
                for(; it != edges.end(); it++)
                    if(it->destination==a.destination) break;
                if(it==edges.end()) edges.push_back(a);
            }

            Node(int a): number(a) {}
            Node(int a, int b, double c=0): number(a)
            {
                add(Edge(b, c));
            }

            ~Node()
            {
                for(it=edges.begin(); it != edges.end(); it++) {}
                    //delete *it;
                edges.clear();
            }
    };

    vector<Node> graf;
    vector<Node>::iterator iter_graf, iter_graf_2;

    public:
        Graph(int n=0)
        {
            for(int i=1; i<=n; i++)
                graf.push_back(Node(i));
        }

        vector<Node>::iterator find_node(int s)
        {
            vector<Node>::iterator help=graf.begin();

            for(; help != graf.end(); help++)
                if(help->number==s) break;

            return help;
        }

        vector<Edge>::iterator find_edge(vector<Node>::iterator help, int e)
        {
            for(help->it=help->edges.begin(); help->it != help->edges.end(); help->it++)
                if(help->it->destination==e) break;

            return help->it;
        }

        bool dodajWierzcholek(int n)
        {
            iter_graf=graf.begin();
            for(; iter_graf != graf.end(); iter_graf++)
                if(iter_graf->number==n) break;

            if(iter_graf!=graf.end() && !graf.empty())  return false;

            graf.push_back(Node(n));

            return true;
        }

        bool dodajKrawedz(int s, int e, double dlug)
        {
            dodajWierzcholek(s);
            dodajWierzcholek(e);

            vector<Edge>::iterator helper1, helper2;
            iter_graf=find_node(s);
            iter_graf_2=find_node(e);
            helper1=find_edge(iter_graf, e);
            helper2=find_edge(iter_graf_2, s);

            if(helper1 == iter_graf->edges.end() && helper2 == iter_graf_2->edges.end())
            {
                iter_graf->edges.push_back(Edge(e, dlug));
                iter_graf_2->edges.push_back(Edge(s, dlug));
                return true;
            }
            return false;
        }

        bool usunKrawedz(int s, int e)
        {
            iter_graf=find_node(s);
            iter_graf_2=find_node(e);

            if(iter_graf == graf.end()||iter_graf_2 == graf.end()) return false;

            vector<Edge>::iterator helper1, helper2;
            helper1=find_edge(iter_graf, e);
            helper2=find_edge(iter_graf_2, s);

            if(helper1 == iter_graf->edges.end()||helper2 == iter_graf_2->edges.end()) return false;
            //delete *iter_graf->it;
            iter_graf->edges.erase(helper1);
            iter_graf_2->edges.erase(helper2);
            return true;
        }

        bool usunKrawedzieWierzch(int n)
        {
            iter_graf=find_node(n);

            if(iter_graf == graf.end()) return false;

            iter_graf->edges.clear();
            return true;
        }

        bool usunWierzcholek(int n)
        {
            iter_graf=find_node(n);

            if(iter_graf == graf.end()) return false;

            iter_graf->edges.clear();
            graf.erase(iter_graf);
            return true;
        }

        bool dlug(double &wynik, const vector<int> &d)
        {
            wynik=0;
            vector<Edge>::iterator helper;
            for(int i=1; i<d.size(); i++)
            {
                iter_graf=find_node(d[i]);

                if(iter_graf==graf.end())
                {
                    wynik=-1;
                    return false;
                }

                helper=find_edge(iter_graf, d[i-1]);

                if(helper==iter_graf->edges.end())
                {
                    wynik=-1;
                    return false;
                }

                wynik+=helper->wage;
            }
            return true;
        }

        ~Graph()
        {
            //iter_graf=no
        }
};

int main()
{
    Graph moj;

    moj.dodajKrawedz(1,2,5);
    moj.dodajKrawedz(2,3,4);
    moj.dodajKrawedz(1,3,2);

    moj.dodajWierzcholek(4);

    vector<int> d;
    d.push_back(1); d.push_back(2); d.push_back(3);
    double wynik;
    moj.dlug(wynik, d);
    if(wynik<0) cout<<"Brak sciezki\n";
    else cout<<wynik<<"\n";
    moj.usunKrawedzieWierzch(3);
    moj.dlug(wynik, d);
    if(wynik<0) cout<<"Brak sciezki\n";
    else cout<<wynik<<"\n";
    system("pause");
    return 0;
}