Changeset 32622 in project


Ignore:
Timestamp:
07/28/15 19:14:07 (5 years ago)
Author:
Jeremy Steward
Message:

Adds docs for releases 0.3, 0.4, and 0.4.1

File:
1 edited

Legend:

Unmodified
Added
Removed
  • wiki/eggref/4/graphs

    r32559 r32622  
    2222
    2323 (use graphs)
     24 (use graphs-derived)
     25
     26The latter module extends the primitives found in the graphs module to perform other graph-related functionality (e.g. searching for isomorphisms between graphs).
    2427
    2528== Description
     
    6366This may not seem like a terribly useful method to have; however, using this in conjunction with destructive operations can help hide side effects on graphs. Because non-destructive operations have to construct a copy of the graph for small changes, they can have larger performance implications down the line (adding 1 vertex to a graph with 100000 vertices means you have to first copy the original graph and then add 1 vertex to that copy destructively). If anybody has any ideas for constructing an efficient functional hash-table or graph type, please let me know, as currently this implementation utilizes srfi-69, which provides traditional (and very imperative) hash-tables.
    6467
    65 <method>(graph->list (G <graph>))</method>
     68<method>(graph->list (G <graph>))        [[DEPRECATED]]</method>
     69
     70'''NOTE:''' As of Release 0.4 this function is deprecated. It will likely be removed in the coming releases.
    6671
    6772Converts a graph-type object into an adjacency-list type format. Currently provides something along the lines of:
     
    142147<method>(graph-vertex (G <graph>) vertex)</method>
    143148
    144 Returns an alist of the attributes for a vertex in G.
     149Returns a hash table of the attributes for a vertex in G.
    145150
    146151; G : the graph to search
     
    269274Computes the degree (number of edges coming in and out of) a vertex in a graph G.
    270275
     276<method>(graph-order (G <graph>))</method>
     277
     278Returns the order of the graph. The order of a graph is defined as the number of unique vertices within a graph.
     279
     280=== graphs-derived
     281
     282==== Isomorphism
     283
     284The set of procedures below implement the VF2 algorithm for graph/subgraph isomorphism checking. To be clear with how these work, a short explanation of the implementation is provided. Specifically, there is some confusion as to what is meant by "subgraph isomorphism." In some circles, it is treated as "there is no subgraph in G1 that is isomorphic to some other graph G2." Here, subgraph isomorphism is taken to mean subgraph isomorphism as treated by the authors of the original VF2 algorithm, that is, "'''a graph G1 is subgraph isomorphic to another graph G2 if there exists some subgraph in G1 which has a direct isomorphism to graph G2.'''" In effect, this means that the order you input your graphs matters when testing for subgraph isomorphism.
     285
     286The second major thing to bear in mind is the {{semantic-feasibility?}} argument that shows up in each of the procedures below. The original authors of the VF2 paper divided their evaluation of an isomorphism into two feasibility categories: semantic and syntactic. Syntactic feasibility defines a set of rules that evaluates whether the structure of a partial mapping between two graphs provides a feasible isomorphism. However, the authors did not specify a unique or specific way to determine semantic feasibility. The reason for this is because semantic feasibility deals with evaluating whether two vertices ''n'' and ''m'' can be added to the partial mapping ''s'' based on their attributes. In the original paper the attributes of their edges (weights, length, etc.) were evaluated as semantically feasible if they existed within some tolerance (to maintain a sense of scale). Consequently, this worked well for the application the authors had in mind, but means nothing for every isomorphism problem in general. Therefore, no particular semantic-feasibility? procedure is assumed, and the default is just a dummy procedure that always returns true (this means we effectively ignore semantic information about the vertices).
     287
     288To construct a custom procedure to evaluate semantic feasibility, it should ideally be written as below:
     289
     290<procedure>(semantic-feasibility? G1 G2 s n m) => bool</procedure>
     291
     292Evaluates semantic feasibility of adding vertices ''n'' from G1 and ''m'' from G2 to the partial mapping ''s''. This can be done by evaluating the vertex attributes between ''n'' and ''m'', or by evaluating the edge attributes of ''n'' and its neighbours in G1 to that of ''m'' and its neighbours in G2.
     293
     294; G1 : the first graph
     295; G2 : the second graph
     296; s : the partial mapping between G1 and G2. Represented as a set of pairs (N . M) of feasible matches between G1 and G2
     297; n : a candidate vertex from G1
     298; m : a candidate vertex from G2
     299
     300<procedure>(graph-isomorphisms G1 G2 #!optional semantic-feasibility?)</procedure>
     301<procedure>(subgraph-isomorphisms G1 G2 #!optional semantic-feasibility?)</procedure>
     302
     303Returns a lazy-seq of all match sets between G1 and G2. Each isomorphism in the lazy-seq is represented as a set of pairs which lists the match between G1 and G2. If subgraph-isomorphisms is used instead, the algorithm attempts to find a subgraph in G1 that is isomorphic to G2.
     304
     305; G1 : the first graph
     306; G2 : the second graph
     307; semantic-feasibility? : a procedure which evaluates semantic feasibility for a candidate pair. See discussion above.
     308
     309<procedure>(graph-isomorphisms-list G1 G2 #!optional semantic-feasibility?)</procedure>
     310<procedure>(subgraph-isomorphisms-list G1 G2 #!optional semantic-feasibility?)</procedure>
     311
     312Same as above, however returns a list instead of a lazy-seq. I suggest avoiding these, as there may be many isomorphisms between two large graphs. As a result, the runtime of this is not necessarily known.
     313
     314<procedure>(graph-isomorphic? G1 G2 #!optional semantic-feasibility?)</procedure>
     315<procedure>(subgraph-isomorphic? G1 G2 #!optional semantic-feasibility?)</procedure>
     316
     317Predicate which tests if a graph G1 is isomorphic or subgraph-isomorphic to G2.
     318
     319; G1 : the first graph
     320; G2 : the second graph
     321; semantic-feasibility? : a procedure which evaluates semantic feasibility for a candidate pair. See discussion above.
     322
    271323== Repository
    272324
     
    279331== Version History
    280332
     333; 0.4.1 : Bug fix for graph-edge -> return a hash-table instead of an alist. Documentation fixes.
     334; 0.4 : Simplified implementation details for API and performance improvements for isomorphism functionality. graph-vertex returns a hash-table, not an alist.
     335; 0.3 : Adds graphs-derived module for isomorphism (VF2) functionality.
    281336; 0.2 : Initial release to the coop under BSD3 license
    282337
Note: See TracChangeset for help on using the changeset viewer.