The Graph API is very simple. To represent a Graph G =(V,E), you create a Graph object and either add Node and Edge objects to it, or use the GraphIO class to to read a graph file.
A sequence for creating an undirected graphs may look like this:
Graph g1 = new Graph(false); Node n11 = g1.addNode(); Node n12 = g1.addNode(); Node n13 = g1.addNode(); Edge ex1 = g1.addEdge(n11, n12); Edge ex2 = g1.addEdge(n12, n13); Edge ex3 = g1.addEdge(n11, n13); g1.removeNode(n11); |
Once more, visualization is done via DOT:
g1.showDot( "g1" ); |
Notice that removing n11 also removed the two edges attached to it.
Here is a directed graph:
Graph g2 = new Graph(true); Node n21 = g2.addNode(); Node n22 = g2.addNode(); Node n23 = g2.addNode(); Edge e1 = g2.addEdge(n21, n22); Edge e3 = g2.addEdge(n22, n21); // NOT duplicate edge (directed graph) |
Nodes and edges are stored in java Vectors:
Graph g = .... for (Enumeration e = g.getEdges().elements() ; e.hasMoreElements() ;) { Edge edge = (Edge) e.nextElement(); if(edge.n1 == edge.n2 ) System.out.println("self-loop found"); } |
In each node, incoming and outgoing arcs are stored as two linked lists:
Node n = .... Edge e = n.firstOut; // outgoing arcs while(e != null) { do_somthing(e); e = e.next; } e = n.firstIn; // incoming arcs while(e != null) { do_somthing(e); e = e.prev; } |
The Node and Edge object have some extra member variables for storing your intermediate data during execution of algorithms. These members are called extran and maybe overwritten by other algorithms (your or JDD's internal algorithms), so be carefull. There are also other usefull members such as flags, weight and id. See also the AttributeExplorer class
The following implementation of a well-known algorithm demonstrates the correct use of these members:
public static void kruskal(Graph g) { EdgeHeap eh = new EdgeHeap(g, true); DisjointSet ds = new DisjointSet( g.numOfNodes() ); int offset = 0, set_flag = Edge.FLAGS_STRONG, remove_flag = ~Edge.FLAGS_STRONG; for (Enumeration e = g.getNodes().elements() ; e.hasMoreElements() ;) ((Node) e.nextElement()).extra1 = offset++; for (Enumeration e = g.getEdges().elements() ; e.hasMoreElements() ;) ((Edge) e.nextElement()).flags &= remove_flag; while(!eh.isEmpty() ) { Edge e = (Edge) eh.pop(); int r1 = ds.find(e.n1.extra1); int r2 = ds.find(e.n2.extra1); if( r1 != r2 ) { ds.union(r1, r2); e.flags |= set_flag; } } } |
Here, instead of
for (Enumeration e = g.getEdges().elements() ; e.hasMoreElements() ;) ((Edge) e.nextElement()).flags &= remove_flag; |
AttributeExplorer.resetEdgeFlag(g, Edge.FLAGS_STRONG); |
Class jdd.util.graph.SimpleAlgorithms | ||
return type | method | parameters |
void | internal_test | |
java.util.Vector | divide | ( jdd.util.graph.Graph ) |
int | level_n_degree | ( jdd.util.graph.Node, int, java.util.AbstractSet ) |
boolean | is_bipartie | ( jdd.util.graph.Graph ) |
boolean | is_connected | ( jdd.util.graph.Graph ) |
int | number_of_islands | ( jdd.util.graph.Graph ) |
boolean | is_tree | ( jdd.util.graph.Graph ) |
jdd.util.math.BitMatrix | transistive_closure | ( jdd.util.graph.Graph ) |
Some other simple operations are found in GraphOperation. Currently we support:
Class jdd.util.graph.GraphOperation | ||
return type | method | parameters |
jdd.util.graph.Graph | clone | ( jdd.util.graph.Graph ) |
jdd.util.graph.Graph | join | ( jdd.util.graph.Graph, jdd.util.graph.Graph ) |
void | connection | ( jdd.util.graph.Graph, jdd.util.graph.Node, jdd.util.graph.Node ) |
void | disconnect | ( jdd.util.graph.Graph, jdd.util.graph.Node, jdd.util.graph.Node ) |
jdd.util.graph.Graph | union | ( jdd.util.graph.Graph, jdd.util.graph.Graph ) |
void | internal_test | |
jdd.util.graph.Graph | hajos_construction | ( jdd.util.graph.Graph, jdd.util.graph.Node, jdd.util.graph.Node, jdd.util.graph.Graph, jdd.util.graph.Node, jdd.util.graph.Node ) |
void | contraction | ( jdd.util.graph.Graph, jdd.util.graph.Node, jdd.util.graph.Node ) |
jdd.util.graph.Node | heavyNode | ( jdd.util.graph.Graph, boolean ) |
jdd.util.graph.Node | lightNode | ( jdd.util.graph.Graph, boolean ) |
Class jdd.util.graph.ApproximationAlgorithms | ||
return type | method | parameters |
void | internal_test | |
void | approx_vertex_cover_ED | ( jdd.util.graph.Graph ) |
void | approx_vertex_cover_MDG | ( jdd.util.graph.Graph ) |
Class jdd.util.graph.ShortestPath | ||
return type | method | parameters |
void | internal_test | |
jdd.util.graph.Tree | bellman_ford | ( jdd.util.graph.Graph, jdd.util.graph.Node ) |
java.util.Vector | dijkstra | ( jdd.util.graph.Graph, jdd.util.graph.Node ) |
jdd.util.math.Matrix | floyd_warshall | ( jdd.util.graph.Graph ) |
Class jdd.util.graph.MinimumSpanningTree | ||
return type | method | parameters |
void | internal_test | |
void | kruskal | ( jdd.util.graph.Graph ) |
Class jdd.util.graph.StronglyConnectedComponent | ||
return type | method | parameters |
void | internal_test | |
jdd.util.graph.Partition | tarjan | ( jdd.util.graph.Graph, jdd.util.graph.Node ) |
Class jdd.util.graph.WeakTopologicalOrdering | ||
return type | method | parameters |
void | internal_test | |
jdd.util.graph.Topology | bourdoncle_PCG | ( jdd.util.graph.Graph ) |
jdd.util.graph.Topology | bourdoncle | ( jdd.util.graph.Graph, jdd.util.graph.Node ) |
jdd.util.graph.Topology | bourdoncle | ( jdd.util.graph.Graph ) |
Here is a example of a sequence that uses all three formats:
Graph g = GraphIO.loadEdgeList("x.pcg"); GraphIO.saveDIMACS(g, "x.DIMACS"); GraphIO.saveXML(g2,"x.xml"); |
A complete graph K5 is created by Factory.complete(5):
A directed tree is created by Factory.tree():
A permutation tree is created by Factory.permutation():
Here is a path of length 5, created by Factory.path(5):
Here is a circle of length 5, created by Factory.circle(5):
A finally, the complete bipartie graph K2,3 , created by the call Factory.complete_bipartie(2,3):