Graphs/Java/Adjacency Map Lite - Revision history

Admin: /* Java Code */

2017-10-17T10:26:02Z

Java Code

← Older revision		Revision as of 10:26, 17 October 2017
Line 63:		Line 63:

	<pre>		<pre>
			public class RoadsAndLibraries {

	static class Graph {		static class Graph {
	~~HashMap~~<~~Integer,~~ Vertex> ~~vertexMap~~;		ArrayList<Vertex> vertexList;
	ArrayList<Edge> edgeList;		ArrayList<Edge> edgeList;

	public Graph() {		public Graph() {
	~~vertexMap~~ = new ~~HashMap~~<>();		vertexList = new ArrayList<>();
	edgeList = new ArrayList<>();		edgeList = new ArrayList<>();
	}		}

	public void ~~addVertex~~(int i) {		public void init(int n) {
	~~// To add a vertex, just add it to the master vertex map~~		for(int i=0; i<n; i++) {
	~~// along with its identifying integer.~~		Vertex v = new Vertex(i+1);
	Vertex v = new Vertex(i);		vertexList.add(v);
	~~vertexMap~~.~~put~~(i,v);		}
	}		}

Line 84:		Line 86:
	// - then create the edge,		// - then create the edge,
	// - then add vertex i and vertex j as neighbors.		// - then add vertex i and vertex j as neighbors.
	Vertex vi = ~~vertexMap~~.get(i);		Vertex vi = vertexList.get(i-1);
	Vertex vj = ~~vertexMap~~.get(j);		Vertex vj = vertexList.get(j-1);
	Edge e = new Edge(vi, vj);		Edge e = new Edge(vi, vj);
	vi.addNeighbor(vj, e);		vi.addNeighbor(vj, e);
Line 95:		Line 97:
	StringBuffer sb = new StringBuffer();		StringBuffer sb = new StringBuffer();
	sb.append("Vertices:\n");		sb.append("Vertices:\n");
	for( ~~Integer~~ i ~~: vertexMap~~.~~keySet~~() ) {		for(int i=0; i<vertexList.size(); i++) {
	sb.append(" ");		sb.append(" ");
	sb.append(i);		sb.append(i);
Line 123:		Line 125:
	this.element = element;		this.element = element;
	neighborList = new HashMap<>();		neighborList = new HashMap<>();
			}
			public Collection<Edge> outgoingEdges() {
			return neighborList.values();
	}		}
	public void addNeighbor(Vertex v, Edge e) {		public void addNeighbor(Vertex v, Edge e) {
Line 129:		Line 134:
	public int getElement() {		public int getElement() {
	return this.element;		return this.element;
			}
			public String toString() {
			return Integer.toString(element);
	}		}
	}		}
Line 145:		Line 153:
	public ArrayList<Vertex> getEndpoints() {		public ArrayList<Vertex> getEndpoints() {
	return endpoints;		return endpoints;
			}
			public boolean hasEndpoint(Vertex v) {
			if(v.getElement() == endpoints.get(0).getElement() ) {
			return true;
			} else if(v.getElement() == endpoints.get(1).getElement() ) {
			return true;
			} else {
			return false;
			}
	}		}
	public Vertex getOpposite(Vertex v) {		public Vertex getOpposite(Vertex v) {
	if(v.~~equals~~(endpoints.get(0))) {		if(v.getElement() == endpoints.get(0).getElement() ) {
	return endpoints.get(1);		return endpoints.get(1);
	} else if(v.~~equals~~(endpoints.get(1))) {		} else if(v.getElement() == endpoints.get(1).getElement() ) {
	return endpoints.get(0);		return endpoints.get(0);
	} else {		} else {
			System.out.println("Endpoint 0: "+endpoints.get(0));
			System.out.println("Endpoint 1: "+endpoints.get(1));
			System.out.println("Checking for vertex: "+v.getElement());
	throw new IllegalArgumentException("Vertex not an endpoint of this edge.");		throw new IllegalArgumentException("Vertex not an endpoint of this edge.");
	}		}
			}
			public String toString() {
			StringBuffer sb = new StringBuffer();
			sb.append("(Edge ");
			sb.append(endpoints.get(0).getElement());
			sb.append("-");
			sb.append(endpoints.get(1).getElement());
			sb.append(")");
			return sb.toString();
	}		}
	}		}
	}
	</pre>		</pre>

Admin: /* Class Implementations */

2017-10-17T10:25:05Z

Class Implementations

← Older revision		Revision as of 10:25, 17 October 2017
Line 13:		Line 13:

	Graph class:		Graph class:
			* Fields: list of vertices, list of edges
	* Constructor: initializes list of vertices, list of edges		* Constructor: initializes list of vertices, list of edges
	* Add vertex method (identified by integers)		* Init: given a number of vertices N, this creates each vertex and populates the list of vertices with them
			* Add vertex method (identified by integers, which are used to access the list of vertices)
	* Add edge method (takes two integers)		* Add edge method (takes two integers)
	* ~~(Optional) Depth~~ first search (~~or any other methods/algorithms required specifically by the problem~~)		* Note that depth first search and other related functionality is usually implemented separately, as a standalone function
			* Method: toString()

	Vertex class:		Vertex class:
	* Map of Vertex objects to Edge objects, to store connecting edges		* Map of Vertex objects to Edge objects, to store connecting edges (neighbor list)
	* Integer (element/identifier)		* Integer (element/identifier)
	* Method: get ~~neighbors~~		* Method: get edges connecting to this vertex
			* Method: add new neighbor to this vertex
	* Method: get element		* Method: get element
			* Method: toString()

	Edge class:		Edge class:
	* List of Vertex objects		* List of Vertex objects
	* (Optional) int array (element/identifier)		* (Optional) int array (element/identifier)
	* Constructor: two vertices, set as endpoints		* Constructor: two vertices (integer indexes), set as endpoints
	* Method: get ~~endpoints~~		* Method: has endpoints (check if a vertex is one of this edge's endpoints)
			* Method: get opposite (pass one endpoint, get the opposite endpoint)
	* Method: get element		* Method: get element
			* Method: toString()

	==Static Classes==		==Static Classes==

Admin: /* Algorithms */

2017-10-17T10:17:40Z

Algorithms

@@ Line 153: / Line 153: @@
 =Algorithms=
 <pre>
-// u is an empty dictionary
+    /** Recursive depth-first search that populates HashMap discovered
-def dfs_connected(g):
+     * with all edges/vertices discoverable from u.*/
-    forest is empty dictionary
+    public static void dfs(Graph g, Vertex u,
-    for each vertex u in graph:
+                           HashSet<Vertex> known,
-        if u not in forest:
+                           HashMap<Vertex, Edge> discovered) {
-             forest[u] = None
+        known.add(u);
-            do_dfs(g, u, forest)
+        for(Edge e : u.outgoingEdges()) {
-     return forest
+            Vertex v = e.getOpposite(u);
-// complementary method: do depth first search
+==Counting connected components with DFS==
-def do_dfs(g, u, discovered):
-     for e in g.incident_edges(u):
+One of the applications of implementing a DFS is to count the number of connected components on a graph. To do this, we need to wrap the DFS with another method that will ensure we visit all components.
-        if v not in discovered:
-            discovered[v] = e
+This method utilizes the fact that the root node of each graph component is NOT included in the discovered map that is populated by the DFS.
-            do_dfs(g, v, discovered)
 </pre>

Admin: /* Java Code */

2017-10-17T07:30:42Z

Java Code

← Older revision		Revision as of 07:30, 17 October 2017
Line 51:		Line 51:

	public class Solution {		public class Solution {
			</pre>

			Here is the Graph class:

			<pre>
	static class Graph {		static class Graph {
	HashMap<Integer, Vertex> vertexMap;		HashMap<Integer, Vertex> vertexMap;
Line 101:		Line 105:
	}		}
	}		}
			</pre>

			The Vertex class:

			<pre>
	static class Vertex {		static class Vertex {
	private int element;		private int element;
Line 116:		Line 124:
	}		}
	}		}
			</pre>

			Finally, here is the Edge class:

			<pre>
	static class Edge {		static class Edge {
	ArrayList<Vertex> endpoints;		ArrayList<Vertex> endpoints;

Admin: /* Algorithms */

2017-10-17T07:29:19Z

Algorithms

← Older revision		Revision as of 07:29, 17 October 2017
Line 40:		Line 40:

	Easiest way to do this is to <code>raise new IllegalArgumentException("Error message here")</code>		Easiest way to do this is to <code>raise new IllegalArgumentException("Error message here")</code>

			=Java Code=

			<pre>
			import java.io.*;
			import java.util.*;
			import java.text.*;
			import java.math.*;
			import java.util.regex.*;

			public class Solution {

			static class Graph {
			HashMap<Integer, Vertex> vertexMap;
			ArrayList<Edge> edgeList;

			public Graph() {
			vertexMap = new HashMap<>();
			edgeList = new ArrayList<>();
			}

			public void addVertex(int i) {
			// To add a vertex, just add it to the master vertex map
			// along with its identifying integer.
			Vertex v = new Vertex(i);
			vertexMap.put(i,v);
			}

			public void addEdge(int i, int j) {
			// To add an edge:
			// - get the two endpoints,
			// - then create the edge,
			// - then add vertex i and vertex j as neighbors.
			Vertex vi = vertexMap.get(i);
			Vertex vj = vertexMap.get(j);
			Edge e = new Edge(vi, vj);
			vi.addNeighbor(vj, e);
			vj.addNeighbor(vi, e);
			edgeList.add(e);
			}

			public String toString() {
			StringBuffer sb = new StringBuffer();
			sb.append("Vertices:\n");
			for( Integer i : vertexMap.keySet() ) {
			sb.append(" ");
			sb.append(i);
			sb.append("\n");
			}
			sb.append("Edges:\n");
			for( Edge e : edgeList ) {
			ArrayList<Vertex> endpoints = e.getEndpoints();
			sb.append(" ");
			sb.append(endpoints.get(0).getElement());
			sb.append("-");
			sb.append(endpoints.get(1).getElement());
			sb.append("\n");
			}
			return sb.toString();
			}
			}

			static class Vertex {
			private int element;
			private HashMap<Vertex, Edge> neighborList;
			public Vertex(int element) {
			this.element = element;
			neighborList = new HashMap<>();
			}
			public void addNeighbor(Vertex v, Edge e) {
			neighborList.put(v, e);
			}
			public int getElement() {
			return this.element;
			}
			}

			static class Edge {
			ArrayList<Vertex> endpoints;
			public Edge(Vertex i, Vertex j) {
			endpoints = new ArrayList<>();
			endpoints.add(i);
			endpoints.add(j);
			}
			public ArrayList<Vertex> getEndpoints() {
			return endpoints;
			}
			public Vertex getOpposite(Vertex v) {
			if(v.equals(endpoints.get(0))) {
			return endpoints.get(1);
			} else if(v.equals(endpoints.get(1))) {
			return endpoints.get(0);
			} else {
			throw new IllegalArgumentException("Vertex not an endpoint of this edge.");
			}
			}
			}
			}
			</pre>

	=Algorithms=		=Algorithms=

Admin at 07:26, 17 October 2017

2017-10-17T07:26:12Z

@@ Line 1: / Line 1: @@
 Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.
 Graph class:
@@ Line 5: / Line 16: @@
 * Add vertex method (identified by integers)
 * Add edge method (takes two integers)
 Vertex class:
@@ Line 19: / Line 31: @@
 * Method: get element
 =Flags=
 {{GraphsFlag}}

Admin at 06:51, 17 October 2017

2017-10-17T06:51:57Z

← Older revision		Revision as of 06:51, 17 October 2017
Line 1:		Line 1:
	Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.		Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.

			Graph class:
			* Constructor: initializes list of vertices, list of edges
			* Add vertex method (identified by integers)
			* Add edge method (takes two integers)

			Vertex class:
			* Map of Vertex objects to Edge objects, to store connecting edges
			* Integer (element/identifier)
			* Method: get neighbors
			* Method: get element

			Edge class:
			* List of Vertex objects
			* (Optional) int array (element/identifier)
			* Constructor: two vertices, set as endpoints
			* Method: get endpoints
			* Method: get element






			=Flags=

			{{GraphsFlag}}

Admin: Created page with "Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge."

2017-10-17T06:31:06Z

Created page with "Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge."

New page

Note: this implementation is more practical for a lightweight problem, such as a programming competition or coding challenge.