Graphs/Data Structures - Revision history

Admin: /* Edge List */

2017-09-05T08:00:55Z

Edge List

← Older revision		Revision as of 08:00, 5 September 2017
Line 11:		Line 11:

	==Edge List==		==Edge List==

	~~<s>[[Graphs/Java/Edge List]]</s>~~

	A simple and cheap but messy implementation of graphs.		A simple and cheap but messy implementation of graphs.

Admin: /* Adjacency Matrix */

2017-08-21T08:12:31Z

Adjacency Matrix

← Older revision		Revision as of 08:12, 21 August 2017
Line 79:		Line 79:
	==Adjacency Matrix==		==Adjacency Matrix==

	~~{{Main\|~~Graphs/Java/Adjacency Matrix}}		<s>[[Graphs/Java/Adjacency Matrix]]</s>

	Provides fast access to specific edges by maintaining a matrix with a row and column entry for each vertex. The entry at (u,v) is the edge (if any) connecting vertex u to vertex v.		Provides fast access to specific edges by maintaining a matrix with a row and column entry for each vertex. The entry at (u,v) is the edge (if any) connecting vertex u to vertex v.

Admin: /* Adjacency List */

2017-08-21T08:11:36Z

Adjacency List

← Older revision		Revision as of 08:11, 21 August 2017
Line 37:		Line 37:
	==Adjacency List==		==Adjacency List==

	~~{{Main\|~~Graphs/Java/Adjacency List}}		<s>[[Graphs/Java/Adjacency List]]</s>

	The adjacency list maintains a list pointing to each vertex, and each vertex points to a list of edges that are incident to that vertex. This makes going from a vertex to a set of edges that connect to it very easy. In this context, we say that the vertex v has an associated '''incidence collection''' (the list of edges that are incident to that vertex).		The adjacency list maintains a list pointing to each vertex, and each vertex points to a list of edges that are incident to that vertex. This makes going from a vertex to a set of edges that connect to it very easy. In this context, we say that the vertex v has an associated '''incidence collection''' (the list of edges that are incident to that vertex).

Admin: /* Edge List */

2017-08-21T08:11:21Z

Edge List

← Older revision		Revision as of 08:11, 21 August 2017
Line 12:		Line 12:
	==Edge List==		==Edge List==

	~~{{Main\|~~Graphs/Java/Edge List}}		<s>[[Graphs/Java/Edge List]]</s>

	A simple and cheap but messy implementation of graphs.		A simple and cheap but messy implementation of graphs.

Admin: /* Notes */

2017-08-21T01:54:02Z

Notes

← Older revision		Revision as of 01:54, 21 August 2017
Line 22:		Line 22:
	[[Image:EdgeListGraph.png\|500px]]		[[Image:EdgeListGraph.png\|500px]]

	~~Vertex objects are augmented as follows~~:		Edge List Graph class:
	* ~~Reference to data element x~~		* List of vertices
	* Reference to position of ~~vertex instance in list V~~		* List of edges
	** In practice, a reference to a position in a list means a pointer to the linked list node that stores the vertex
	** This allows for easy removal of ~~a vertex object from a graph~~

	Edge ~~objects are augmented as follows~~:		Edge List Vertex class:
	* ~~Reference~~ to ~~data~~ element x		* Data/element x
	* ~~Reference to all~~ vertex objects associated with edge e (~~allow for constant-time implementation of methods to get~~ endpoints ~~of a vertex, or to get opposite vertex given a vertex and an edge~~)		* Position of vertex in graph's vertex list (in practice, this is a pointer to a linked list node)
	* ~~Reference to position~~ in edge list (~~allowing easy/efficient removal of an Edge object, given the Edge object and a Graph object)~~
	** In practice, ~~a reference to a position in the edge list means~~ a pointer to a linked list node		Edge List Edge class:
			* Data/element x
			* List of vertex objects associated with edge e (the two endpoints)
			* Position of edge in graph's edge list (in practice, this is a pointer to a linked list node)

	==Adjacency List==		==Adjacency List==
Line 45:		Line 46:

	Adjacency List Graph class:		Adjacency List Graph class:
	* ~~Stores list~~ of edges		* List of all edges on graph
	* ~~Stores list~~ of ~~nodes~~		* List of all vertices on graph

	Adjacency List Vertex class:		Adjacency List Vertex class:
	* ~~Reference~~ to		* Data/element x
	* ~~Reference~~ to ~~incidence~~ list		* Vertex incidence list (list of edges that connect to this vertex)
			* Position of vertex in graph's vertex list (pointer to linked list node)

			Adjacency List Edge class:
			* Data/element x
			* Position of edge in graph's edge list (pointer to linked list node)

	==Adjacency Map==		==Adjacency Map==
Line 58:		Line 64:
	Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.		Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.

	Graph ~~object stores the following~~:		Adjacency Map Graph class:
	* ~~Linked list~~ of all vertices on graph		* List of all vertices on graph
	* ~~Linked list~~ of all edges on graph		* List of all edges on graph

	Vertex ~~objects are augmented as follows~~:		Adjacency Map Vertex class:
	* ~~Reference to data~~ element x		* Data/element x
	* ~~Reference to position of vertex instance in list V~~ (~~in the form of a linked~~ list ~~node pointer)~~		* Vertex adjacency map (mapping from keys (list of vertices connected to this vertex) to values (edges that connect the two vertices))
	* Map of vertices to edges ~~(incidence collection/adjacency map~~)		* Position of vertex in graph's vertex list (pointer to linked list node)
	* ~~Boolean indicating whether the map is directed or undirected~~
	** If graph ~~is directed,~~ vertex ~~will store two maps~~ (~~incoming and outgoing edges~~)
	** If graph is undirected, incoming and outgoing maps point to the same place

	Edge ~~objects are augmented as follows~~:		Adjacency Map Edge class:
	* ~~Reference to data~~ element x		* Data/element x
	* Reference to vertex objects at endpoints of edge		* Reference to position in the list of edges (?) (linked list node pointer)
	* Reference to position in the list of edges (~~in the form of a~~ linked list node pointer)

	==Adjacency Matrix==		==Adjacency Matrix==
Line 80:		Line 82:

	Provides fast access to specific edges by maintaining a matrix with a row and column entry for each vertex. The entry at (u,v) is the edge (if any) connecting vertex u to vertex v.		Provides fast access to specific edges by maintaining a matrix with a row and column entry for each vertex. The entry at (u,v) is the edge (if any) connecting vertex u to vertex v.

			Adjacency Matrix Graph class:
			* List of all vertices on graph
			* List of all edges on graph
			* Adjacency Matrix

			Adjacency Matrix Vertex class:

			Adjacency Matrix Edge class:

	=Flags=		=Flags=

	{{GraphsFlag}}		{{GraphsFlag}}

Admin: /* Adjacency List */

2017-08-21T01:39:46Z

Adjacency List

← Older revision		Revision as of 01:39, 21 August 2017
Line 39:		Line 39:

	The adjacency list maintains a list pointing to each vertex, and each vertex points to a list of edges that are incident to that vertex. This makes going from a vertex to a set of edges that connect to it very easy. In this context, we say that the vertex v has an associated '''incidence collection''' (the list of edges that are incident to that vertex).		The adjacency list maintains a list pointing to each vertex, and each vertex points to a list of edges that are incident to that vertex. This makes going from a vertex to a set of edges that connect to it very easy. In this context, we say that the vertex v has an associated '''incidence collection''' (the list of edges that are incident to that vertex).

			The figure below illustrates that the adjacency list stores everything the same way the edge list stores things, plus augments it by adding a list of edges to each vertex object. The Edge and Vertex classes described above are re-used, with the only additional augmentation being:

	[[Image:AdjacencyListGraph.png\|500px]]		[[Image:AdjacencyListGraph.png\|500px]]

	~~The figure shows that the adjacency~~ list ~~stores everything the same way the edge list stores things, plus augments it by adding a~~ list of ~~edges to each vertex object. The Edge and Vertex classes described above are re-used, with the only additional augmentation being:~~		Adjacency List Graph class:
			* Stores list of edges
			* Stores list of nodes

	Vertex ~~objects~~:		Adjacency List Vertex class:
			* Reference to
	* Reference to incidence list		* Reference to incidence list

Admin: /* Adjacency Map */

2017-08-21T01:38:27Z

Adjacency Map

← Older revision		Revision as of 01:38, 21 August 2017
Line 52:		Line 52:

	Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.		Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.

			Graph object stores the following:
			* Linked list of all vertices on graph
			* Linked list of all edges on graph

	Vertex objects are augmented as follows:		Vertex objects are augmented as follows:

Admin: /* Edge List */

2017-08-21T01:20:39Z

Edge List

← Older revision		Revision as of 01:20, 21 August 2017
Line 24:		Line 24:
	Vertex objects are augmented as follows:		Vertex objects are augmented as follows:
	* Reference to data element x		* Reference to data element x
	* Reference to position of vertex instance in list V (allows for easy removal of a ~~Vertex~~ object~~, given~~ a ~~Vertex object and a Graph object, because we have the index in the Graph object's list of vertices)~~		* Reference to position of vertex instance in list V
			** In practice, a reference to a position in a list means a pointer to the linked list node that stores the vertex
			** This allows for easy removal of a vertex object from a graph

	Edge objects are augmented as follows:		Edge objects are augmented as follows:
Line 30:		Line 32:
	* Reference to all vertex objects associated with edge e (allow for constant-time implementation of methods to get endpoints of a vertex, or to get opposite vertex given a vertex and an edge)		* Reference to all vertex objects associated with edge e (allow for constant-time implementation of methods to get endpoints of a vertex, or to get opposite vertex given a vertex and an edge)
	* Reference to position in edge list (allowing easy/efficient removal of an Edge object, given the Edge object and a Graph object)		* Reference to position in edge list (allowing easy/efficient removal of an Edge object, given the Edge object and a Graph object)
			** In practice, a reference to a position in the edge list means a pointer to a linked list node

	==Adjacency List==		==Adjacency List==

Admin: /* Adjacency Map */

2017-08-21T01:19:01Z

Adjacency Map

← Older revision		Revision as of 01:19, 21 August 2017
Line 52:		Line 52:
	Vertex objects are augmented as follows:		Vertex objects are augmented as follows:
	* Reference to data element x		* Reference to data element x
	* Reference to position of vertex instance in list V		* Reference to position of vertex instance in list V (in the form of a linked list node pointer)
	* Map of vertices to edges (incidence collection/adjacency map)		* Map of vertices to edges (incidence collection/adjacency map)
	* Boolean indicating whether the map is directed or undirected		* Boolean indicating whether the map is directed or undirected
Line 61:		Line 61:
	* Reference to data element x		* Reference to data element x
	* Reference to vertex objects at endpoints of edge		* Reference to vertex objects at endpoints of edge
	* Reference to position in the list of edges		* Reference to position in the list of edges (in the form of a linked list node pointer)

	==Adjacency Matrix==		==Adjacency Matrix==

Admin: /* Adjacency Map */

2017-08-21T01:09:44Z

Adjacency Map

← Older revision		Revision as of 01:09, 21 August 2017
Line 49:		Line 49:

	Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.		Similar approach to adjacency list, but replaces the edge list with a map. The keys are other vertices connected to this vertex, and values are the edges that connect the two vertices.

			Vertex objects are augmented as follows:
			* Reference to data element x
			* Reference to position of vertex instance in list V
			* Map of vertices to edges (incidence collection/adjacency map)
			* Boolean indicating whether the map is directed or undirected
			** If graph is directed, vertex will store two maps (incoming and outgoing edges)
			** If graph is undirected, incoming and outgoing maps point to the same place

			Edge objects are augmented as follows:
			* Reference to data element x
			* Reference to vertex objects at endpoints of edge
			* Reference to position in the list of edges

	==Adjacency Matrix==		==Adjacency Matrix==