Interface to a graph. More...

Inheritance diagram for aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >:

Collaboration diagram for aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >:

Classes
class	Edges
	Defines iterator over all edges of anlink AbstractGraph}. More...

Public Member Functions
	AbstractGraph (Node nodeGenerator, Edge edgeGenerator)
	Constructor. More...

abstract boolean	isDirected ()
	Is graph directed? More...

abstract Node	addNode ()
	create and add new node More...

abstract Edge	addEdge (Node source, Node destination)
	Create and add new edge from `source` to `destination`. More...

abstract void	removeNode (Node node)
	Remove node and all its incident and excident edges. More...

abstract void	removeEdge (Edge edge)
	Remove edge. More...

abstract int	getNumNodes ()
	get number of nodes More...

abstract Node	getSomeNode ()
	Get some node. More...

abstract Edge	getEdge (Node source, Node destination)
	Get edge from `source` to `destination`. More...

Edge	ensureEdge (Node source, Node destination)
	Same as `getEdge` but throw if there is no such edge. More...

abstract Vector< Edge >	getInEdges (Node node)
	Get incident edges of node. More...

abstract Vector< Edge >	getOutEdges (Node node)
	Get incident edges of node. More...

int	getInDegree (Node node)
	get number of edges incident to node More...

int	getOutDegree (Node node)
	get number of edges emanating from node More...

int	getDegree (Node node)
	Get total degree. More...

abstract Iterator< Edge >	getEdgeIterator ()
	Get iterator over all edges. More...


Edges	edges ()
	Get Edges instance to obtain iterator. More...

String	toString ()

GraphvizDecorator	getDecorator ()
	get decoration or `null` More...

String	toDot ()
	Get dot representation. More...

String	toDot ()
	Get dot representation. More...

GraphvizDecorator	getDecorator ()
	get decoration or `null` More...

Protected Member Functions
Node	check (Node node)
	helper: check if node is valid More...

Edge	check (Edge edge)
	helper: check if edge is valid More...

Detailed Description

Interface to a graph.

Methods throw an IllegalArgumentException if a given node or edge is invalid, i.e., it equals null, or it is not part of this graph.

Parameters

<Node>	represents a node
<Edge>	represents an e dge

Definition at line 22 of file AbstractGraph.java.

Constructor & Destructor Documentation

◆ AbstractGraph()

aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.AbstractGraph	(	Node	nodeGenerator,
		Edge	edgeGenerator
	)

Constructor.

The constructor takes two objects that serve as "templates" for creating new Node (AbstractNode#create) and Edge (AbstractEdge#create) instances.

Note: The instances are required due to the way how Java generics work (see type erasure). This is different (indeed much simpler but weaker) than, e.g., C++ templates.

Parameters

nodeGenerator	"template" for creating Node instances
edgeGenerator	"template" for creating Edge instances

Definition at line 46 of file AbstractGraph.java.

                                                              {
    nodeGenerator_=nodeGenerator;
    edgeGenerator_=edgeGenerator;
  }

Member Function Documentation

◆ addEdge()

abstract Edge aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.addEdge	(	Node	source,
		Node	destination
	)

abstract

Create and add new edge from source to destination.

For undirected graphs, source and destination may be swapped such that always source.index()<=destination.index().
RuntimeException is thrown if the edge already exists.

Parameters

source	source node
destination	destination node

Returns: edge instance

Exceptions

IllegalArgumentException
RuntimeException

See also: AbstractNode::index

Referenced by aud.util.GraphDemo.main(), aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ addNode()

abstract Node aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.addNode ( )

abstract

create and add new node

Returns: node instance

Referenced by aud.util.GraphDemo.main(), aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ check() [1/2]

Edge aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.check ( Edge edge )

protected

helper: check if edge is valid

Returns: node

Exceptions

IllegalArgumentException

Definition at line 179 of file AbstractGraph.java.

                                  {
    if (edge==null)
      throw new IllegalArgumentException("null edge");
    if (edge.graph_!=this)
      throw new IllegalArgumentException("edge is bound to other graph");
 
    return edge;
  }

◆ check() [2/2]

Node aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.check ( Node node )

protected

helper: check if node is valid

Returns: node

Exceptions

IllegalArgumentException

Definition at line 167 of file AbstractGraph.java.

                                  {
    if (node==null)
      throw new IllegalArgumentException("null node");
    if (node.graph_!=this)
      throw new IllegalArgumentException("node is bound to other graph");
 
    return node;
  }

◆ edges()

Edges aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.edges ( )

Get Edges instance to obtain iterator.

Provided for convenience.

Use as for (edge : graph.edges()) { ... }

Definition at line 203 of file AbstractGraph.java.

203{ return new Edges(this); }

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ ensureEdge()

Edge aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.ensureEdge	(	Node	source,
		Node	destination
	)

Same as getEdge but throw if there is no such edge.

Exceptions

RuntimeException	if there is no such edge
IllegalArgumentException

Returns: edge

Definition at line 115 of file AbstractGraph.java.

                                                       {
    Edge edge=getEdge(source,destination);
    if (edge==null)
      throw new RuntimeException("no such edge "+source.index()+
                                 (isDirected() ? "->" : "--")+
                                 destination.index());
    return edge;
  }

◆ getDecorator()

GraphvizDecorator aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getDecorator ( )

get decoration or null

Implements aud.util.GraphvizDecorable.

Definition at line 215 of file AbstractGraph.java.

                                                    {
    return null;
  }

Referenced by aud.util.GraphDemo.main().

Here is the caller graph for this function:

◆ getDegree()

int aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getDegree ( Node node )

Get total degree.

sum of getInEdges and getOutEdges for directed graphs isDirected
getInEdges (equals getOutEdges} for undirected graphs

Definition at line 151 of file AbstractGraph.java.

                                  {
    if (isDirected())
      return getInDegree(node)+getOutDegree(node);
    else
      return getInDegree(node);
  }

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getEdge()

abstract Edge aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getEdge	(	Node	source,
		Node	destination
	)

abstract

Get edge from source to destination.

Order of arguments is not relevant for undirected graphs.

Exceptions

IllegalArgumentException

Returns: edge or null if there is no such edge

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getEdgeIterator()

abstract Iterator< Edge > aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getEdgeIterator ( )

abstract

Get iterator over all edges.

Edges are traversed in arbitrary order.

Referenced by aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.Edges.iterator().

Here is the caller graph for this function:

◆ getInDegree()

int aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getInDegree ( Node node )

get number of edges incident to node

Definition at line 139 of file AbstractGraph.java.

139{ return getInEdges(node).size(); }

aud.graph.AbstractGraph.getInEdges

abstract Vector< Edge > getInEdges(Node node)

Get incident edges of node.

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getInEdges()

abstract Vector< Edge > aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getInEdges ( Node node )

abstract

Get incident edges of node.

For undirected graphs same as getOutEdges.

Exceptions

IllegalArgumentException

Returns: vector of edges

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getNumNodes()

abstract int aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getNumNodes ( )

abstract

get number of nodes

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getOutDegree()

int aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getOutDegree ( Node node )

get number of edges emanating from node

Definition at line 142 of file AbstractGraph.java.

142{ return getOutEdges(node).size(); }

aud.graph.AbstractGraph.getOutEdges

abstract Vector< Edge > getOutEdges(Node node)

Get incident edges of node.

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getOutEdges()

abstract Vector< Edge > aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getOutEdges ( Node node )

abstract

Get incident edges of node.

For undirected graphs same as getInEdges.

Exceptions

IllegalArgumentException

Returns: vector of edges

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ getSomeNode()

abstract Node aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.getSomeNode ( )

abstract

Get some node.

This may be any node of the graph.

Returns: node

Exceptions

NoSuchElementException (for empty graph)

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ isDirected()

abstract boolean aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.isDirected ( )

abstract

Is graph directed?

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ removeEdge()

abstract void aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.removeEdge ( Edge edge )

abstract

Remove edge.

Exceptions

IllegalArgumentException

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ removeNode()

abstract void aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.removeNode ( Node node )

abstract

Remove node and all its incident and excident edges.

Exceptions

IllegalArgumentException

Referenced by aud.test.GraphTest.testDirectedGraph(), and aud.test.GraphTest.testUndirectedGraph().

Here is the caller graph for this function:

◆ toDot()

String aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.toDot ( )

Get dot representation.

Implements aud.util.Graphvizable.

Definition at line 219 of file AbstractGraph.java.

                                  {
    String edgeOp=(isDirected() ? " -> " : " -- ");
    String dot=(isDirected() ? "digraph " : "graph ")+
      "AbstractGraph {\n";
 
    GraphvizDecorator decorator=getDecorator();
    if (decorator!=null) {
      String d=decorator.getGlobalStyle();
      if (d!=null) dot+=" "+d+";\n";
      d=decorator.getGraphDecoration(this);
      if (d!=null) dot+=" graph ["+d+"];\n";
    }
 
    for (Node node : this) {
      decorator=node.getDecorator();
      dot+=" \""+node.index()+"\" [label=\""+node.getLabel()+"\",";
      dot+=(decorator!=null) ? decorator.getFullNodeDecoration(node) : "shape=circle";
 
      double[] p=node.getPosition();
      if (p!=null) {
        dot+=",pos=\""+p[0]+","+p[1]+"\",pin=true,";
      }
 
      dot+="];\n";
    }
 
    dot+="\n\n";
 
    for (Edge edge : this.edges()) {
      decorator=edge.getDecorator();
      dot+=" \""+edge.source().index()+"\""+edgeOp+
           "\""+edge.destination().index()+"\" ";
      String label=edge.getLabel();
      dot+=(label!=null) ? "[label=\""+label+"\"," : "[";
      dot+=edge.hasWeight() ? "weight="+edge.getWeight()+"," : "";
      dot+=edge.hasWeight() ? "len="+edge.getWeight()+"," : "";
      dot+=(decorator!=null) ? decorator.getFullEdgeDecoration(edge) : "";
      dot+="];\n";
    }
 
    dot+="\n}\n";
    //System.out.println(dot);
    return dot;
  }

References aud.util.GraphvizDecorator.getFullEdgeDecoration(), aud.util.GraphvizDecorator.getFullNodeDecoration(), aud.util.GraphvizDecorator.getGlobalStyle(), and aud.util.GraphvizDecorator.getGraphDecoration().

Referenced by aud.example.graph.GraphParser.main().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ toString()

String aud.graph.AbstractGraph< Node extends AbstractNode, Edge extends AbstractEdge >.toString ( )

Definition at line 205 of file AbstractGraph.java.

                                     {
    String rv="nodes:\n";
    for (Node node : this)
      rv+=" "+node.toString()+"\n";
    rv+="edges:\n";
    for (Edge edge : this.edges())
      rv+=" "+edge.toString()+"\n";
    return rv;
  }

The documentation for this class was generated from the following file:

AbstractGraph.java

Classes

Public Member Functions

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ AbstractGraph()

Member Function Documentation

◆ addEdge()

◆ addNode()

◆ check() [1/2]

◆ check() [2/2]

◆ edges()

◆ ensureEdge()

◆ getDecorator()

◆ getDegree()

◆ getEdge()

◆ getEdgeIterator()

◆ getInDegree()

◆ getInEdges()

◆ getNumNodes()

◆ getOutDegree()

◆ getOutEdges()

◆ getSomeNode()

◆ isDirected()

◆ removeEdge()

◆ removeNode()

◆ toDot()

◆ toString()