Graph Types¶
This package provides several graph types that implement different subsets of interfaces. In particular, it has four graph types:
GenericEdgeList
GenericAdjacencyList
GenericIncidenceList
GenericGraph
All of these types are parametric. One can easily derive customized graph types using different type parameters.
Edge List¶
GenericEdgeList
implements the edge list representation of a graph, where a list of all edges is maintained by each graph.
Here is the definition of GenericEdgeList
:
type EdgeList{V,E,VList,EList} <: AbstractGraph{V, E}
It has four type parameters:
V
: the vertex typeE
: the edge typeVList
: the type of the vertex listEList
: the type of the edge list
The package defines the following aliases for convenience:
typealias SimpleEdgeList{E} GenericEdgeList{Int,E,UnitRange{Int},Vector{E}}
typealias EdgeList{V,E} GenericEdgeList{V,E,Vector{V},Vector{E}}
GenericEdgeList
implements the following interfaces
vertex_list
vertex_map
edge_list
edge_map
Specifically, it implements the following methods:
-
is_directed
(g)¶ returns whether
g
is a directed graph.
-
num_vertices
(g)¶ returns the number of vertices contained in
g
.
-
vertices
(g)¶ returns an iterable view/container of all vertices.
-
num_edges
(g)¶ returns the number of edges contained in
g
.
-
vertex_index
(v, g)¶ returns the index of a vertex
v
in graphg
-
edges
(g)¶ returns the list of all edges
-
edge_index
(e, g)¶ returns the index of
e
in graphg
.
In addition, it implements following methods for construction:
-
simple_edgelist
(nv, edges[, is_directed=true])¶ constructs a simple edge list with
nv
vertices and the given list of edges.
-
edgelist
(vs, edges[, is_directed=true])¶ constructs an edge list given lists of vertices and edges.
Adjacency List¶
GenericAdjacencyList
implements the adjacency list representation of a graph, where each vertex maintains a list of neighbors (i.e. adjacent vertices).
Here is the definition of GenericAdjacencyList
:
type GenericAdjacencyList{V, VList, AdjList} <: AbstractGraph{V, Edge{V}}
It has three type parameters:
V
: the vertex typeVList
: the type of vertex listAdjList
: the type of the adjacency list. Leta
be an instance ofAdjList
, andi
be the index of a vertex, thena[i]
must be an iterable container of the neighbors.
The package defines following aliases for convenience:
typealias SimpleAdjacencyList GenericAdjacencyList{Int, UnitRange{Int}, Vector{Vector{Int}}}
typealias AdjacencyList{V} GenericAdjacencyList{V, Vector{V}, Vector{Vector{V}}}
GenericAdjacencyList
implements the following interfaces
vertex_list
vertex_map
adjacency_list
Specifically, it implements the following methods:
-
is_directed
(g) returns whether
g
is a directed graph.
-
num_vertices
(g) returns the number of vertices contained in
g
.
-
vertices
(g) returns an iterable view/container of all vertices.
-
num_edges
(g) returns the number of edges contained in
g
.
-
vertex_index
(v, g) returns the index of a vertex
v
in graphg
-
out_degree
(v, g)¶ returns the number of outgoing neighbors from vertex
v
in graphg
.
-
out_neighbors
(v, g)¶ returns an iterable view/container of all outgoing neighbors of vertex
v
in graphg
.
In addition, it implements following methods for construction:
-
simple_adjlist
(nv[, is_directed=true])¶ constructs a simple adjacency list with
nv
vertices and no edges (initially).
-
adjlist
(V[, is_directed=true])¶ constructs an empty adjacency list of vertex type
V
.
-
adjlist
(vs[, is_directed=true]) constructs an adjacency list with a vector of vertices given by
vs
.
-
add_vertex!(g, v)
adds a vertex
v
. This function applies only to graph of typeAdjacencyList
. It returns the added vertex.If the vertex type is
KeyVertex{K}
, then the second argument here can be the key value, and the function will constructs a vertex and assigns an index.
-
add_edge!(g, u, v)
adds an edge between u and v, such that
v
becomes an outgoing neighbor ofu
. Ifg
is undirected, thenu
is also added to the neighbor list ofv
.
Incidence List¶
GenericIncidenceList
implements the incidence list representation of a graph, where each vertex maintains a list of outgoing edges.
Here is the definition of GenericIncidenceList
:
type GenericIncidenceList{V, E, VList, IncList} <: AbstractGraph{V, E}
It has four type parameters:
V
: the vertex typeE
: the edge typeVList
: the type of vertex listIncList
: the type of incidence list. Leta
be such a list, thena[i]
should be an iterable container of edges.
The package defines following aliases for convenience:
typealias SimpleIncidenceList GenericIncidenceList{Int, IEdge, UnitRange{Int}, Vector{Vector{IEdge}}}
typealias IncidenceList{V,E} GenericIncidenceList{V, E, Vector{V}, Vector{Vector{E}}}
GenericIncidenceList
implements the following interfaces:
vertex_list
vertex_map
edge_map
adjacency_list
incidence_list
Specially, it implements the following methods:
-
is_directed
(g) returns whether
g
is a directed graph.
-
num_vertices
(g) returns the number of vertices contained in
g
.
-
vertices
(g) returns an iterable view/container of all vertices.
-
num_edges
(g) returns the number of edges contained in
g
.
-
vertex_index
(v, g) returns the index of a vertex
v
in graphg
-
edge_index
(e, g) returns the index of an edge
e
in graphg
.
-
source
(e, g)¶ returns the source vertex of an edge
e
in graphg
.
-
target
(e, g)¶ returns the target vertex of an edge
e
in graphg
.
-
out_degree
(v, g) returns the number of outgoing neighbors from vertex
v
in graphg
.
-
out_edges
(v, g)¶ returns the number of outgoing edges from vertex
v
in graphg
.
-
out_neighbors
(v, g) returns an iterable view/container of all outgoing neighbors of vertex
v
in graphg
.Note:
out_neighbors
here is implemented based onout_edges
via a proxy type. Therefore, it may be less efficient than the counterpart forGenericAdjacencyList
.
In addition, it implements following methods for construction:
-
simple_inclist
(nv[, is_directed=true])¶ constructs a simple incidence list with
nv
vertices and no edges (initially).
-
inclist
(V[, is_directed=true])¶ constructs an empty incidence list of vertex type
V
. The edge type isEdge{V}
.
-
inclist
(vs[, is_directed=true]) constructs an incidence list with a list of vertices
vs
. The edge type isEdge{V}
.
-
inclist
(V, E[, is_directed=true]) constructs an empty incidence list of vertex type
V
. The edge type isE
.
-
inclist
(vs, E[, is_directed=true]) constructs an incidence list with a list of vertices
vs
. The edge type isE
.
-
add_vertex!(g, x)
adds a vertex. Here,
x
can be of a vertex type, or can be made into a vertex usingmake_vertex(g, x)
.
-
add_edge!(g, e)
adds an edge
e
to the graph.
-
add_edge!(g, u, v)
adds an edge between
u
andv
. This applies whenmake_edge(g, u, v)
is defined for the input types.
Graph¶
GenericGraph
provides a complete interface by integrating edge list, bidirectional adjacency list, and bidirectional incidence list into one type. The definition is given by
type GenericGraph{V,E,VList,EList,IncList} <: AbstractGraph{V,E}
It has six type parameters:
V
: the vertex typeE
: the edge typeVList
: the type of vertex listEList
: the type of edge listIncList
: the type of incidence list
It also defines SimpleGraph
as follows
typealias SimpleGraph GenericGraph{Int,IEdge,UnitRange{Int},Vector{IEdge},Vector{Vector{IEdge}}}
and a more full-fledged type Graph
as follows
typealias Graph{V,E} GenericGraph{V,E,Vector{V},Vector{E},Vector{Vector{E}}}
GenericGraph
implements the following interfaces:
vertex_list
edge_list
vertex_map
edge_map
adjacency_list
incidence_list
bidirectional_adjacency_list
bidirectional_incidence_list
Specifically, it implements the following methods:
-
is_directed
(g) returns whether
g
is a directed graph.
-
num_vertices
(g) returns the number of vertices contained in
g
.
-
vertices
(g) returns an iterable view/container of all vertices.
-
num_edges
(g) returns the number of edges contained in
g
.
-
edges
(g) returns an iterable view/container of all edges.
-
vertex_index
(v, g) returns the index of a vertex
v
in graphg
-
edge_index
(e, g) returns the index of a vertex
e
in graphg
.
-
source
(e, g) returns the source vertex of an edge
e
in graphg
.
-
target
(e, g) returns the target vertex of an edge
e
in graphg
.
-
out_degree
(v, g) returns the number of outgoing neighbors from vertex
v
in graphg
.
-
out_edges
(v, g) returns the number of outgoing edges from vertex
v
in graphg
.
-
out_neighbors
(v, g) returns an iterable view/container of all outgoing neighbors of vertex
v
in graphg
.
-
in_degree
(v, g)¶ returns the number of incoming neighbors to vertex
v
in graphg
.
-
in_edges
(v, g)¶ returns the number of incoming edges to vertex
v
in graphg
.
-
in_neighbors
(v, g)¶ returns an iterable view/container of all incoming neighbors to vertex
v
in graphg
.
In addition, it also implements the following methods for construction:
-
simple_graph
(nv[, is_directed=true])¶ constructs an instance of
SimpleGraph
withnv
vertices and no edges (initially).
-
graph
(vertices, edges[, is_directed=true]) constructs an instance of
Graph
with given vertices and edges.
-
add_vertex!(g, x)
adds a vertex. Here,
x
can be of a vertex type, or can be made into a vertex usingmake_vertex(g, x)
.
-
add_edge!(g, e)
adds an edge
e
to the graph.
-
add_edge!(g, u, v)
adds an edge between
u
andv
. This applies whenmake_edge(g, u, v)
is defined for the input types.