Graphs/Java/Adjacency Map - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:26:56Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

Admin at 06:30, 17 October 2017

2017-10-17T06:30:43Z

← Older revision		Revision as of 06:30, 17 October 2017
Line 1:		Line 1:
			For a more lightweight implementation, see [[Graphs/Java/Adjacency Map Lite]]

	Adjacency Map Graph class implementation: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures		Adjacency Map Graph class implementation: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures
	* The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.		* The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.

Admin: /* Adjacency Map Graph Class */

2017-10-17T06:30:23Z

Adjacency Map Graph Class

← Older revision		Revision as of 06:30, 17 October 2017
Line 165:		Line 165:

	/** Construct an empty graph. */		/** Construct an empty graph. */
	public ~~AdjMapGraph2~~(boolean directed) {		public AdjMapGraph(boolean directed) {
	isDirected = directed;		isDirected = directed;
	vertexList = new LinkedList<Vertex<V>>();		vertexList = new LinkedList<Vertex<V>>();

Admin: /* Adjacency Map Graph */

2017-08-22T00:09:04Z

Adjacency Map Graph

Show changes

Admin at 00:04, 22 August 2017

2017-08-22T00:04:50Z

@@ Line 2: / Line 2: @@
 * The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.
 * The AdjMapGraph2.java class implements a validate method, gracefully switches between the interface types IVertex/IEdge and the classes Vertex/Edge, and is a demonstration of good API implementation. Use it.
 ==Overview==
@@ Line 52: / Line 54: @@
+	}
 </pre>

Admin: /* Interface Classes */

2017-08-22T00:00:02Z

Interface Classes

← Older revision		Revision as of 00:00, 22 August 2017
Line 7:		Line 7:
	Before going through the details of the implementation, let's give an overview of the inheritance/interface/class logistics. Unfortunately, this step is a Catch-22: making a wrong decision at this step will cause lots of headaches and extra work, even for a small and simple class, but you really have to implement everything to have a good sense of how it should be done. Practice makes perfect.		Before going through the details of the implementation, let's give an overview of the inheritance/interface/class logistics. Unfortunately, this step is a Catch-22: making a wrong decision at this step will cause lots of headaches and extra work, even for a small and simple class, but you really have to implement everything to have a good sense of how it should be done. Practice makes perfect.

	===~~Interface~~ Classes===		===Abstract Vertex and Edge Classes===

	There are three interfaces defined: IGraph, IVertex, and IEdge.		We implement abstract vertex and edge classes via interfaces.
	* Link to IGraph: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IGraph.~~java~~
			There are three interfaces defined: IGraph, IVertex, and IEdge. We'll just focus on the latter two.
	* Link to IVertex: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IVertex.java		* Link to IVertex: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IVertex.java
	* Link to IEdge: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IEdge.java		* Link to IEdge: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IEdge.java

	These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.		These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.

			===Concrete Vertex and Edge Classes===

	Complementing this are two classes, Vertex and Edge, implemented inside of the Adjacency Map Graph class. These implement specific functionality that is neglected by the interfaces.		Complementing this are two classes, Vertex and Edge, implemented inside of the Adjacency Map Graph class. These implement specific functionality that is neglected by the interfaces.

Admin: /* Interface Classes */

2017-08-21T23:58:59Z

Interface Classes

← Older revision		Revision as of 23:58, 21 August 2017
Line 14:		Line 14:
	* Link to IEdge: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IEdge.java		* Link to IEdge: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IEdge.java

	These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.		These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.

			Complementing this are two classes, Vertex and Edge, implemented inside of the Adjacency Map Graph class. These implement specific functionality that is neglected by the interfaces.
			* Link to Vertex class: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L21
			* Link to Edge class: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L59

	The only catch is, any time we need to use the specific functionality of the Vertex and Edge classes implemented inside of the Adjacency Map Graph class, we need a validate() method to perform a safe cast from the generic interface type to the specific internal class type. Here is an example of such a method that converts a pointer of type IVertex (the generic interface type) to a pointer of type Vertex (the internal implementation of the Vertex class inside the Adjacency Map Graph class), and same with an IEdge to Edge validate method:		The only catch is, any time we need to use the specific functionality of the Vertex and Edge classes implemented inside of the Adjacency Map Graph class, we need a validate() method to perform a safe cast from the generic interface type to the specific internal class type. Here is an example of such a method that converts a pointer of type IVertex (the generic interface type) to a pointer of type Vertex (the internal implementation of the Vertex class inside the Adjacency Map Graph class), and same with an IEdge to Edge validate method:
			* Link to validate vertex method: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L104
			* Link to validate edge method: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L118

	<pre>		<pre>

Admin: Created page with "Adjacency Map Graph class implementation: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures * The AdjMapGraph.java class does not implement a validate me..."

2017-08-21T23:56:40Z

Created page with "Adjacency Map Graph class implementation: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures * The AdjMapGraph.java class does not implement a validate me..."

New page

Adjacency Map Graph class implementation: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures
* The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.
* The AdjMapGraph2.java class implements a validate method, gracefully switches between the interface types IVertex/IEdge and the classes Vertex/Edge, and is a demonstration of good API implementation. Use it.

==Overview==

Before going through the details of the implementation, let's give an overview of the inheritance/interface/class logistics. Unfortunately, this step is a Catch-22: making a wrong decision at this step will cause lots of headaches and extra work, even for a small and simple class, but you really have to implement everything to have a good sense of how it should be done. Practice makes perfect.

===Interface Classes===

There are three interfaces defined: IGraph, IVertex, and IEdge.
* Link to IGraph: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IGraph.java
* Link to IVertex: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IVertex.java
* Link to IEdge: https://charlesreid1.com:3000/cs/java/src/master/graphs/data-structures/IEdge.java

These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.

The only catch is, any time we need to use the specific functionality of the Vertex and Edge classes implemented inside of the Adjacency Map Graph class, we need a validate() method to perform a safe cast from the generic interface type to the specific internal class type. Here is an example of such a method that converts a pointer of type IVertex (the generic interface type) to a pointer of type Vertex (the internal implementation of the Vertex class inside the Adjacency Map Graph class), and same with an IEdge to Edge validate method:

<pre>
@SuppressWarnings({"unchecked"})
private Vertex<V> validate(IVertex<V> v) {
if (!(v instanceof Vertex)) {
throw new IllegalArgumentException("Invalid vertex");
}

// Safe cast:
Vertex<V> vert = (Vertex<V>) v;

return vert;
}

@SuppressWarnings({"unchecked"})
private Edge<E> validate(IEdge<E> e) {
if (!(e instanceof Edge)) {
throw new IllegalArgumentException("Invalid edge");
}

// Safe cast:
Edge<E> edge = (Edge<E>) e;

return edge;
}
</pre>

← Older revision		Revision as of 03:26, 9 October 2019
Line 1:		Line 1:
	For a more lightweight implementation, see [[Graphs/Java/Adjacency Map Lite]]		For a more lightweight implementation, see [[Graphs/Java/Adjacency Map Lite]]

	Adjacency Map Graph class implementation: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures		Adjacency Map Graph class implementation: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures
	* The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.		* The AdjMapGraph.java class does not implement a validate method, uses the Vertex and Edge classes directly, and is rough around the edges. Don't use it.
	* The AdjMapGraph2.java class implements a validate method, gracefully switches between the interface types IVertex/IEdge and the classes Vertex/Edge, and is a demonstration of good API implementation. Use it.		* The AdjMapGraph2.java class implements a validate method, gracefully switches between the interface types IVertex/IEdge and the classes Vertex/Edge, and is a demonstration of good API implementation. Use it.

	Link to code: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/		Link to code: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/

	==Overview==		==Overview==
Line 16:		Line 16:

	There are three interfaces defined: IGraph, IVertex, and IEdge. We'll just focus on the latter two.		There are three interfaces defined: IGraph, IVertex, and IEdge. We'll just focus on the latter two.
	* Link to IVertex: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/IVertex.java		* Link to IVertex: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/IVertex.java
	* Link to IEdge: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/IEdge.java		* Link to IEdge: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/IEdge.java

	These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.		These are minimally functional (but still useful) interfaces - useful to use as types for pointers to vertices and edges. Many of the methods in the Adjacency Map Graph class refer to variables of type IVertex and IEdge. These are public classes available to anyone, and prevent classes creating/using an Adjacency Map Graph object (or any other graph object that uses these interfaces) from having to deal with the specific internal implementations. Any algorithms that utilize generic vertex and edge methods, and program to the interface, can also be re-utilized by other graph types using the same IVertex/IEdge interfaces.
Line 24:		Line 24:

	Complementing this are two classes, Vertex and Edge, implemented inside of the Adjacency Map Graph class. These implement specific functionality that is neglected by the interfaces.		Complementing this are two classes, Vertex and Edge, implemented inside of the Adjacency Map Graph class. These implement specific functionality that is neglected by the interfaces.
	* Link to Vertex class: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L21		* Link to Vertex class: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L21
	* Link to Edge class: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L59		* Link to Edge class: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L59

	The only catch is, any time we need to use the specific functionality of the Vertex and Edge classes implemented inside of the Adjacency Map Graph class, we need a validate() method to perform a safe cast from the generic interface type to the specific internal class type. Here is an example of such a method that converts a pointer of type IVertex (the generic interface type) to a pointer of type Vertex (the internal implementation of the Vertex class inside the Adjacency Map Graph class), and same with an IEdge to Edge validate method:		The only catch is, any time we need to use the specific functionality of the Vertex and Edge classes implemented inside of the Adjacency Map Graph class, we need a validate() method to perform a safe cast from the generic interface type to the specific internal class type. Here is an example of such a method that converts a pointer of type IVertex (the generic interface type) to a pointer of type Vertex (the internal implementation of the Vertex class inside the Adjacency Map Graph class), and same with an IEdge to Edge validate method:
	* Link to validate vertex method: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L104		* Link to validate vertex method: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L104
	* Link to validate edge method: https://charlesreid1.com~~:3000~~/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L118		* Link to validate edge method: https://git.charlesreid1.com/cs/java/src/master/graphs/data-structures/AdjMapGraph2.java#L118

	<pre>		<pre>