C++ Program to Find the Shortest Cycle in a Graph

[preslav_milev]

Hi. I need to write a program that finds the shortest route in directed graph.
Please look at the picture.
Click Here

Here is my code:

#include <iostream>

using namespace std;

const int N = 10;

struct elem
{
    char key;
    elem *next; 
} *g[N];

void init(elem *g[N])
{
    for (int i = 0; i < N; i++)
        g[i] = NULL;
}

int search_node(char c, elem *g[N])
{
    for (int i = 0; i < N; i++)
        if (g[i])
            if (g[i]->key == c)
                return 1;

    return 0;
}

int search_arc(char from, char to, elem *g[N])
{
    if (search_node(from, g) && search_node(to, g))
    {
        int i = 0;

        while (g[i] == NULL || g[i]->key != from) i++;

        elem *p = g[i];

        while(p->key != to && p->next)
            if (p->key == to)
                return 1;
    }

    return 0;
}

void add_node(char c, elem *g[N])
{
    if (search_node(c, g))
        cout << "Node already exists.\n";

    int i = 0;
    while (g[i] && (i < N)) i++;

    if (g[i] == NULL)
    {
        g[i] = new elem;
        g[i]->key = c;
        g[i]->next = NULL;
    }
    else
    {
        cout << "Maximum nodes reached.\n";
    }
}

void add_arc(char from, char to, elem *g[N])
{
    if (search_arc(from, to, g))
        cout << "Arc already exists.\n";
    else
    {
        if (!search_node(from, g))
            add_node(from, g);

        if (!search_node(to, g))
            add_node(to, g);

        int i = 0;
        while (g[i] == NULL || g[i]->key != from) i++;

        elem *p = new elem;
        p->key = to;
        p->next = g[i]->next;

        g[i]->next = p;
    }
}

void del_node(char c, elem *g[N])
{

    if(search_node(c, g))
    {

        int i = 0;
        while(g[i] == NULL || g[i]->key != c)
            i++;
        elem *p, *q;
        while(g[i])
        {

            p = g[i];
            g[i] = g[i]->next;
            delete p;

        }

        for(int i = 0; i < N; i++)
            if(g[i])
            {

                p = g[i];
                while(p->key != c && p->next)
                {

                    q = p;
                    p = p->next;

                }
                if(p->key == c)
                {

                    q->next = p->next;
                    delete p;

                }

            }

    }
    else
        cout << "\nThe node is not in the graph!" << endl;

}

void del_arc(char c1, char c2, elem *g[N])
{

    /*if(search_arc(c1, c2, g))
    {

        int i = 0;
        while(g[i])

    }*/

}

int cnt = 0;

void print(elem *g[N])
{

    for (int i = 0; i < N; i++)
        if (g[i])
        {
            elem *p = g[i];

            while(p)
            {
                cout << p->key << "\t";
                p = p->next;
                cnt++;
            }

            cout << endl;
        }

        cout << "Number of nodes: " << cnt << endl;

}

/*
void dijkstra()
{

    int s[N] = {0}; // N - number of nodes in graph
    int d[N]; // array, which store the shortest paths from the start
    int p[N]; // p is supporting array containing peaks prior to the current special path
    int w, i;
    s[0] = 1;
    int c[N];

    for(int i = 1; i < N; i++)
    {

        d[i] = c[0, i];
        p[i] = 0;

    }

    for(int i = 1; i < N; i++)
    {

        s[w] = 1;
        for(int i = 1; i < N; i++)
            if(s[i] == 0)
                if(d[i] > d[w] + c[w, i])
                {

                    p[i] = w;
                    d[i] = d[w] + c[w, i];

                }

    }

}
*/

int main()
{

    int choice;

    do
    {
        cout<<"\n\t\t\t\t MAIN MENU\n";
        cout<<"\t\t  # # # # # # # # # # # # # # # # # # # # #"<<endl;
        cout<<"\t\t  #                                       #";
        cout<<"\n\t\t  #  1. Search node                       #";
        cout<<"\n\t\t  #  2. Search add                        #";
        cout<<"\n\t\t  #  3. Add node                          #";
        cout<<"\n\t\t  #  4. Add arc                           #";
        cout<<"\n\t\t  #  5. Pring graph                       #";
        cout<<"\n\t\t  #  6. Find shortest cycle               #";
        cout<<"\n\t\t  #  7. Delete node                       #";
        cout<<"\n\t\t  #  8. Delete arc                        #";
        cout<<"\n\t\t  #  9. Exit                              #"<<endl;
        cout<<"\t\t  #                                       #";
        cout<<"\n\t\t  # # # # # # # # # # # # # # # # # # # # #"<<endl;
        cout<<"\n\t\t  Select your choice: ";

        cin >> choice;

        cout<<"\n";

        char node_key;
        char from, to;

        switch(choice)
        {
            case 1:
                cout << "Node key: ";
                cin >> node_key;
                cout << (search_node(node_key, g) ? "Node exists." : "Node doesn't exist." ) << endl;
                break;
            case 2:
                cout << "From: ";
                cin >> from;
                cout << "To: ";
                cin >> to;
                cout << (search_arc(from, to, g) ? "Arc exists." : "Arc doesn't exist." ) << endl;
                break;
            case 3:
                cout << "Node key: ";
                cin >> node_key;
                add_node(node_key, g);
                break;
            case 4:
                cout << "From: ";
                cin >> from;
                cout << "To: ";
                cin >> to;
                add_arc(from, to, g);
                break;
            case 5:
                print(g);
                break;
            case 6:
                dijkstra();
                break;
            case 7:
                break;
            case 8: 
                break;
            case 9:
                exit(0);
                break;
        }
    } while (true);

    system("pause");
    return 0;
}

I try to use the algorithm of Dijkstra, but something is not working.

[David W]

You will find that help comes more readily if you present the problem clearly.

Provide the shortest amount of code possible to illustrate the problem.

State clearly the problem ...

i.e. do NOT just say:

'there is a problem' / 'something is not working' !

[David W]

P.S.

You may find some related examples here:

http://developers-heaven.net/forum/index.php/topic,2614.0.html

[preslav_milev]

Hi.

I think I found another way to solve the problem instead of using algorithm of Dijkstra. My graph is (A,B,C,D) and the connections (arcs) between the elements are (A->B), (A->A), (B->C), (B->A), (C->D), (C->A), (D->A) and so cycles are the following: А->B->C->D->A; A->B->C->A; A->B->A; A->A. Program should print the shortest cycle, ie A->A. To solve it i need first to find all cycles, then put them each in a separate list and finally bring the smallest list, which will be the shortest cycle (A-> A), but I do not know how to realize it. At the moment I made connections (arcs) between elements. here's optimized code:

#include <iostream>

using namespace std;

const int N = 10;

struct elem
{
    char key;
    elem *next; 
} *g1[N];

void init(elem *g[N])
{
    for (int i = 0; i < N; i++)
        g[i] = NULL;
}

int search_node(char c, elem *g[N])
{
    for (int i = 0; i < N; i++)
        if (g[i])
            if (g[i]->key == c)
            {
                return 1;
            }

    return 0;
}

int search_arc(char from, char to, elem *g[N])
{
    if (search_node(from, g) && search_node(to, g))
    {
        int i = 0;

        while (g[i]->key != from) i++;

        elem *p = g[i]->next;

        while (true)
        {
            if (p == NULL)
            {
                break;
            }

            if (p->key == to)
            {
                return 1;
            }

            p = p->next;
        }
    }

    return 0;
}

void add_node(char c, elem *g[N])
{
    if (search_node(c, g))
        cout << "Node already exists.\n";

    int i = 0;
    while (g[i] && (i < N)) i++;

    if (g[i] == NULL)
    {
        g[i] = new elem;
        g[i]->key = c;
        g[i]->next = NULL;
    }
    else
    {
        cout << "Maximum nodes reached.\n";
    }
}

void add_arc(char from, char to, elem *g[N])
{
    if (search_arc(from, to, g))
        cout << "Arc already exists.\n";
    else
    {
        if (!search_node(from, g))
            add_node(from, g);

        if (!search_node(to, g))
            add_node(to, g);

        int i = 0;
        while (g[i]->key != from) i++;

        elem *p = new elem;
        p->key = to;
        p->next = g[i]->next;

        g[i]->next = p;
    }
}

void print(elem *g[N])
{
    for (int i = 0; i < N; i++)
    {
        if (g[i] != NULL)
        {
            elem *p = g[i];

            while (p)
            {
                cout << p->key << "\t";
                p = p->next;
            }

            cout << endl;
        }
    }
}


void iscycle(elem *g[N])
{

}

int main()
{
    system ("cls");

    cout << "init: " << endl;
    init(g1);

    cout << "graph 1: " << endl;
    add_arc('a', 'b', g1);
    add_arc('a', 'a', g1);
    add_arc('b', 'c', g1);
    add_arc('b', 'a', g1);
    add_arc('c', 'a', g1);
    add_arc('c', 'd', g1);
    add_arc('d', 'a', g1);

    print(g1);

    cout << "cycles: ";
    iscycle(g1);

    system("pause");
    return 0;

}