Archive

Posts Tagged ‘graphs’

Find a path between two vertices using Python


Representation of the graphs and their usage is very easy with the concept of Dictionaries in Python. Dictionaries come very handy in representing Graphs in Adjacency list form.

Here is the Python code:

def Graph():
    graph={}
    size1=int(raw_input('Enter the size of the graph:'))

    for i in range(size1):
        node=(raw_input('Enter a node:'))
        adj=[]
        ad=(raw_input('Enter adjacent vertex:( enter -1 when done):'))
        while(ad!='-1'):
            adj.append(ad)
            ad=(raw_input('Enter adjacent vertex:( enter -1 when done)'))
        graph[node]=adj

    visited={}
    for i in graph.keys():
        visited[i]=False
    print visited
    start=raw_input('Enter start vertex:')
    end=raw_input('Enter start vertex:')
    print find_path(graph,start,end)

def find_path(graph,start,end, path=[]) :
    path=path+[start]
    if start==end :
        return path
    if not graph.has_key(start) :
        return None
    else :
        for node in graph[start] :
                 if node not in path:
                    newpath = find_path(graph, node, end, path)
                 if newpath :
                    return newpath
        return None

def main() :
    Graph()

if __name__=='__main__' :
    main()

Adjacency list represention of graph in Java


Here is the program for adjacency list representation of graphs using java. If you are new to Graphs please read about graphs here before reading the rest of this post.

I used a List data structure inside the graph. I think much explanation is not required because it is very simple.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @author Vasanth Raja Chittampally
 */
class List{
    int node;
    List next;
}

class Node {
    int node;
    List adjList;
}

public class Graphs {
    void insertVertices() throws IOException
    {
         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter number of nodes in a graph: ");
        int n=(Integer.parseInt(br.readLine()));
        Node g[]=new Node[n];
        for (int i = 0; i < n; i++) {
            g[i]=new Node();
            g[i].node=i+1;
            g[i].visit=false;
            while(true)
            {
                System.out.println("Enter zero to stop");
                System.out.println("Enter adjacent nodes to node "+(i+1)+" :");
                 int adjVertex=Integer.parseInt((br.readLine()));
                 if(adjVertex==0)
                     break;
                 else
                 {
                        List l=new List();
                        l.node=adjVertex;
                        l.next=null;
                        if(g[i].adjList==null)
                        {
                            g[i].adjList=l;
                        }
                        else
                        {
                            List p=g[i].adjList;
                            while(p.next!=null){
                                p=p.next;
                            }
                            p.next=l;
                        }
                 }
            }
        }
        System.out.println("Adjacency matrix representation");
        for (int i = 0; i < n; i++) {
            System.out.print(g[i].node+" --> ");
            List l=g[i].adjList;
            while(l!=null)
            {
                System.out.print(l.node+" --> ");
                l=l.next;
            }
            System.out.println("");
        }
    }

    public static void main(String[] args) throws IOException {
             new Graphs().insertVertices();
    }

}