Basic Interface
Erdos.jl defines the following basic functionalities:
Erdos.nv
— Functionnv(g)
The number of vertices in g
.
Erdos.ne
— Functionne(g)
The number of edges in g
.
Time Complexity: O(1)
Erdos.add_vertex!
— Functionadd_vertex!(g)
Add a new vertex to the graph g
.
Erdos.add_vertices!
— Functionadd_vertices!(g, n)
Add n
new vertices to the graph g
. Returns the final number of vertices.
Erdos.rem_vertex!
— Functionrem_vertex!(g, v)
Remove the vertex v
from graph g
. It will change the label of the last vertex of the old graph to v
.
See also rem_vertices!
.
Erdos.pop_vertex!
— Functionpop_vertex!(g)
Remove the last vertex of g
. Equivalent to rem_vertex!(g, nv(g)).
Erdos.rem_vertices!
— Functionrem_vertices!(g, vs)
rem_vertices!(g, v1, v2, ....)
Remove the vertices in vs
from graph g
.
Some vertices of g
may be reindexed during the removal. To keep track of the reindexing, a vertex map is returned, associating vertices with changed indexes to their old indexes.
Erdos.has_edge
— Functionhas_edge(g, e)
has_edge(g, u, v)
Returns true if the graph g
has an edge e
(from u
to v
).
Erdos.src
— Functionsrc(e)
Returns the source of an edge.
Erdos.dst
— Functiondst(e)
Returns the destination of an edge.
Erdos.edge
— Functionedge(g, u, v)
Returns an edge from 'u' to 'v'. The edge doesn't necessarily exists in g
.
Erdos.add_edge!
— Functionadd_edge!(g, e) -> (ok, new_edge)
Add to g
the edge e
.
add_edge!(g, u, v) -> (ok, new_edge)
Add to g
an edge from u
to v
.
ok=false
if add fails (e.g. if vertices are not in the graph or the edge is already present) and true
otherwise. new_edge
is the descriptor of the new edge.
Erdos.unsafe_add_edge!
— Functionunsafe_add_edge!(g, u, v)
Possibly faster and unsafer version of add_edge!
, which doesn't guarantee some graph invariant properties.
For example, some graph types (e.g. Graph
) assume sorted adjacency lists as members. In this case order is not preserved while inserting new edges, resulting in a faster construction of the graph. As a consequence though, some functions such has_edge(g, u, v)
could give incorrect results.
To restore the correct behaviour, call rebuild!
(g) after the last call to unsafe_add_edge!
.
Erdos.rebuild!
— Functionrebuild!(g)
Check and restore the structure of g
, which could be corrupted by the use of unsafe functions (e. g. unsafe_add_edge!
)
Erdos.rem_edge!
— Functionrem_edge!(g, e)
Remove the edge e
.
rem_edge!(g, u, v)
Remove the edge from u
to v
.
Returns false if edge removal fails (e.g., if the edge does not exist) and true otherwise.
Erdos.degree
— Functiondegree(g, v)
Return the number of edges from the vertex v
.
Erdos.in_degree
— Functionin_degree(g, v)
Returns the number of edges which start at vertex v
.
Erdos.out_degree
— Functionout_degree(g, v)
Returns the number of edges which end at vertex v
.
Erdos.neighbors
— Functionneighbors(g, v)
Returns a list of all neighbors from vertex v
in g
.
For directed graph, this is equivalent to out_neighbors
(g, v).
NOTE: it may return a reference, not a copy. Do not modify result.
Erdos.in_neighbors
— Functionin_neighbors(g, v)
Returns an iterable to all neighbors connected to vertex v
by an incoming edge.
NOTE: it may return a reference, not a copy. Do not modify result.
Erdos.out_neighbors
— Functionout_neighbors(g::AGraphOrDiGraph, v)
Returns an iterable to all neighbors connected to vertex v
by an outgoing edge.
NOTE: it may return a reference, not a copy. Do not modify result.
Erdos.all_neighbors
— Functionall_neighbors(g, v)
Iterates over all distinct in/out neighbors of vertex v
in g
.
Erdos.edges
— Functionedges(g, v)
Returns an iterator to the edges in g
coming from vertex v
. v == src(e)
for each returned edge e
.
It is equivalent to out_edges
.
For digraphs, use all_edges
to iterate over both in and out edges.
Erdos.in_edges
— Functionin_edges(g, v)
Returns an iterator to the edges in g
going to vertex v
. v == dst(e)
for each returned edge e
.
Erdos.out_edges
— Functionout_edges(g, v)
Returns an iterator to the edges in g
coming from vertex v
. v == src(e)
for each returned edge e
.
Erdos.all_edges
— Functionall_edges(g, v)
Iterates over all in and out edges of vertex v
in g
.
Erdos.swap_vertices!
— Functionswap_vertices!(g, u, v)
Swap the labels of vertices u
and v
. In the new graph all old neighbors of vertex u
will be neighbors of v
and viceversa.
Erdos.has_vertex
— Functionhas_vertex(g, v)
Return true if v
is a vertex of g
.
Erdos.is_directed
— Functionis_directed(g)
Check if g
a graph with directed edges.
Base.reverse
— Functionreverse(e)
Returns an edge with swapped src(e)
and dst(e)
.
reverse(g::ADiGraph)
Produces a graph where all edges are reversed from the original.
Base.reverse!
— Functionreverse!(g::DiGraph)
In-place reverse (modifies the original graph).
Erdos.adjacency_list
— Functionadjacency_list(g::AGraph)
adjacency_list(g::ADiGraph, dir=:out)
Returns the adjacency list a
of a graph (a vector of vector of ints). The i
-th element of the adjacency list is a vector containing the neighbors of i
in g
.
For directed graphs a second optional argument can be specified (:out
or :in
). The neighbors in the returned adjacency list are considered accordingly as those related through outgoing or incoming edges.
The elements of a[i]
have the same order as in the iterator (out_/in_)neighbors(g,i)
.
Attention: For some graph types it returns a reference, not a copy, therefore the returned object should not be modified.
Erdos.clean_vertex!
— Functionclean_vertex!(g, v)
Remove all incident edges on vertex v
in g
.
Erdos.density
— Functiondensity(g)
Density is defined as the ratio of the number of actual edges to the number of possible edges. This is $|v| |v-1|$ for directed graphs and $(|v| |v-1|) / 2$ for undirected graphs.
Erdos.vertices
— Functionvertices(g)
Returns an iterator to the vertices of a graph (i.e. 1:nv(g))
Erdos.has_self_loops
— Functionhas_self_loops(g)
Returns true if g
has any self loops.
Erdos.num_self_loops
— Functionnum_self_loops(g)
Returns the number of self loops in g
.
Erdos.is_graphical
— Functionis_graphical(degs::Vector{Int})
Check whether the degree sequence degs
is graphical, according to Erdös-Gallai condition.
Time complexity: O(length(degs)^2)
Erdos.graph
— Functiongraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
G = Graph)
Build a graph with n
vertices, of type G
, and given edgelist
.
graph(s::Symbol, G = Graph)
Creates a notorious graph s
of type G
. Admissible values for s
are:
s | graph type |
---|---|
:bull | A bull graph. |
:chvatal | A Chvátal graph. |
:cubical | A Platonic cubical graph. |
:desargues | A Desarguesgraph. |
:diamond | A diamond graph. |
:dodecahedral | A Platonic dodecahedral graph. |
:frucht | A Frucht graph. |
:heawood | A Heawood graph. |
:house | A graph mimicing the classic outline of a house. |
:housex | A house graph, with two edges crossing the bottom square. |
:icosahedral | A Platonic icosahedral graph. |
:krackhardtkite | A Krackhardt-Kite social network graph. |
:moebiuskantor | A Möbius-Kantor graph. |
:octahedral | A Platonic octahedral graph. |
:pappus | A Pappus graph. |
:petersen | A Petersen graph. |
:sedgewickmaze | A simple maze graph used in Sedgewick's Algorithms in C++: Graph Algorithms (3rd ed.) |
:tetrahedral | A Platonic tetrahedral graph. |
:truncatedcube | A skeleton of the truncated cube graph. |
:truncatedtetrahedron | A skeleton of the truncated tetrahedron graph. |
:tutte | A Tutte graph. |
A collection of real world graphs is available through the readgraph
function.
Erdos.digraph
— Functiondigraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
G = Graph)
Build a digraph with n
vertices, type G
, and given edgelist
.
digraph(s::Symbol, G = DiGraph)
Creates a notorious digraph s
of type G
. Admissible values for s
are:
s | graph type |
---|---|
:truncatedtetrahedron | A skeleton of the truncated tetrahedron digraph. |
Erdos.edgetype
— Functionedgetype(g)
edgetype(G)
Returns the type of edges of graph g
(or graph type G
), i. e. the element type returned of the iterator edges(g)
.
Erdos.vertextype
— Functionvertextype(g)
vertextype(G)
Returns the integer type of vertices of graph g
(or graph type G
).
Erdos.graphtype
— Functiongraphtype{G<:AGraphOrDiGraph}(::Type{G})
The graph type corresponding to G
. If G<:AGraph
returns G
, if G<:ADiGraph
returns a type H<:AGraph
.
Erdos.digraphtype
— Functiondigraphtype{G<:AGraphOrDiGraph}(::Type{G})
The digraph type corresponding to G
. If G<:ADiGraph
returns G
, if G<:AGraph
returns a type H<:ADiGraph
.