Graph

From Progteam

Revision as of 03:10, 22 February 2008 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A graph is a set of objects called points, nodes, or vertices connected by links called lines or edges. In a proper graph, which is by default undirected, a line from point A to point B is considered to be the same thing as a line from point B to point A. In a digraph, short for directed graph, the two directions are counted as being distinct arcs or directed edges. Typically, a graph is depicted in diagrammatic form as a set of dots (for the points, vertices, or nodes), joined by curves (for the lines or edges)

Code Packet

Modeling problems as graphs is essential for contest problems. The implementation of a graph, and some graph algorithms appear below:

NOTE: This class requires a List implementation, which also appears in the code packet.

import java.util.*;

class Graph{
    /** Core Stuff **/
    public Vertex[] verts;

    public Graph(int order){
        verts=new Vertex[order];

        for(int i=0;i<order;i++){
            verts[i]=new Vertex();
            verts[i].ID=i;
        }
    }

    public void addEdge(Vertex i,Vertex j){
        i.adj.add(j);
        j.adj.add(i);
    }

    public void addEdge(int i,int j){
        addEdge(verts[i],verts[j]);
    }

    public void removeEdge(Vertex i,Vertex j){
        i.adj.remove(j);
        j.adj.remove(i);
    }

    /** Optional Stuff **/

    public Vertex getFirst(){
        return verts[0];
    }

    public boolean isConnected(){
        return verts.length==countNodes(getFirst());
    }

    private int countNodes(Vertex v){
        if(v.visited)
            return 0;

        v.visited=true;

        int num=1;

        for(Vertex x:v){
            num+=countNodes(x);
        }

        return num;
    }
}

class Vertex implements Iterable<Vertex>{
    public boolean visited=false;
    public List adj;
    public int ID;

    public Vertex(){
        adj=new List();
    }

    public int degree(){
        return adj.size;
    }

    public Iterator<Vertex> iterator(){
        return adj.iterator();
    }

}

class List implements Iterable<Vertex>{

    class Node{
        Vertex el;
        Node next;
    }

    class Iter implements Iterator<Vertex>{
        Node ptr;

        public boolean hasNext(){
            return ptr.next!=null;
        }
        public Vertex next(){
            ptr=ptr.next;return ptr.el;
        }
        public void remove(){}
    }

    Node header;
    int size;

    public List(){
        header=new Node();
        header.next=null;
        size=0;
    }

    public boolean add(Vertex v){
        for(Vertex x:this)
            if(v.equals(x))
                return false;
        Node n=new Node();
        n.el=v;
        n.next=header.next;
        header.next=n;
        ++size;
        return true;
    }

    public boolean remove(Vertex v){
        for(Node n=header;n.next!=null;n=n.next)
            if(n.next.el.equals(v)){
                n.next=n.next.next;
                --size;
                return true;
            }
        return false;
    }

    public Iter iterator(){
        Iter i=new Iter();
        i.ptr=header;
        return i;
    }
}

Personal tools