- Introduction
- Full Documentation
- Practical examples with Methods
- Practical examples with Classes
- Like it / Hate it!
- Projects that used this API
- References
"[Graph API] website" is a standard Java library that provides various methods and classes that help users to implement graphs. In this package we cover the basics of [Graph Theory] website1 by providing useful helper functions and important algorithms. Keep reading this guide to learn more about the different operations that can be performed using the API. "Graph API" has a very practical functionallity and it is very easy to use it in different applications. Clients can use the "Graph API" to program diverse tools with strong performance. In this library we tried to combine all essential ideas of Graph Theory so all the users can easily implement their applications using this API.
This package represents a general [unlabeled graph] website2 whose vertices are denoted by positive integers. A graph may be directed or undirected. For an undirected graph, outgoing and incoming edges are the same. Graphs may have self edges, but no multi-edges (edges with the same end points). Edges in a Graph are ordered by the sequence in which they were added. If you are not familiar with Graph Theory, we strongly recommend to run through an introductory tutorial before using this package. You can find detailed information about this in "Full Documentation" section.
"Graph API" " is free and unencumbered software released into the public domain. This libary is under GNU GENERAL PUBLIC LICENSE. In order to use this package click on "Download ZIP" and unpack it in a directory named "graph" created by yourself in your workspace.
We devided this section into two subparts. In the first part we provide all methods provided by this API. For more information you can look at Graph.java file. In the second part we described all classes provided by this package that help users to implement important algorithms related to Graph Theory, such as [BFS] BFSwebsite, [DFS] DFSwebsite and [Shortest Path] Pathwebsite. You can explore Traversal.java BreadthFirstTraversal.java and DepthFirstTraversal.java for exploring the implementation details for graph traversals and ShortestPaths.java and SimpleShortestPaths.java for finding the Shortest Path. In this package you can also find some JUnit tests, which were created for documentation purposes. You are free to remove them. In the next two sections you can find useful examples of using provided methods and classes.
- vertexSize() - Returns the number of vertices in me.
- maxVertex() - Returns my maximum vertex number, or 0 if I am empty.
- edgeSize() - Returns the number of edges in me.
- isDirected() - Returns true iff I am a directed graph.
- outDegree(int v) - Returns the number of outgoing edges incident to V, or 0 if V is not one of my vertices.
- inDegree(int v) - Returns the number of incoming edges incident to V, or 0 if V is not one of my vertices.
- degree(int v) - Returns outDegree(V). This is simply a synonym, intended for use in undirected graphs.
- contains(int u) - Returns true iff U is one of my vertices.
- contains(int u, int v) - Returns true iff U and V are my vertices and I have an edge (U, V).
- add() - Returns a new vertex and adds it to me with no incident edges. The vertex number is always the smallest integer >= 1 that is not currently one of my vertex numbers.
- add(int u, int v) - Add an edge incident on U and V. If I am directed, the edge is directed (leaves U and enters V). Assumes U and V are my vertices. Has no effect if there is already an edge from U to V. Returns U.
- remove(int v) - Remove V, if present, and all adjacent edges.
- remove(int u, int v) - Remove edge (U, V) from me, if present.
- vertices() - Returns an Iteration over all vertices in numerical order.
- successor(int v, int k) - Return successor K of V, numbering from 0, or 0 if there is no such successor (or V is not a vertex).
- predecessor(int v, int k) - Return predecessor K of V, numbering from 0, or 0 if there is no such predecessor. Assumes V is one of my vertices.
- neighbor(int v, int k) - Return neighbor K of V, numbering from 0, or 0 if there is no such neighbor. Assumes V is one of my vertices. This is a synonym for successor(v, k).
- successors(int v) - Returns an iteration over all successors of V in the order the edges to them were added. Empty if V is not my vertex.
- predecessors(int v) - Returns an iteration over all predecessors of V in the order the edges to them were added. Empty if V is not my vertex.
- neighbors(int v) - Returns successors(V). This is a synonym typically used on undirected graphs.
- edges() - Returns an iteration over all edges in me. Edges are returned as two-element arrays (u, v), which are directed if the graph is. In fact, the same array is used for each, and modified by the next() method of the iteration.
- mine(int v) - Return true iff V is one of my vertices.
- checkMyVertex(int v) - Throw exception if V is not one of my vertices.
- edgeId(int u, int v) - Returns a unique positive identifier for the edge (U, V), if it is present, or 0 otherwise. The value of edgeId(v0, v1) does not change while the edge is present. It is used in LabeledGraph to number edges so that their labels are easy to retrieve and set.
- DirectedGraph - Represents a general unlabeled directed graph whose vertices are denoted by positive integers. Graphs may have self edges.
- UndirectedGraph - Represents an undirected graph. Out edges and in edges are not distinguished. Likewise for successors and predecessors.
- ShortestPaths - The shortest paths through an edge-weighted graph. By overrriding methods getWeight, setWeight, getPredecessor, and setPredecessor, the client can determine how to represent the weighting and the search results. By overriding estimatedDistance, clients can search for paths to specific destinations using A* search.
- SimpleShortestPaths - A partial implementation of ShortestPaths that contains the weights of the vertices and the predecessor edges. The client needs to supply only the two-argument getWeight method.
- Traversal - Implements a generalized traversal of a graph. At any given time, there is a particular collection of untraversed vertices---the "fringe." Traversal consists of repeatedly removing an untraversed vertex from the fringe, visting it, and then adding its untraversed successors to the fringe. Generally, the client will extend Traversal. By overriding the visit method, the client can determine what happens when a node is visited. By supplying an appropriate type of Queue object to the constructor, the client can control the behavior of the fringe. By overriding the shouldPostVisit and postVisit methods, the client can arrange for post-visits of a node (as in depth-first search). By overriding the reverseSuccessors and processSuccessor methods, the client can control the addition of neighbor vertices to the fringe when a vertex is visited. Traversals may be interrupted or restarted, remembering the previously marked vertices.
- BreadthFirstTraversal - Implements a breadth-first traversal of a graph. Generally, the client will extend this class, overriding the visit method as desired (by default, it does nothing).
- DepthFirstTraversal - Implements a depth-first traversal of a graph. Generally, the client will extend this class, overriding the visit and postVisit methods, as desired (by default, they do nothing).
In order to use methods and classes from this package you need to import them in your files. If you assume that you put all the files of this package in a directory called "graph", here are some examples of importing classes from this library:
import graph.LabeledGraph;
import graph.DirectedGraph;
import graph.DepthFirstTraversal;
a. Declaring Directed graph: UndirectedGraph ug = new UndirectedGraph();
b. Declaring Undirected graph: DirectedGraph dg = new DirectedGraph();
c. Adding vertices to graph. (Doesn't really matter whether we take directed or Undirected Graph).
UndirectedGraph ug = new UndirectedGraph();
ug.add();
ug.add();
ug.add();
ug.add();
...
d. Adding edges to graph. In this example we will add an edge between vertices 1 and 3.
DirectedGraph dg = new DirectedGraph();
dg.add();
dg.add();
dg.add();
dg.add(1, 3);
...
e. Removing a vertex from a graph. (Same works for DirectedGraphs too).
UndirectedGraph ug = new UndirectedGraph();
ug.add();
ug.add();
ug.add();
ug.remove(1);
ug.remove(3);
f. Removing an edge from two vertices. In this example we will remove an edge from vertices 1 and 3.
DirectedGraph dg = new DirectedGraph();
dg.add();
dg.add();
dg.add();
dg.add(1, 3);
dg.remove(1, 3);
g. A JUnit test samples that tests successors of the graph.
@Test
public void dtestSuccessor() {
DirectedGraph ug = new DirectedGraph();
ug.add();
ug.add();
ug.add();
ug.add();
ug.add(1, 2);
ug.add(1, 3);
ug.add(1, 4);
ug.add(3, 4);
assertEquals(2, ug.successor(1, 0));
assertEquals(3, ug.successor(1, 1));
assertEquals(4, ug.successor(1, 2));
assertEquals(0, ug.successor(1, 3));
assertEquals(0, ug.successor(5, 0));
assertEquals(0, ug.successor(2, 0));
assertEquals(4, ug.successor(3, 0));
assertEquals(0, ug.successor(4, 0));
}
h. An example for using vertices() method:
UndirectedGraph ug = new UndirectedGraph();
ug.add();
ug.add();
ug.add();
ug.add();
ArrayList<Integer> result = new ArrayList<Integer>();
for (int x : ug.vertices()) {
result.add(x);
}
...
i. A JUnit test sample for edgeSize()
@Test
public void testDedgesize() {
DirectedGraph ug = new DirectedGraph();
ug.add();
ug.add();
ug.add();
ug.add();
ug.add(1, 3);
ug.add(3, 1);
ug.add(2, 3);
assertEquals(3, ug.edgeSize());
}
j. A JUnit test that checks contains method:
@Test
public void utest() {
UndirectedGraph ug = new UndirectedGraph();
ug.add();
ug.add();
ug.add(1, 2);
assertTrue(ug.contains(1, 2));
assertFalse(ug.contains(1, 3));
ug.add();
ug.add(1, 3);
assertTrue(ug.contains(1, 3));
assertFalse(ug.contains(2, 3));
ug.add();
ug.add(2, 3);
assertTrue(ug.contains(2, 3));
ug.add(3, 4);
assertTrue(ug.contains(3, 4));
assertTrue(ug.contains(3, 1));
}
a. A class that generates the idea of BFS:
public class BFSTest extends BreadthFirstTraversal {
BFSTest(Graph G) {
super(G);
visitedData = new ArrayList<Integer>();
postVisitData = new ArrayList<Integer>();
}
@Override
protected boolean visit(int v) {
visitedData.add(v);
return true;
}
@Override
protected boolean postVisit(int v) {
postVisitData.add(v);
return true;
}
protected ArrayList<Integer> getvisitedData() {
return visitedData;
}
protected ArrayList<Integer> getpostVisitData() {
return postVisitData;
}
private ArrayList<Integer> visitedData;
private ArrayList<Integer> postVisitData;
}
b. A class that generates the idea of BFS:
public class DFSTest extends DepthFirstTraversal {
DFSTest(Graph G) {
super(G);
visited = new ArrayList<Integer>();
postVisited = new ArrayList<Integer>();
}
@Override
protected boolean visit(int v) {
visited.add(v);
return true;
}
@Override
protected boolean postVisit(int v) {
postVisited.add(v);
return true;
}
protected ArrayList<Integer> getVisited() {
return visited;
}
protected ArrayList<Integer> getpostVisited() {
return postVisited;
}
private ArrayList<Integer> visited;
private ArrayList<Integer> postVisited;
}
c. A class that generates the algorithm of Shortest Path.
public class TestShortestPath extends SimpleShortestPaths {
public TestShortestPath(Graph G, int source, int dest) {
super(G, source, dest);
weightData = new HashMap<Integer, Integer>();
}
public void setWeight(int u, int v, int weight) {
int id = _G.edgeId(u, v);
weightData.put(id, weight);
}
@Override
public double getWeight(int u, int v) {
int id = _G.edgeId(u, v);
return weightData.get(id);
}
private HashMap<Integer, Integer> weightData;
}
This API has been written by [Rafayel Mkrtchyan] profile at University of California, Berkeley in December, 2014. I would like to thank my professors Paul Hilfinger and Josh Hug, who teach "Data Structures" course at UC Berkeley, for providing fundamental assistance in completing this project. For additional comments and suggestions you can contact rafamian@berkeley.edu. I don't claim to be perfect so if you find a bug in this library, please send me an email preferably with a test that revealed that error so that I know what I need to fix.
Here is the list of some open-source projects that used this API:
| [Topographic Maps] web1 | [Your Repo Here] setup | [Your Repo Here] roadmap | [Your Repo Here] contributing | [Your Repo Here] web5link |
|---|---|---|---|---|
| [![i1] techdocs-image] techdocs | [![i2] setup-image] setup | [![i3] roadmap-image] roadmap | [![i4] contributing-image] contributing | [![i5] image-5] web5 |
- "Graph Theory" by Keijo Ruohonen - http://math.tut.fi/~ruohonen/GT_English.pdf
- MIT Lecture 6: Graph Theory and Coloring - http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-fall-2010/video-lectures/lecture-6-graph-theory-and-coloring/
- Graph Theory - An Introduction! - https://www.youtube.com/watch?v=HmQR8Xy9DeM
- Graphs and Graph Theory - http://www.ccs3.lanl.gov/mega-math/gloss/graph/gr.html
- "Introduction to Graph Theory and Applications" by Tero Harju - http://cs.bme.hu/fcs/graphtheory.pdf
- "Graph Theory and Applications" - http://www.hamilton.ie/ollie/Downloads/Graph.pdf
- "Basic Concepts in Graph Theory" - http://cseweb.ucsd.edu/~gill/BWLectSite/Resources/C2U4GT.pdf
- "Introduction to Graph Theory" - http://www.math.utah.edu/mathcircle/notes/MC_Graph_Theory.pdf
- "Data Structures Into Java" by Paul Hilfinger - http://inst.eecs.berkeley.edu/~cs61b/fa07/book2/data-structures.pdf
- "Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory" by Luca Trevisan - http://www.eecs.berkeley.edu/~luca/books/expanders.pdf