missing.topology — org.clojars.rutledgepaulv/missing 0.1.37

Simple graph functions for graphs in adjacency map form.

append-edge clj

(append-edge g [from to])

Appends an edge to a graph.

append-path clj

(append-path g path)

Appends a path onto a graph.

bidirectional clj

(bidirectional g)

Returns a new graph where all edges go both directions.

branches clj

(branches g)

Returns the branches of the tree.

bridge? clj

(bridge? g edge)

Is the given edge a bridge of the graph g?

bridges clj

(bridges g)

Returns the edges whose removal would alter the transitive closure of the graph (increase the number of connected components).

complement clj

(complement g)

Returns the difference between fully connected g and g

complete clj

(complete g)

Returns the fully connected variant of g

complete? clj

(complete? g)

Is the graph complete?

connected? clj

(connected? g)

Can you navigate from any starting node to any other node?

consumers clj

(consumers g)

Get all nodes with inbound edges.

contractg clj

(contractg pred g)

Removes nodes that match pred and adds new edges between inbound and outbound neighbors of each node impacted (leaves the transitive closure otherwise intact).

cyclical? clj

(cyclical? g)

Are there cycles in this graph?

defgn clj macro

(defgn symbol docs bindings & body)

Like defn but handles normalizing any 'g or g{digit}' arguments first.

degree clj

(degree g n)

How many edges does this node have?

difference clj

(difference g1 g2)

Subtract g2 from g1.

edges clj

(edges g)

Get the set of edges of graph g.

empty clj

(empty g)

Returns a graph with the same nodes as g but no edges.

exclusive? clj

(exclusive? g1 g2)

Returns whether the graphs don't overlap.

expandg clj

(expandg f g)

Expand nodes into more nodes while maintaining all the same edges between any new nodes.

exterior clj

(exterior g)

Returns the exterior nodes of the graph.

filterg clj

(filterg pred g)

Only keep nodes in the graph that satisfy pred. All inbound and outbound edges involving removed nodes are also removed.

graph clj

(graph edges)

(graph nodes edges)

Create a graph from a set of edges

incoming-degree clj

(incoming-degree g n)

Gets the incoming degree of n.

incoming-edges clj

(incoming-edges g n)

Get all edges that go from another node to n.

incoming-neighbors clj

(incoming-neighbors g n)

Gets the neighbors of n from any inbound edges.

interior clj

(interior g)

Returns the interior nodes of the graph.

intersect? clj

(intersect? g1 g2)

Returns whether the graphs overlap.

intersection clj

(intersection g1 g2)

Intersect two graphs.

inverse clj

(inverse g)

Invert the graph by reversing all edges.

leaves clj

(leaves g)

Returns the leaves of the tree.

mapg clj

(mapg f g)

Transform nodes in the graph according to f.

neighbors clj

(neighbors g n)

Gets all the neighbors of n.

nodes clj

(nodes g)

Get all nodes from the graph g.

normalize clj

(normalize g)

Given an adjacency with potentially missing entries, populate the entries based on the appearance of other nodes on the right side of an edge. Tags the result with metadata so it doesn't recompute for repeat invocations.

outgoing-degree clj

(outgoing-degree g n)

Gets the outgoing degree of n.

outgoing-edges clj

(outgoing-edges g n)

Get all edges that go from n to another node.

outgoing-neighbors clj

(outgoing-neighbors g n)

Gets the neighbors of n from any outbound edges.

producers clj

(producers g)

Get all nodes with outbound edges.

remove-edge clj

(remove-edge g [from to])

Removes an edge from a graph.

remove-path clj

(remove-path g path)

Removes a path from a graph.

removeg clj

(removeg pred g)

Remove nodes in the graph that satisfy pred. All inbound and outbound edges involving removed nodes are also removed.

root clj

(root g)

Returns the root of the graph if any, else nil.

select clj

(select g from)

Return the subgraph of g that is within reach of 'from'

self-looped clj

(self-looped g)

Returns a new graph where self-loops were added to all nodes in g.

self-loops clj

(self-loops g)

Returns the nodes that have self-loops.

shortest-paths clj

(shortest-paths g & [weight-fn])

Uses Floyd-Warshall to returns a map of {[source destination] {:distance <num> :path [source ... destination]}} for the given graph. Uses weight-fn (a function of two nodes) to assign a cost to edges.

sink? clj

(sink? g n)

Is n a node with no outgoing edges?

sinks clj

(sinks g)

Get all nodes with no outbound edges.

source? clj

(source? g n)

Is n a node with no incoming edges?

sources clj

(sources g)

Get all nodes with no inbound edges.

subgraph? clj

(subgraph? g1 g2)

Is g1 a subgraph of g2?

supergraph? clj

(supergraph? g1 g2)

Is g1 a supergraph of g2?

symmetric-difference clj

(symmetric-difference g1 g2)

Returns the union of the exclusive sections of g1 and g2.

topological-sort clj

(topological-sort g)

Returns a topological sort of the adjacency map

topological-sort-with-grouping clj

(topological-sort-with-grouping g)

Returns a topological sort of the adjacency map and partition items into sets where order is arbitrary.

transitive-closure clj

(transitive-closure g)

Creates new edges on g such that every node connects directly to any node that could previously have been connected indirectly.

transitive-difference clj

(transitive-difference g1 g2)

Returns the subgraph of g1 that isn't transitively referenced by g2.

transitive-intersection clj

(transitive-intersection g1 g2)

The intersection of g1 and g2, extended by anything transitively reachable in either graph.

transitive-symmetric-difference clj

(transitive-symmetric-difference g1 g2)

Returns the union of those subgraphs which appear in either g1 or g2 but do not appear in their transitive intersection.

transitive-union clj

(transitive-union g1 g2)

Returns g1 extended by the transitive intersection of g1 and g2.

tree? clj

(tree? g)

Is this graph a tree?

union clj

(union g1 g2)

Union two graphs together.

walk? clj

(walk? g [x1 x2 & xs])

Check if the given walk is valid for the graph.