Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the graph Reference Manual, version 0.0.0, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 11:53:34 2018 GMT+0.
• Introduction: | What graph is all about | |
• Systems: | The systems documentation | |
• Files: | The files documentation | |
• Packages: | The packages documentation | |
• Definitions: | The symbols documentation | |
• Indexes: | Concepts, functions, variables and data types |
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 and Clozure 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: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The graph system: | ||
• The graph/graph system: |
Next: The graph/graph system, Previous: Systems, Up: Systems [Contents][Index]
Eric Schulte <schulte.eric@gmail.com>
Thomas Dye
GPL V3
simple library for building and manipulating graphs
0.0.0
asdf-package-system
graph.asd (file)
Previous: The graph system, Up: Systems [Contents][Index]
graph.asd (file)
lisp.lisp (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files: |
• The graph.asd file: | ||
• The graph/graph/lisp.lisp file: |
Next: The graph/graph/lisp<dot>lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
graph.asd
Previous: The graph<dot>asd file, Up: Lisp files [Contents][Index]
graph/graph (system)
graph.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The graph/graph package: |
lisp.lisp (file)
graph
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions: | ||
• Internal definitions: |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions: | ||
• Exported generic functions: | ||
• Exported classes: |
Next: Exported generic functions, Previous: Exported definitions, Up: Exported definitions [Contents][Index]
lisp.lisp (file)
lisp.lisp (file)
Return an Erdős–Rényi digraph with N nodes and M edges.
lisp.lisp (file)
Return an Erdős–Rényi graph with N nodes and M edges.
lisp.lisp (file)
Next: Exported classes, Previous: Exported functions, Up: Exported definitions [Contents][Index]
Add EDGE to GRAPH with optional VALUE. The nodes of EDGE are also added to GRAPH.
lisp.lisp (file)
Add NODE to GRAPH.
lisp.lisp (file)
Return the combination of paths PATH1 and PATH2 through GRAPH. Each element of PATH has the form (cons edge value).
lisp.lisp (file)
Return the combination of paths PATH1 and PATH2 through DIGRAPH. Each element of path has the form (cons edge value).
Return all basic cycles in the GRAPH.
lisp.lisp (file)
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.
lisp.lisp (file)
Return the maximal cliques of GRAPH. The Bron-Kerbosh algorithm is used.
lisp.lisp (file)
Return true if NODES are fully connected in GRAPH.
lisp.lisp (file)
Inverse of the ‘farness’ for NODE in GRAPH.
lisp.lisp (file)
Fraction of connected triples which are closed.
lisp.lisp (file)
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
lisp.lisp (file)
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.
lisp.lisp (file)
Return all connected node groups of SIZE in GRAPH.
lisp.lisp (file)
Return true if the graph is connected.
TYPE keyword argument is passed to ‘connected-components’.
lisp.lisp (file)
Return a copy of GRAPH.
lisp.lisp (file)
Return all cycles of GRAPH (both basic and compound).
lisp.lisp (file)
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.
lisp.lisp (file)
Return the degree of NODE in GRAPH.
lisp.lisp (file)
Delete EDGE from GRAPH. Return the old value of EDGE.
lisp.lisp (file)
Delete NODE from GRAPH.
Delete and return the old edges of NODE in GRAPH.
lisp.lisp (file)
Copy GRAPH into a ‘digraph’ and return.
lisp.lisp (file)
Populate GRAPH including every possible edge with probability P.
lisp.lisp (file)
Return all edges which share a node with EDGE in GRAPH.
lisp.lisp (file)
Return the value of EDGE in GRAPH.
lisp.lisp (file)
(setf edge-value) (generic function)
Set the value of EDGE in GRAPH to NEW.
lisp.lisp (file)
edge-value (generic function)
Return a list of the edges in GRAPH.
lisp.lisp (file)
(setf edges) (generic function)
Set the edges in GRAPH to NEW.
Return an alist of edges of GRAPH with their values.
lisp.lisp (file)
(setf edges-w-values) (generic function)
Set the edges of graph to edges and values in NEW.
lisp.lisp (file)
edges-w-values (generic function)
Populate GRAPH with M edges in an Erdős–Rényi random graph model.
lisp.lisp (file)
Sum of the distance from NODE to every other node in connected GRAPH.
lisp.lisp (file)
Populate GRAPH with the contents of PLIST.
lisp.lisp (file)
Populate GRAPH from the value matrix MATRIX.
lisp.lisp (file)
Compare GRAPH1 and GRAPH2 for equality.
lisp.lisp (file)
Copy DIGRAPH into a ‘graph’ and return.
lisp.lisp (file)
Return ‘true’ if GRAPH has edge EDGE.
lisp.lisp (file)
Return ‘true’ if GRAPH has node NODE.
lisp.lisp (file)
The number of edges directed to NODE in GRAPH.
lisp.lisp (file)
Return the k-cores of GRAPH.
lisp.lisp (file)
Combined measure of number and nearness of nodes to NODE.
lisp.lisp (file)
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.
lisp.lisp (file)
Return the maximum flow from FROM and TO in GRAPH. GRAPHS must be a network with numeric values of all edges. The Ford-Fulkerson algorithm is used.
lisp.lisp (file)
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.
lisp.lisp (file)
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.
lisp.lisp (file)
Return both the global min-cut of GRAPH and the weight of the cut.
lisp.lisp (file)
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.
lisp.lisp (file)
Return all nodes which share an edge with NODE in GRAPH.
lisp.lisp (file)
Return the value of NODE in GRAPH.
lisp.lisp (file)
(setf node-edges) (generic function)
Set the edges of NODE in GRAPH to NEW.
Delete and return the old edges of NODE in GRAPH.
lisp.lisp (file)
node-edges (generic function)
Return a list of the nodes in GRAPH.
lisp.lisp (file)
(setf nodes) (generic function)
Set the nodes in GRAPH to NEW.
Return an alist of nodes of GRAPH with their values.
lisp.lisp (file)
The number of edges directed from NODE in DIGRAPH.
lisp.lisp (file)
Populate the nodes and edges of GRAPH based on keyword arguments.
lisp.lisp (file)
Return all nodes preceding NODE in an edge of DIGRAPH.
lisp.lisp (file)
Add NODES to GRAPH using preferential attachment, return the new edges. Optionally assign edge values from those listed in EDGE-VALS.
lisp.lisp (file)
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.
lisp.lisp (file)
Return a copy of GRAPH with all edges reversed.
lisp.lisp (file)
Return the shortest path in GRAPH from A to B.
GRAPH must be a directed graph. Dijkstra’s algorithm is used.
lisp.lisp (file)
Return the nodes of GRAPH partitioned into strongly connected components. Uses Tarjan’s algorithm.
lisp.lisp (file)
Return the subgraph of GRAPH restricted to NODES.
lisp.lisp (file)
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.
lisp.lisp (file)
Return the value matrix of GRAPH.
lisp.lisp (file)
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.
lisp.lisp (file)
Previous: Exported generic functions, Up: Exported definitions [Contents][Index]
A ‘graph’ with directed edges.
lisp.lisp (file)
graph (class)
:edge-h
(graph/graph::make-diedge-hash-table)
edge-h (generic function)
(setf edge-h) (generic function)
:edge-eq
(quote graph/graph::dir-edge-equalp)
edge-eq (generic function)
(setf edge-eq) (generic function)
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’).
lisp.lisp (file)
standard-object (class)
digraph (class)
:node-h
(make-hash-table)
node-h (generic function)
(setf node-h) (generic function)
:edge-h
(graph/graph::make-edge-hash-table)
edge-h (generic function)
(setf edge-h) (generic function)
:edge-eq
(quote graph/graph::edge-equalp)
edge-eq (generic function)
(setf edge-eq) (generic function)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal functions: | ||
• Internal generic functions: |
Next: Internal generic functions, Previous: Internal definitions, Up: Internal definitions [Contents][Index]
lisp.lisp (file)
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.
lisp.lisp (file)
lisp.lisp (file)
lisp.lisp (file)
Test edge hashes HASH1 and HASH2 for equality.
lisp.lisp (file)
lisp.lisp (file)
lisp.lisp (file)
Test node hashes HASH1 and HASH2 for equality.
lisp.lisp (file)
lisp.lisp (file)
lisp.lisp (file)
Previous: Internal functions, Up: Internal definitions [Contents][Index]
Returns t if node is a carrier, i.e., both indegree and outdegree are 1.
lisp.lisp (file)
automatically generated reader method
lisp.lisp (file)
automatically generated writer method
lisp.lisp (file)
automatically generated reader method
lisp.lisp (file)
automatically generated writer method
lisp.lisp (file)
automatically generated reader method
lisp.lisp (file)
automatically generated writer method
lisp.lisp (file)
automatically generated reader method
lisp.lisp (file)
automatically generated writer method
lisp.lisp (file)
Returns t if node is an isolate, i.e., both indegree and outdegree are 0.
lisp.lisp (file)
Return a list of the isolated node in digraph.
lisp.lisp (file)
Return a list of the ordinary nodes in digraph.
lisp.lisp (file)
Returns t if node is ordinary, i.e., is not a transmitter, receiver, isolate, or carrier.
lisp.lisp (file)
Returns t if node is a receiver, i.e., has outdegree of 0 and positive indegree.
lisp.lisp (file)
Return a list of the receivers in digraph.
lisp.lisp (file)
Returns t if node is a transmitter, i.e., has indegree of 0 and positive outdegree.
lisp.lisp (file)
Return a list of the transmitters in digraph.
lisp.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index: | ||
• Function index: | ||
• Variable index: | ||
• Data type index: |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F G L |
---|
Jump to: | F G L |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [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 type index, Previous: Function index, Up: Indexes [Contents][Index]
Jump to: | E N S |
---|
Jump to: | E N S |
---|
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | C D G P S |
---|
Jump to: | C D G P S |
---|