Variations of Graph ADTs
From
| Line 3: | Line 3: | ||
</noinclude> | </noinclude> | ||
<br/> | <br/> | ||
| - | + | ===Directed Graphs=== | |
| + | [[Image:Directed.svg|125px|thumb|A directed graph.]] | ||
| + | The number of edges with one endpoint on a given vertex is called that vertex's '''degree'''. In a directed graph, the number of edges that point ''to'' a given vertex is called its '''in-degree''', and the number that point ''from'' it is called its '''out-degree'''. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph '''labeled'''. | ||
| + | |||
| + | <div class="interface" style="background-color: #FFFFEE; border: solid 1px #FFC92E; padding: 1em; width:80%" title="Directed Graph Operations"> | ||
| + | '''Directed Graph Operations''' | ||
| + | <dl> | ||
| + | <dt style="font-weight:normal"><code style="background:#FFFFEE">'''make-graph'''(): graph</code> | ||
| + | <dd>Create a new graph, initially with no nodes or edges. | ||
| + | |||
| + | <dt style="font-weight:normal"><code style="background:#FFFFEE">'''make-vertex'''(graph ''G'', element ''value''): vertex</code> | ||
| + | <dd>Create a new vertex, with the given value. | ||
| + | |||
| + | <dt style="font-weight:normal"><code style="background:#FFFFEE">'''make-edge'''(vertex ''u'', vertex ''v''): edge</code> | ||
| + | <dd>Create an edge between ''u'' and ''v''. In a directed graph, the edge will flow from ''u'' to ''v''. | ||
| + | |||
| + | <dt style="font-weight:normal"><code style="background:#FFFFEE">'''get-edges'''(vertex ''v''): edge-set</code> | ||
| + | <dd>Returns the set of edges flowing from ''v'' | ||
| + | |||
| + | <dt style="font-weight:normal"><code style="background:#FFFFEE">'''get-neighbors'''(vertex ''v''): vertex-set</code> | ||
| + | <dd>Returns the set of vertexes connected to ''v'' | ||
| + | </dl> | ||
| + | |||
| + | [TODO: also need undirected graph abstraction in that section, and also find a better set of operations-- the key to finding good operations is seeing what the algorithms that ''use'' graphs actually ''need''] | ||
| + | </div> | ||
| + | |||
| + | We can use graphs to represent relationships between objects. For example, the popular game "[http://en.wikipedia.org/wiki/Six_Degrees_of_Kevin_Bacon Six Degrees of Kevin Bacon]" can be modeled by a graph, in particular, a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Then the problem of finding a path from any actor to Kevin Bacon in six or less steps easily reduces to the Single Source Shortest Path problem found in the companion [[Computer_Science:Algorithms|Algorithms]] book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks[http://www.cs.virginia.edu/oracle/]. | ||
| + | |||
| + | ===Undirected Graphs=== | ||
| + | [[Image:Undirected.svg|thumb|125px|An undirected graph.]] | ||
| + | In a directed graph, the edges point from one vertex to another, while in an '''undirected graph''', they merely connect two vertices. | ||
| + | |||
| + | ===Weighted Graphs=== | ||
| + | We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called '''weighted'''. An example of a weighted graph would be the distance between the capitals of a set of countries. | ||
| + | |||
| + | Directed and undirected graphs may both be weighted. The operations on a weighted graph are the same with addition of a weight parameter during edge creation: | ||
| + | <div class="interface" style="background-color: #FFFFEE; border: solid 1px #FFC92E; padding: 1em; width:80%" title="Directed Graph Operations"> | ||
| + | '''Weighted Graph Operations (an extension of undirected/directed graph operations)''' | ||
| + | <dt style="font-weight:normal"><code style="background:#FFFFEE">'''make-edge'''(vertex ''u'', vertex ''v'', weight ''w''): edge</code> | ||
| + | <dd>Create an edge between ''u'' and ''v'' with weight ''w''. In a directed graph, the edge will flow from ''u'' to ''v''. | ||
| + | </dl> | ||
| + | </div> | ||
| + | |||
---- | ---- | ||
{{CS2/ChapNav}} | {{CS2/ChapNav}} | ||
---- | ---- | ||
[[Category:CS2|{{SUBPAGENAME}}]] | [[Category:CS2|{{SUBPAGENAME}}]] | ||
Revision as of 20:21, 9 April 2009
| ← Representing Graphs | ↑ Contents: CS2 | Common Graph Algorithms → |
Directed Graphs
The number of edges with one endpoint on a given vertex is called that vertex's degree. In a directed graph, the number of edges that point to a given vertex is called its in-degree, and the number that point from it is called its out-degree. Often, we may want to be able to distinguish between different nodes and edges. We can associate labels with either. We call such a graph labeled.
Directed Graph Operations
make-graph(): graph- Create a new graph, initially with no nodes or edges.
make-vertex(graph G, element value): vertex- Create a new vertex, with the given value.
make-edge(vertex u, vertex v): edge- Create an edge between u and v. In a directed graph, the edge will flow from u to v.
get-edges(vertex v): edge-set- Returns the set of edges flowing from v
get-neighbors(vertex v): vertex-set- Returns the set of vertexes connected to v
[TODO: also need undirected graph abstraction in that section, and also find a better set of operations-- the key to finding good operations is seeing what the algorithms that use graphs actually need]
We can use graphs to represent relationships between objects. For example, the popular game "Six Degrees of Kevin Bacon" can be modeled by a graph, in particular, a labeled undirected graph. Each actor becomes a node, labeled by the actor's name. Nodes are connected by an edge when the two actors appeared together in some movie. We can label this edge by the name of the movie. Then the problem of finding a path from any actor to Kevin Bacon in six or less steps easily reduces to the Single Source Shortest Path problem found in the companion Algorithms book. The Oracle of Bacon at the University of Virginia has actually implemented this algorithm and can tell you the path from any actor to Kevin Bacon in a few clicks[1].
Undirected Graphs
In a directed graph, the edges point from one vertex to another, while in an undirected graph, they merely connect two vertices.
Weighted Graphs
We may also want to associate some cost or weight to the traversal of an edge. When we add this information, the graph is called weighted. An example of a weighted graph would be the distance between the capitals of a set of countries.
Directed and undirected graphs may both be weighted. The operations on a weighted graph are the same with addition of a weight parameter during edge creation:
Weighted Graph Operations (an extension of undirected/directed graph operations)
make-edge(vertex u, vertex v, weight w): edge- Create an edge between u and v with weight w. In a directed graph, the edge will flow from u to v.
CS2: Data Structures
Theory of Computation - ADT Preliminaries
Linear ADTs - Tree ADTs - Graph ADTs - Unordered Collection ADTs
