• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 414
  • Last Modified:

Non-weighted and non-directed graph

Hi,
  I have to implement a simple class for a non-weighted and non-directed graph. Which data structure should I use, taking into account that I have to implement a function that would return the shortest path from one node to another? That is to say, the least possible number of edges between one vertex from another.
0
zwinmin
Asked:
zwinmin
  • 2
2 Solutions
 
AlexFMCommented:
http://msdn.microsoft.com/vcsharp/default.aspx?pull=/library/en-us/dv_vstechart/html/datastructures_guide5.asp

This article contains good description of graphs and data structures used to keep them in memory, and Dijkstra's algorithm to find shortest path between graph nodes.
Sample code is in C# (this language is easy understandable to C++ developer). You can use only article text or sample code if you are familiar with C#.
0
 
zwinminAuthor Commented:
The article suggested using adjacency list or adjacency matrix to implement the graph. But the algorithm described there is to find shortest path for weighted path, while i am doing it for non-weighted path. So, how should I find the shortest path for non-weighted graph using adjacency matrix? Thanks.
0
 
AlexFMCommented:
For non-weighted graph it is not necessary to keep edge weight in the Node instance of adjacency list. Generally, it is beter to keep edge weight and set it always to 1 for non-weighted graph. In this case the same algorithm will work both for weighted and non-weighted graphs.
0
 
itsmeandnobodyelseCommented:
I tried it using my own structures and algorithm:

#include<iostream>
#include <map>
#include <list>
using namespace std;

class Vertex
{
    int id;
public:
    Vertex() : id(0) {}
    Vertex(int i) : id(i) {}
    bool operator < (const Vertex& vertex) const
    {
        return id < vertex.id;
    }
    bool operator == (const Vertex& vertex) const
    {
        return id == vertex.id;
    }
    bool operator == (int i) const
    {
        return id == i;
    }
    int getId() const { return id; }
};

class Edge
{
    static int   nextId;
    int id;
    Vertex v1;
    Vertex v2;
public:

    Edge(int i1, int i2)
        : id(++Edge::nextId), v1((i1 < i2)? i1:i2), v2((i1 <i2)? i2 : i1) {}
    Edge(const Vertex& ve1, const Vertex& ve2)
        : id(++Edge::nextId)
    {  
        v1 = (ve1 < ve2)? ve1 : ve2;
        v2 = (ve1 < ve2)? ve2 : ve1;
    }    

    bool operator < (const Edge& edge) const
    {
        return v1 < edge.v1;
    }

    const Vertex& getV1() const { return v1; }
    const Vertex& getV2() const { return v2; }
};

class Distance
{
    Vertex v;
    int dist;
public:
    Distance() : v(0), dist(0) {}
    Distance(const Vertex& ve1, int d) : v(ve1), dist(d) {}
    Vertex& getV() { return v; }
};

class SimpleGraph
{
    list<Edge> edges;
public:
    void add(int n1, int n2)
    {
        edges.push_back(Edge(n1, n2));
    }
    int getNeighbors(const Vertex& v, list<Vertex>& neighbors)
    {
        sort();
        bool found = false;
        for (list<Edge>::iterator it = edges.begin(); it != edges.end(); ++it)
        {
            if (it->getV1() == v)
            {
                found = true;
                neighbors.push_back(it->getV2());
            }
            else if (found)
                break;
        }
        return neighbors.size();
    }

    int getShortestPath(int n1, int n2, list<Vertex>& path)
    {
        int dist = 1;
        list<Vertex> vl1;
        list<Vertex> vl2;
        list<Vertex>& vc = vl1;
        list<Vertex>& vn = vl2;
        map<Vertex, Distance> m;

        Vertex v1 = n1;
        Vertex v2 = n2;
        m[v1] = Distance(v1, 0);
        vc.push_back(v1);
        bool found = v1 == v2;

        while (!found && dist <= edges.size())
        {
            for (list<Vertex>::iterator it = vc.begin(); it != vc.end(); ++it)
            {
                v1 = *it;
                list<Vertex> neighbors;
                getNeighbors(v1, neighbors);
                for (list<Vertex>::iterator it1 = neighbors.begin(); it1 != neighbors.end(); ++it1)
                {
                    v2 = *it1;
                    cout << dist << ":" << v1.getId() << " -> " << v2.getId() << endl;
                    if (m.find(v2) == m.end())
                    {
                        m[v2] = Distance(*it, dist);
                        vn.push_back(v2);
                        if (*it1 == n2)
                        {
                            found = true;
                            break;
                        }
                    }
                   
                }
            }
            list<Vertex>& vs = vc;
            vc = vn;
            vn = vs;
            vn.clear();
            dist++;
        }

        path.clear();
        if (found)
        {
            v1 = Vertex(n1);
            v2 = Vertex(n2);
            Vertex v = v2;
            path.push_front(v2);
            while(!(v == v1))
            {
                Distance d = m[v];
                v = d.getV();
                path.push_front(v);
            }
        }
        return dist;
    }

protected:
    void sort()
    {
        edges.sort();
    }

};  

int   Edge::nextId      = 0;  
     
int  main()
{
    SimpleGraph g;
    g.add(1, 2);
    g.add(1, 5);
    g.add(1, 7);
    g.add(2, 3);
    g.add(2, 5);
    g.add(2, 8);
    g.add(2, 11);
    g.add(5, 8);
    g.add(5, 6);
    g.add(7, 9);
    g.add(10, 9);
    g.add(10, 11);
    g.add(10, 13);
    g.add(13, 12);
    g.add(6, 12);

    list<Vertex> route;

    if (g.getShortestPath(1, 13, route) > 0)
    {
        for (list<Vertex>::iterator it = route.begin(); it != route.end(); ++it)
        {
            cout << it->getId() << " -> ";
        }
        cout << endl;
    }

    return 0;
}

Regards, Alex
0

Featured Post

Prep for the ITIL® Foundation Certification Exam

December’s Course of the Month is now available! Enroll to learn ITIL® Foundation best practices for delivering IT services effectively and efficiently.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now