Graph implementation based on adjacency matrix. More...

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

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

Public Member Functions
	GraphAM (Node nodeGenerator, Edge edgeGenerator, boolean directed)
	Create graph. More...

boolean	isDirected ()

Node	addNode ()

Edge	addEdge (Node source, Node destination)

int	getNumNodes ()

Node	getSomeNode ()

Iterator< Node >	iterator ()

Edge	getEdge (Node source, Node destination)

Vector< Edge >	getInEdges (Node node)

Vector< Edge >	getOutEdges (Node node)

void	removeNode (Node node)

void	removeEdge (Edge edge)

Iterator< Edge >	getEdgeIterator ()

Public Member Functions inherited from aud.graph.AbstractGraph< Node, Edge >
	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...

Protected Member Functions
Node	check (Node node)

Edge	check (Edge edge)

Protected Member Functions inherited from aud.graph.AbstractGraph< Node, Edge >
Node	check (Node node)
	helper: check if node is valid More...

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

Detailed Description

Graph implementation based on adjacency matrix.

The implementation uses a sparse AdjacencyMatrix

See also: AdjacencyMatrix

Definition at line 13 of file GraphAM.java.

Constructor & Destructor Documentation

◆ GraphAM()

aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.GraphAM	(	Node	nodeGenerator,
		Edge	edgeGenerator,
		boolean	directed
	)

Create graph.

Parameters

nodeGenerator	same as for `AbstractGraph#AbstractGraph`
edgeGenerator	same as for `AbstractGraph#AbstractGraph`
directed	`true` for creating a directed graph, `false` for an undirected graph (symmetric `AdjacencyMatrix`)

Definition at line 27 of file GraphAM.java.

                                   {
    super(nodeGenerator,edgeGenerator);
 
    adj_=new AdjacencyMatrix<Edge>(!directed);
    nodes_=new TreeSet<Node>();
  }

Member Function Documentation

◆ addEdge()

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

Definition at line 49 of file GraphAM.java.

                                                              {
    Edge edge=getEdge(check(source),check(destination));
 
    if (edge!=null)
      throw new RuntimeException("edge "+source.index()+
                                 (isDirected() ? "->" : "--")+
                                 destination.index()+" exists");
 
    edge=(Edge) edgeGenerator_.create();
    edge.graph_=this;
    if (!isDirected() && source.index_>destination.index_)   {
      edge.dst_=source;
      edge.src_=destination;
    }
    else {
      edge.src_=source;
      edge.dst_=destination;
    }
 
    adj_.set(source.index_,destination.index_,edge);
 
    return edge;
  }

References aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.check(), aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.getEdge(), and aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.isDirected().

Referenced by aud.example.graph.MaxFlowExample.createGraph(), aud.test.GraphTest.testDouble(), aud.test.GraphTest.testDouble2(), and aud.test.GraphTest.testOther().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ addNode()

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

Definition at line 40 of file GraphAM.java.

                                  {
    Node node=(Node) nodeGenerator_.create();
    node.graph_=this;
    node.index_=nodes_.size();
    nodes_.add(node);
    return node;
  }

Referenced by aud.example.graph.MaxFlowExample.createGraph(), aud.test.GraphTest.testDouble(), aud.test.GraphTest.testDouble2(), and aud.test.GraphTest.testOther().

Here is the caller graph for this function:

◆ check() [1/2]

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

protected

Definition at line 89 of file GraphAM.java.

                                            {
    super.check(edge);  // additional assertion
    assert(adj_.get(edge.src_.index_,edge.dst_.index_)==edge);
    return edge;
  }

◆ check() [2/2]

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

protected

Definition at line 84 of file GraphAM.java.

                                            {
    super.check(node); // additional assertion
    assert(nodes_.contains(node));
    return node;
  }

Referenced by aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.addEdge(), and aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.removeEdge().

Here is the caller graph for this function:

◆ getEdge()

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

Definition at line 80 of file GraphAM.java.

                                                              {
    return adj_.get(source.index_,destination.index_);
  }

Referenced by aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.addEdge(), and aud.example.graph.IterativeDFS1.start().

Here is the caller graph for this function:

◆ getEdgeIterator()

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

Definition at line 113 of file GraphAM.java.

                                                    {
    return adj_.iterator();
  }

◆ getInEdges()

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

Definition at line 95 of file GraphAM.java.

                                                      {
    return adj_.getColumnEntries(check(node).index_);
  }

◆ getNumNodes()

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

Definition at line 73 of file GraphAM.java.

73{ return nodes_.size(); }

Referenced by aud.example.graph.PriorityFirstSearch.start().

Here is the caller graph for this function:

◆ getOutEdges()

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

Definition at line 98 of file GraphAM.java.

                                                       {
    return adj_.getRowEntries(check(node).index_);
  }

◆ getSomeNode()

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

Definition at line 74 of file GraphAM.java.

74{ return nodes_.first(); }

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

Here is the caller graph for this function:

◆ isDirected()

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

Definition at line 35 of file GraphAM.java.

                                        {
    return !adj_.isSymmetricMatrix();
  }

Referenced by aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.addEdge().

Here is the caller graph for this function:

◆ iterator()

Iterator< Node > aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.iterator ( )

Definition at line 76 of file GraphAM.java.

                                             {
    return (Iterator<Node>) nodes_.iterator();
  }

◆ removeEdge()

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

Definition at line 108 of file GraphAM.java.

                                              {
    check(edge);
    adj_.set(edge.src_.index_,edge.dst_.index_,null);
  }

References aud.graph.GraphAM< Node extends AbstractNode, Edge extends AbstractEdge >.check().

Here is the call graph for this function:

◆ removeNode()

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

Definition at line 102 of file GraphAM.java.

                                              {
    adj_.clearColumnAndRow(check(node).index_);
    boolean removed=nodes_.remove(node);
    assert(removed);
  }

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

GraphAM.java

Public Member Functions

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ GraphAM()

Member Function Documentation

◆ addEdge()

◆ addNode()

◆ check() [1/2]

◆ check() [2/2]

◆ getEdge()

◆ getEdgeIterator()

◆ getInEdges()

◆ getNumNodes()

◆ getOutEdges()

◆ getSomeNode()

◆ isDirected()

◆ iterator()

◆ removeEdge()

◆ removeNode()