Documentation
¶
Overview ¶
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Author: anupam.kapoor@gmail.com (Anupam Kapoor)
couple of commonly used algorithms for graphs are provided in this package.
this file provides the "connected-component" implementation which separates vertices of a graph into equivalece classes
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Author: anupam.kapoor@gmail.com (Anupam Kapoor)
couple of commonly used algorithms for graphs are provided in this package.
this file implements a cycle-detector which detects and returns a detected cycle in digraphs
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Author: anupam.kapoor@gmail.com (Anupam Kapoor)
couple of commonly used algorithms for graphs are provided in this package.
this file provides imeplentation of single-source bfs and dfs paths in a graph, and some routines to query/enumerate such paths
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Author: anupam.kapoor@gmail.com (Anupam Kapoor)
couple of commonly used algorithms for graphs are provided in this package.
this file implements the topological-sort order for a digraph
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func ComputeTopologicalOrder ¶
this function computes the topological order for a given digraph. returns an error if no such ordering is possible
Types ¶
type ConnectedComponent ¶
type ConnectedComponent struct {
// contains filtered or unexported fields
}
func New ¶
func New(G graph.GraphOps) (CC *ConnectedComponent)
find all connected-components in a graph using breadth-first-search
func (*ConnectedComponent) Count ¶
func (CC *ConnectedComponent) Count() int32
returns the number of connected components in the source graph
func (*ConnectedComponent) IsConnected ¶
func (CC *ConnectedComponent) IsConnected(v, w int32) (yesno bool, err error)
returns true if v is connected to w false otherwise. signals an error if either v/w are invalid vertices for the graph
func (*ConnectedComponent) String ¶
func (CC *ConnectedComponent) String() string
type GraphPath ¶
type GraphPath struct {
// contains filtered or unexported fields
}
func BFSPath ¶
this function is called to compute the breadth-first-search path for the given graph from a source vertex
Example ¶
fname := "../data/graph-003.data"
g, _ := graph.LoadFromFile(fname)
source_vertex := int32(0)
bfs_path := BFSPath(g, source_vertex)
fmt.Printf("%s\n", bfs_path)
Output: source-vertex: 0 0: 0 1: 0 2: 0 3: 2 4: 2 5: 0
func DFSPath ¶
this function is called to compute the depth-first-search path for the given graph from a source vertex
Example ¶
fname := "../data/graph-003.data"
g, _ := graph.LoadFromFile(fname)
source_vertex := int32(0)
dfs_path := DFSPath(g, source_vertex)
fmt.Printf("%s\n", dfs_path)
Output: source-vertex: 0 0: 0 1: 2 2: 3 3: 5 4: 2 5: 0
func (*GraphPath) HasPathTo ¶
this function returns true if a path from source -> dst exists, false otherwise. signals an error if the dst doesn't seem to be valid.
Source Files