Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the graph Reference Manual, version 0.0.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Mon Aug 15 04:43:03 2022 GMT+0.
Next: Systems, Previous: The graph Reference Manual, Up: The graph Reference Manual [Contents][Index]
GRAPH - simple graph data structure and algorithms
The GRAPH library strives for simplicity both in backing data
structures and in usage. Graphs and Digraphs are represented as CLOS
objects with methods and algorithms provided for graph manipulation
and analysis.
Note: currently this library is only supported on SBCL, Clozure CL,
and Allegro CL because of the need to create hashes with custom
equality tests, however custom equality tests are commonly
supported so extending to other lisps should be simple. Patches
welcome.
For more information see http://eschulte.github.com/graph.
Next: Files, Previous: Introduction, Up: The graph Reference Manual [Contents][Index]
The main system appears first, followed by any subsystem dependency.
Next: graph/graph, Previous: Systems, Up: Systems [Contents][Index]
simple library for building and manipulating graphs
Eric Schulte <schulte.eric@gmail.com>
Thomas Dye
MIT
0.0.0
asdf-package-system (system).
Eric Schulte <schulte.eric@gmail.com>
Thomas Dye
MIT
Next: Packages, Previous: Systems, Up: The graph Reference Manual [Contents][Index]
Files are sorted by type and then listed depth-first from the systems components trees.
Next: graph/graph/file-type.lisp, Previous: Lisp, Up: Lisp [Contents][Index]
graph (system).
Previous: graph/graph.asd, Up: Lisp [Contents][Index]
graph/graph (system).
Next: Definitions, Previous: Files, Up: The graph Reference Manual [Contents][Index]
Packages are listed by definition order.
graph
Next: Indexes, Previous: Packages, Up: The graph Reference Manual [Contents][Index]
Definitions are sorted by export status, category, package, and then by lexicographic order.
Next: Internals, Previous: Definitions, Up: Definitions [Contents][Index]
Next: Generic functions, Previous: Public Interface, Up: Public Interface [Contents][Index]
Return an Erdős–Rényi digraph with N nodes and M edges.
Return an Erdős–Rényi graph with N nodes and M edges.
Next: Classes, Previous: Ordinary functions, Up: Public Interface [Contents][Index]
Add EDGE to GRAPH with optional VALUE. The nodes of EDGE are also added to GRAPH.
Add NODE to GRAPH.
Return the combination of paths PATH1 and PATH2 through GRAPH. Each element of PATH has the form (cons edge value).
List nodes adjacent from NODE in DIGRAPH.
List nodes adjacent to NODE in DIGRAPH.
Return all paths in GRAPH from A to B.
Return all basic cycles in the GRAPH.
Fraction of shortest paths through GRAPH which pass through NODE. Fraction of node pairs (s,t) s.t. s and t ≠ NODE and the shortest path between s and t in GRAPH passes through NODE.
Returns t if node is a carrier, i.e., both indegree and outdegree are 1.
Return a list of the carrier nodes in digraph.
Return the maximal cliques of GRAPH. The Bron-Kerbosh algorithm is used.
Return true if NODES are fully connected in GRAPH.
Inverse of the ‘farness’ for NODE in GRAPH.
Fraction of connected triples which are closed.
Return the connected component of NODE in GRAPH.
The TYPE keyword argument only has an effect for directed graphs in
which it may be set to one of the following with :STRONG being the
default value.
:STRONG ..... connections only traverse edges along the direction of
the edge
:WEAK ....... connections may traverse edges in any direction
regardless of the edge direction
:UNILATERAL . two nodes a and b connected iff a is strongly connected to b or b is strongly connected to a
Return a list of the connected components of GRAPH.
Keyword TYPE is passed to ‘connected-component’ and only has effect
for directed graphs. Returns strongly connected components of a
directed graph by default.
Return all connected node groups of SIZE in GRAPH.
Return true if the graph is connected.
TYPE keyword argument is passed to ‘connected-components’.
Return a copy of GRAPH.
Return all cycles of GRAPH (both basic and compound).
Return the degeneracy and k-cores of GRAPH.
Also return the node ordering with optimal coloring number as an
alist. The ‘car’ of each element of the alist identifies k-cores and
the ‘cdr’ holds the nodes in the ordering.
Return the degree of NODE in GRAPH.
Delete EDGE from GRAPH. Return the old value of EDGE.
Delete NODE from GRAPH.
Delete and return the old edges of NODE in GRAPH.
Copy GRAPH into a ‘digraph’ and return.
Populate GRAPH including every possible edge with probability P.
Return all edges which share a node with EDGE in GRAPH.
Return the value of EDGE in GRAPH.
Set the value of EDGE in GRAPH to NEW.
Return a list of the edges in GRAPH.
Set the edges in GRAPH to NEW.
Return an alist of edges of GRAPH with their values.
Set the edges of graph to edges and values in NEW.
Populate GRAPH with M edges in an Erdős–Rényi random graph model.
Sum of the distance from NODE to every other node in connected GRAPH. Optional argument HEURISTIC if supplied is passed through to guide the A* search used in ‘shortest-path’.
Populate GRAPH with the contents of PLIST.
Populate GRAPH from the value matrix MATRIX.
Compare GRAPH1 and GRAPH2 for equality.
Copy DIGRAPH into a ‘graph’ and return.
Return ‘true’ if GRAPH has edge EDGE.
Return ‘true’ if GRAPH has node NODE.
The number of edges directed to NODE in GRAPH.
Returns t if node is an isolate, i.e., both indegree and outdegree are 0.
Return a list of the isolated nodes in digraph.
Return the k-cores of GRAPH.
Combined measure of number and nearness of nodes to NODE.
Keyword argument HEURISTIC if supplied is passed through to guide the
A* search used in ‘shortest-path’.
Assign a positive integer to each node in DIGRAPH,
called its level, where, for each directed edge (a b) the
corresponding integers satisfy a < b. Returns either a hash table
where the nodes are keys and the levels are values, or an association
list of nodes and their levels, along with the number of levels in
DIGRAPH.
Return the maximum flow from FROM and to TO in GRAPH.
GRAPHS must be a network with numeric values of all edges (otherwise a
default cost of 1 is used for every edge). The Ford-Fulkerson
algorithm is used. Optional argument HEURISTIC if supplied is passed
through to guide the A* search used in ‘shortest-path’.
Combine EDGE1 and EDGE2 in GRAPH into a new EDGE.
Optionally provide a value for the new edge, the values of EDGE1 and
EDGE2 will be combined.
Combine NODE1 and NODE2 in GRAPH into the node NEW.
All edges of NODE1 and NODE2 in GRAPH will be combined into a new node
of value NEW. Edges between only NODE1 and NODE2 will be removed.
Return both the global min-cut of GRAPH and the weight of the cut.
Return a minimum spanning tree of GRAPH.
Prim’s algorithm is used. Optional argument TREE may be used to
specify an initial tree, otherwise a random node is used.
Return all nodes which share an edge with NODE in GRAPH.
Return the value of NODE in GRAPH.
Set the edges of NODE in GRAPH to NEW.
Delete and return the old edges of NODE in GRAPH.
Return a list of the nodes in GRAPH.
Set the nodes in GRAPH to NEW.
Return an alist of nodes of GRAPH with their values.
Return a list of the ordinary nodes in digraph.
Returns t if node is ordinary, i.e., is not a transmitter, receiver, isolate, or carrier.
The number of edges directed from NODE in DIGRAPH.
Populate the nodes and edges of GRAPH based on keyword arguments.
Return all nodes preceding NODE in an edge of DIGRAPH.
Add NODES to GRAPH using preferential attachment, return the new edges. Optionally assign edge values from those listed in EDGE-VALS.
Returns t if node is a receiver, i.e., has outdegree of 0 and positive indegree.
Return a list of the receivers in digraph.
Return the residual graph of GRAPH with FLOW.
Each edge in the residual has a value equal to the original capacity
minus the current flow, or equal to the negative of the current flow.
Return a copy of GRAPH with all edges reversed.
Return the shortest path in GRAPH from A to B.
Implemented using A* search. Optional argument HEURISTIC may be a
function which returns an estimated heuristic cost from an node to the
target B. The default value for HEURISTIC is the constant function of
0, reducing this implementation to Dijkstra’s algorithm. The
HEURISTIC function must satisfy HEURITIC(x)≤d(x,y)+HEURITIC(y) ∀ x,y
in GRAPH allowing the more efficient monotonic or "consistent"
implementation of A*.
Return the nodes of GRAPH partitioned into strongly connected components. Uses Tarjan’s algorithm.
Return the subgraph of GRAPH restricted to NODES.
Serialize GRAPH as a plist.
Keyword arguments NODE-FN and EDGE-FN will be called on a node or edge
and should return a plist of data to associate with the given node or
edge in the results.
Return the value matrix of GRAPH.
Returns a topologically ordered list of the nodes in DIGRAPH, such that, for each edge in DIGRAPH, the start of the edge appears in the list before the end of the edge.
Returns t if node is a transmitter, i.e., has indegree of 0 and positive outdegree.
Return a list of the transmitters in digraph.
Previous: Generic functions, Up: Public Interface [Contents][Index]
A ‘graph’ with directed edges.
(graph/graph::make-diedge-hash-table)
:edge-h
(quote graph/graph::dir-edge-equalp)
:edge-eq
A graph consisting of ‘nodes’ connected by ‘edges’.
Nodes must be numbers symbols or keywords. Edges may be assigned
arbitrary values, although some functions assume numeric values (e.g.,
‘merge-nodes’, ‘merge-edges’, ‘max-flow’ and ‘min-cut’).
(make-hash-table)
:node-h
(graph/graph::make-edge-hash-table)
:edge-h
(quote graph/graph::edge-equalp)
:edge-eq
Previous: Public Interface, Up: Definitions [Contents][Index]
Next: Generic functions, Previous: Internals, Up: Internals [Contents][Index]
Return a copy of HASH.
Optional argument TEST specifies a new equality test to use for the
copy. Second optional argument COMB specifies a function to use to
combine the values of elements of HASH which collide in the copy due
to a new equality test specified with TEST.
Test edge hashes HASH1 and HASH2 for equality.
Test node hashes HASH1 and HASH2 for equality.
Previous: Ordinary functions, Up: Internals [Contents][Index]
Previous: Definitions, Up: The graph Reference Manual [Contents][Index]
| Jump to: | (
A B C D E F G H I K L M N O P R S T W |
|---|
| Jump to: | (
A B C D E F G H I K L M N O P R S T W |
|---|
Next: Data types, Previous: Functions, Up: Indexes [Contents][Index]
| Jump to: | E N S |
|---|
| Jump to: | E N S |
|---|
| Jump to: | C D F G P S |
|---|
| Jump to: | C D F G P S |
|---|