Docs for CS252 Spring 2002: Class IncidenceListOrderedGraph

Overview

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: INNER | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

jdsl.map.ref
Class IncidenceListOrderedGraph

java.lang.Object
  |
  +--jdsl.core.ref.AbstractPositionalContainer
        |
        +--jdsl.graph.ref.AbstractGraph
              |
              +--jdsl.map.ref.IncidenceListOrderedGraph

All Implemented Interfaces:: Container, InspectableContainer, InspectableGraph, InspectableOrderedGraph, InspectablePositionalContainer, ModifiableGraph, OrderedGraph, PositionalContainer

public class IncidenceListOrderedGraph
extends AbstractGraph
implements OrderedGraph

Implements the OrderedGraph interface by a list of vertices, each of which has a circular sequence of edges. The graph also has a list of edges, in order to support certain operation more easily and quickly (for example, elements(), isElement(), size()).

The sequences store as their elements the positions of the graph. So verts_ stores ILOGVertex's as its elements, edges_ stores ILOGEdge's. The positions in turn know their position within the appropriate sequence, so that when the user gives the graph a vertex or an edge, the graph can extract that information in constant-time.

That is a source of some difficulty for the edges, since they are contained within the graph's edgelist, as well as within its two endvertices' incidence lists. This was resolved by requiring the caller to identify itself, so that the edge can then know which position to report.

This class does not claim to be the most efficient graph data structure possible: asymptotic improvements are possible in certain methods, and large constant factors could be fixed. Some places to improve:

Use copy-on-write techniques for getting iterators, for speed.
Use dictionaries to store some information, for example the adjacency lists, in order to have better running-time for some queries, for example edges(Vertex,Vertex)
Have vertices store 3 lists of edges: incoming, outgoing, or undirected, for faster queries based on those (this will, however, increase the difficulty, and most likely time, of handling edges)

Version:: $Id: IncidenceListOrderedGraph.java,v 1.11 2001/04/03 16:20:55 lv Exp $
Author:: Benoit Hudson, Luca Vismara (lv)

Inner classes inherited from class jdsl.graph.ref.AbstractGraph

AbstractGraph.OO_to_O_MergerIterator

Constructor Summary

IncidenceListOrderedGraph()


Method Summary

Edge anEdge()
          O(1)

Edge anIncidentEdge(Vertex v)
          O(1)

Edge anIncidentEdge(Vertex v, int edgetype)
          O(degree)

boolean areIncident(Vertex v, Edge e)
          O(1)

Edge attachVertex(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement)


Edge attachVertex(Vertex v, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)

Edge attachVertexFrom(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement)


Edge attachVertexFrom(Vertex origin, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)

Edge attachVertexTo(Vertex v, java.lang.Object vertexElement, java.lang.Object edgeElement)


Edge attachVertexTo(Vertex destination, Order order, Edge e, java.lang.Object vertexInfo, java.lang.Object edgeInfo)
          O(1)

Vertex aVertex()
          O(1)

boolean contains(Accessor p)
          O(1)

int degree(Vertex v)
          O(1)

int degree(Vertex v, int edgetype)
          O(degree)

Vertex destination(Edge e)
          O(1)

EdgeIterator edges()
          O(m)

ObjectIterator elements()
          O(n+m)

Vertex[] endVertices(Edge e)
          O(1)

EdgeIterator incidentEdges(Vertex v)
          O(degree)

EdgeIterator incidentEdges(Vertex v, int edgetype)
          O(degree)

Edge insertDirectedEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, java.lang.Object info)
          O(1)

Edge insertDirectedEdge(Vertex v1, Vertex v2, java.lang.Object element)


Edge insertEdge(Vertex v1, Order order1, Edge e1, Vertex v2, Order order2, Edge e2, java.lang.Object info)
          O(1)

Edge insertEdge(Vertex v1, Vertex v2, java.lang.Object element)


Vertex insertVertex(java.lang.Object elt)
          O(1)

boolean isDirected(Edge e)
          O(1)

void makeUndirected(Edge e)
          O(1)

void moveEndVertex(Edge e1, Vertex v1, Vertex v2, Order order, Edge e2)
          O(1)

Container newContainer()
          O(1)

Edge nextIncidentEdge(Vertex v, Edge e)
          O(1)

Edge nextIncidentEdge(Vertex v, Edge e, int edgetype)
          O(degree)

int numEdges()
          O(1)

int numVertices()
          O(1)

Vertex opposite(Vertex v, Edge e)
          O(1)

Vertex origin(Edge e)
          O(1)

Edge prevIncidentEdge(Vertex v, Edge e)
          O(1)

Edge prevIncidentEdge(Vertex v, Edge e, int edgetype)
          O(degree)

java.lang.Object removeEdge(Edge e)
          O(1)

java.lang.Object removeVertex(Vertex v)
          O(degree)

java.lang.Object replaceElement(Accessor p, java.lang.Object newElement)
          O(1)

void reverseDirection(Edge e)
          O(1)

void setDirectionFrom(Edge e, Vertex v)
          O(1)

void setDirectionTo(Edge e, Vertex v)
          O(1)

Vertex splitEdge(Edge e, java.lang.Object info)
          O(1)

Edge splitVertex(Vertex v, Edge e1, Edge e2, java.lang.Object edgeinfo)
          O(degree)

Edge unsplitEdge(Vertex v, java.lang.Object info)
          O(1)

Vertex unsplitVertex(Edge e, java.lang.Object vertexinfo)
          O(degree1+degree2)

VertexIterator vertices()
          O(n)

Methods inherited from class jdsl.graph.ref.AbstractGraph

aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, areAdjacent, connectingEdges, directedEdges, positions, size, undirectedEdges

Methods inherited from class jdsl.core.ref.AbstractPositionalContainer

isEmpty, swapElements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface jdsl.graph.api.InspectableGraph

aCommonVertex, aConnectingEdge, adjacentVertices, adjacentVertices, areAdjacent, areAdjacent, connectingEdges, directedEdges, undirectedEdges

Methods inherited from interface jdsl.core.api.InspectablePositionalContainer

positions

Methods inherited from interface jdsl.core.api.InspectableContainer

isEmpty, size

Methods inherited from interface jdsl.core.api.PositionalContainer

swapElements

Constructor Detail

IncidenceListOrderedGraph

public IncidenceListOrderedGraph()

Method Detail

contains

public boolean contains(Accessor p)
                 throws InvalidAccessorException

O(1)

Specified by:: contains in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Throws:: InvalidAccessorException - if a is null

elements

public ObjectIterator elements()

O(n+m)

Specified by:: elements in interface InspectableContainer

Following copied from interface: jdsl.core.api.InspectableContainer

Returns:: an iterator over all the elements stored in this container

newContainer

public Container newContainer()

O(1)

Specified by:: newContainer in interface Container

Following copied from interface: jdsl.core.api.Container

Returns:: A new, empty Container of the same class as this one.

replaceElement

public java.lang.Object replaceElement(Accessor p,
                                       java.lang.Object newElement)
                                throws InvalidAccessorException

O(1)

Specified by:: replaceElement in interface Container

Following copied from interface: jdsl.core.api.Container

Parameters:: a - Accessor in this container; newElement - to be stored at a
Returns:: old element, previously stored at a
Throws:: InvalidAccessorException - if a is null or does not belong to this container