Basic Interface

Erdos.jl defines the following basic functionalities:

# Erdos.nv — Function.

nv(g)

The number of vertices in g.

source

# Erdos.ne — Function.

ne(g)

The number of edges in g.

Time Complexity: O(1)

source

# Erdos.add_vertex! — Function.

add_vertex!(g)

Add a new vertex to the graph g.

source

# Erdos.add_vertices! — Function.

add_vertices!(g, n)

Add n new vertices to the graph g. Returns the final number of vertices.

source

# Erdos.rem_vertex! — Function.

rem_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!.

source

# Erdos.pop_vertex! — Function.

pop_vertex!(g)

Remove the last vertex of g. Equivalent to rem_vertex!(g, nv(g)).

source

# Erdos.rem_vertices! — Function.

rem_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.

source

# Erdos.has_edge — Function.

has_edge(g, e)
has_edge(g, u, v)

Returns true if the graph g has an edge e (from u to v).

source

# Erdos.src — Function.

src(e)

Returns the source of an edge.

source

# Erdos.dst — Function.

dst(e)

Returns the destination of an edge.

source

# Erdos.edge — Function.

edge(g, u, v)

Returns an edge from 'u' to 'v'. The edge doesn't necessarily exists in g.

source

# Erdos.add_edge! — Function.

add_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.

source

# Erdos.unsafe_add_edge! — Function.

unsafe_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!.

source

# Erdos.rebuild! — Function.

rebuild!(g)

Check and restore the structure of g, which could be corrupted by the use of unsafe functions (e. g. unsafe_add_edge!)

source

# Erdos.rem_edge! — Function.

rem_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.

source

# Erdos.degree — Function.

degree(g, v)

Return the number of edges from the vertex v.

source

# Erdos.in_degree — Function.

in_degree(g, v)

Returns the number of edges which start at vertex v.

source

# Erdos.out_degree — Function.

out_degree(g, v)

Returns the number of edges which end at vertex v.

source

# Erdos.neighbors — Function.

neighbors(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.

source

# Erdos.in_neighbors — Function.

in_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.

source

# Erdos.out_neighbors — Function.

out_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.

source

# Erdos.all_neighbors — Function.

all_neighbors(g, v)

Iterates over all distinct in/out neighbors of vertex v in g.

source

# Erdos.edges — Function.

edges(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.

source

edges(g)

Returns an iterator to the edges of a graph g. The returned iterator is invalidated by changes to g.

source

# Erdos.in_edges — Function.

in_edges(g, v)

Returns an iterator to the edges in g going to vertex v. v == dst(e) for each returned edge e.

source

# Erdos.out_edges — Function.

out_edges(g, v)

Returns an iterator to the edges in g coming from vertex v. v == src(e) for each returned edge e.

source

# Erdos.all_edges — Function.

all_edges(g, v)

Iterates over all in and out edges of vertex v in g.

source

# Erdos.swap_vertices! — Function.

swap_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.

source

# Erdos.has_vertex — Function.

has_vertex(g, v)

Return true if v is a vertex of g.

source

# Erdos.is_directed — Function.

is_directed(g)

Check if g a graph with directed edges.

source

# Base.reverse — Function.

reverse(e)

Returns an edge with swapped src(e) and dst(e).

source

reverse(g::ADiGraph)

Produces a graph where all edges are reversed from the original.

source

# Base.reverse! — Function.

reverse!(g::DiGraph)

In-place reverse (modifies the original graph).

source

# Erdos.adjacency_list — Function.

adjacency_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.

source

# Erdos.clean_vertex! — Function.

clean_vertex!(g, v)

Remove all incident edges on vertex v in g.

source

# Erdos.density — Function.

density(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.

source

# Erdos.vertices — Function.

vertices(g)

Returns an iterator to the vertices of a graph (i.e. 1:nv(g))

source

# Erdos.has_self_loops — Function.

has_self_loops(g)

Returns true if g has any self loops.

source

# Erdos.num_self_loops — Function.

num_self_loops(g)

Returns the number of self loops in g.

source

# Erdos.is_graphical — Function.

is_graphical(degs::Vector{Int})

Check whether the degree sequence degs is graphical, according to Erdös-Gallai condition.

Time complexity: O(length(degs)^2)

source

# Erdos.graph — Function.

graph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
    G = Graph)

Build a graph with n vertices, of type G, and given edgelist.

source

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.

source

# Erdos.digraph — Function.

digraph{G<:AGraph}(n, edgelist::Vector{Tuple{Int,Int}},
    G = Graph)

Build a digraph with n vertices, type G, and given edgelist.

source

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.

source

# Erdos.edgetype — Function.

edgetype(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).

source

# Erdos.vertextype — Function.

vertextype(g)
vertextype(G)

Returns the integer type of vertices of graph g (or graph type G).

source

# Erdos.graphtype — Function.

graphtype{G<:AGraphOrDiGraph}(::Type{G})

The graph type corresponding to G. If G<:AGraph returns G, if G<:ADiGraph returns a type H<:AGraph.

source

# Erdos.digraphtype — Function.

digraphtype{G<:AGraphOrDiGraph}(::Type{G})

The digraph type corresponding to G. If G<:ADiGraph returns G, if G<:AGraph returns a type H<:ADiGraph.

source